Position of the First (Lowest) Set Bit
Implement int first_set_bit(uint32_t n) that returns the 1-based position of the lowest set bit, or 0 if no bit is set. This matches the POSIX ffs() function.
Example: 18 (binary 10010) → 2; 1 → 1; 0x80000000 → 32; 0 → 0.
Write your code on the right and press Run (or Ctrl + Enter). Hidden tests check your functions and print the result below the editor.
Handle 0 first, or the loop never ends. Then shift right until the lowest bit is 1, counting the shifts. For a faster version, n & -n isolates the lowest set bit.
#include <stdio.h>
#include <stdint.h>
int first_set_bit(uint32_t n)
{
if (n == 0)
return 0; /* no set bit: also prevents an endless loop */
int pos = 1;
while ((n & 1u) == 0) {
n >>= 1;
pos++;
}
return pos;
}
Your version is correct, and the n == 0 check is essential: without it the loop shifts zeros forever.
Walk-through: n = 18 = 0b10010
| n | n & 1 | pos |
|---|---|---|
| 10010 | 0 | 1 → shift |
| 01001 | 1 | 2 → stop |
Result: 2.
Faster ways (what interviewers ask next):
- n & -n (or n & (~n + 1)) keeps only the lowest set bit: 18 → 00010. Its position is then a single count.
- Built-ins: __builtin_ctz(n) + 1 (count trailing zeros, undefined for 0) or __builtin_ffs(n), which compile to one or two instructions. On Arm, ctz is RBIT followed by CLZ.
- Highest set bit instead: 32 - __builtin_clz(n) gives the 1-based position (this is ⌊log₂ n⌋ + 1).
Where it is used in firmware: finding the highest-priority pending interrupt or ready task from a bitmap (RTOS schedulers such as FreeRTOS's optimised port and Zephyr do this with CLZ), allocating the first free slot from a bitmap, and decoding which flag in a status register fired.
Note the convention: this question uses 1-based positions with 0 meaning "none". If an interviewer asks for 0-based positions, you need another way to signal "no bit set", such as returning −1.
Show the hidden tests
/* ---- tests ---- */
static int fails;
#define CHECK(c) do { if (!(c)) { printf("FAIL line %d: %s\n", __LINE__, #c); fails++; } } while (0)
int main(void)
{
CHECK(first_set_bit(18) == 2);
CHECK(first_set_bit(1) == 1);
CHECK(first_set_bit(0) == 0);
CHECK(first_set_bit(0x80000000u) == 32);
CHECK(first_set_bit(0xFFFFFFFFu) == 1);
CHECK(first_set_bit(0x00010000u) == 17);
CHECK(first_set_bit(12) == 3); /* 1100 */
puts(fails ? "Some tests failed" : "All tests passed");
return fails != 0;
}