Topics / Bit Manipulation / Q8
How do you find the position of the lowest set bit?
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
CLZto 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).