</>EmbeddedInterview
← All problems · Bit Manipulation

Position of the First (Lowest) Set Bit

Easy

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.

solution.c
OutputPress Run to compile and test your code.
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;
}