</>EmbeddedInterview

How do you find the position of the lowest set bit?

MediumBit Manipulation

Short answer: x & -x isolates the lowest set bit, and its index is the number of trailing zeros: __builtin_ctz(x) (undefined when x == 0). For the highest set bit use 31 - __builtin_clz(x).

unsigned lowest_set_index(uint32_t x)   /* x != 0 */
{
    return (unsigned)__builtin_ctz(x);
}

unsigned highest_set_index(uint32_t x)  /* x != 0 */
{
    return 31u - (unsigned)__builtin_clz(x);
}

Portable loop (for an interview without builtins):

int lowest_set_index_loop(uint32_t x)
{
    if (x == 0) return -1;
    int i = 0;
    while ((x & 1u) == 0) { x >>= 1; i++; }
    return i;
}

How the hardware does it on Arm: CLZ (count leading zeros) exists on Arm v5 and later, including Cortex-M3/M4/M7 but not Cortex-M0/M0+. Count trailing zeros is RBIT (reverse bits) followed by CLZ.

Why x & -x isolates the lowest bit: in two's complement -x == ~x + 1. Inverting flips every bit, and adding 1 ripples up to the lowest original 1, so only that bit is common to x and -x.

x  = 0b0110_1000
-x = 0b1001_1000
x & -x = 0b0000_1000   -> bit 3

Where it is used:

  • RTOS schedulers: FreeRTOS's port-optimised task selection keeps one bit per priority and uses CLZ to find the highest ready priority in one instruction.
  • Interrupt dispatch: finding the first pending source.
  • ffs() in POSIX returns the 1-based index (0 for no bits) and is defined for 0.

Follow-up: "log₂ of a power of two?" __builtin_ctz(x). "Floor log₂ of any x?" 31 - __builtin_clz(x).