The lowest 1 bit
Isolate a number's lowest 1 bit with n & −n. About 7 minutes.
How minus n is stored
Computers store −12 by flipping every bit of 12 and adding 1, a scheme called two's complement. Start with 12 as 00001100. Flip to 11110011, add 1, and the carry ripples up through the flipped zeros at the bottom to give 11110100.
The lowest 1 bit is unchanged, and every bit above it is the opposite of what 12 had.
12 is 00001100. Its lowest 1 is the 4s bit.
AND keeps only that bit
Line up 12 and −12 and keep only the bits that are on in both. Below the lowest 1, both are 0. Above it they are opposites, so they are never both 1. Only the lowest 1 survives: 00000100, which is 4.
That result is also the largest power of two that divides the number.
return n & -n
What is 12 & −12?
- A4
- B8
- C12
Show the answer
4. 12 = 1100; its lowest 1 bit is worth 4.
Lowest 1 bit
Return the value of n's lowest 1 bit (the largest power of two dividing n), or 0 if n is 0.
n = 12 → 4
0 ≤ n ≤ 2^31 − 1