</>EmbeddedInterview

How do you clear the rightmost (lowest) set bit, and what other tricks use n & (n - 1)?

EasyBit Manipulation

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

  1. Power-of-two test: n && !(n & (n - 1)).
  2. Counting set bits: repeat until zero, counting the iterations (one loop per set bit).
  3. 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; }
  4. Lowest set bit as a mask: n & -n is 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.