Topics / Bit Manipulation / Q5
How do you clear the rightmost (lowest) set bit, and what other tricks use n & (n - 1)?
Short answer: n & (n - 1) turns off the lowest set bit. It is the building block for the power-of-two test, Kernighan's bit count and several other classic tricks.
uint32_t clear_lowest_set(uint32_t n) { return n & (n - 1); } /* 0b1011_0100 -> 0b1011_0000 */
uint32_t isolate_lowest_set(uint32_t n){ return n & (~n + 1); } /* 0b1011_0100 -> 0b0000_0100 (n & -n) */
uint32_t set_lowest_clear(uint32_t n) { return n | (n + 1); } /* 0b1011_0111 -> 0b1011_1111 */
uint32_t clear_trailing_ones(uint32_t n){ return n & (n + 1); } /* 0b1011_0111 -> 0b1011_0000 */
How it works: in binary, n - 1 flips the lowest 1 to 0 and all the 0s below it to 1. ANDing with the original keeps the high part, removes the lowest 1 and leaves the low part zero.
Walk-through for n = 12 (0b1100): n - 1 = 0b1011, n & (n - 1) = 0b1000 = 8. The lowest set bit (value 4) is gone.
Uses
- Power-of-two test:
n && !(n & (n - 1)). - Counting set bits: repeat until zero, counting the iterations (one loop per set bit).
- Iterating over set bits: handle pending interrupt flags or ready tasks one at a time:
c while (pending) { unsigned bit = __builtin_ctz(pending); /* index of lowest set bit */ handle(bit); pending &= pending - 1; } - Lowest set bit as a mask:
n & -nis used in Fenwick trees and to pick the highest-priority ready task when priority 0 is bit 0.
Edge case: for n = 0 the result is 0, which is fine. The n & -n form on a signed type overflows for INT_MIN, so use unsigned values.