Bit Tricks

Bit tricks turn a few Boolean operators into compact tools for flags, population counts, and power-of-two checks. The code is short enough to look suspicious, so this lesson keeps the full 8-bit word visible while each expression changes exactly the bits it claims to change.

You reach for these operations when the bits already carry meaning. A permission or feature-flag word needs one bit tested without disturbing the rest. A sparse set of flags can be counted or visited one 1 at a time. popcount(a ^ b) gives the Hamming distance between two bit patterns, while a power-of-two check catches invalid capacities and alignments before later bit arithmetic relies on them.

Think of an integer as a row of eight light switches. A mask is a cardboard stencil: AND lets you inspect or preserve selected switches, OR reaches through the holes to turn them on, and an inverted mask covers those holes so AND turns them off. The arithmetic trick x - 1 is stranger, but just as mechanical.

How bit tricks work: clear one 1, skip the zeros

To target bit k, build mask = 1 << k. The mask contains one 1 at bit k and zeros everywhere else. Testing x & mask asks whether that one position is set. Setting uses x | mask; clearing uses x & ~mask.

OR is idempotent here. Setting a bit that is already 1 leaves the word unchanged. Clearing is different: x & ~mask guarantees that bit becomes 0, whether it began as 0 or 1. Therefore set-then-clear restores the original word only when the target bit began clear.

The expression x & (x - 1) clears the lowest set bit. Subtracting one redraws the suffix: every higher bit stays put, the lowest 1 flips to 0, and all lower zeros become ones. Now the current value acts like the stencil. AND preserves the unchanged prefix, blocks the newly drawn lower ones, and deletes only the lowest 1. Repeat until the word reaches zero; the number of repetitions is the number of set bits.

A positive power of two has exactly one set bit, so clearing its lowest set bit produces zero. That gives the test x > 0 and (x & (x - 1)) == 0. The x > 0 guard is part of the proof, not defensive decoration: zero also satisfies the clearing expression.

Bit Tricks step by step

The default trace starts with x = 40 = 00101000 and k = 2. Shifting 1 left by two positions builds mask = 00000100.

First, 40 & 4 is zero, so bit 2 begins clear. OR reaches through the mask and sets it: 00101000 | 00000100 = 00101100, or 44. Testing the new word with the same mask now returns nonzero.

The inverted mask is 11111011 inside the visible 8-bit word. AND clears the target position: 00101100 & 11111011 = 00101000. Because bit 2 began clear, this particular set-then-clear sequence returns to 40.

The population count then starts again from the original 40. On the first pass, 40 - 1 = 39 = 00100111, and 40 & 39 = 32 = 00100000; the lowest 1 is gone, so the count becomes 1. On the second pass, 32 - 1 = 31 = 00011111, and 32 & 31 = 0; the count becomes 2. Two loop passes, two set bits.

Finally, the power-of-two section points back to the first count pass instead of calculating 40 & 39 = 32 again. That nonzero result makes 40 a clear false case. The trace then supplies the missing half of the rule: 32 & 31 = 0, so a positive one-hot value is true. Zero exposes the guard: 0 & -1 = 0 also passes the unguarded equality, but 0 > 0 is false. The guarded test therefore accepts 32 and rejects both 40 and 0 for different reasons.

Time and space complexity

For a fixed-width machine word, building a mask, testing, setting, clearing, and checking for a power of two each take O(1) time and O(1) extra space.

Kernighan's bit-counting loop runs once per set bit. If p is the population count, its time is O(p) and its extra space is O(1). Since p <= W for a W-bit word, the worst case is O(W). The usual scan-through-every-position method always pays O(W), even for a word with one lonely 1.

That distinction matters when the word is sparse or when you also need to visit each set flag: use the clear-lowest-one loop and let the data decide how many passes run. For a plain count in production code, prefer the language or CPU's native popcount operation when one is available. The same loop is still the useful proof behind that result, and popcount(a ^ b) turns it into a Hamming-distance calculation.

Edge cases

• x = 0 makes the counting loop run zero times. The power check must still return false, which is why it needs the positivity guard.
• x = 1 has one set bit. One clearing step reaches zero, so it is a power of two.
• x = 255 = 11111111 takes eight counting passes, the densest possible trace in this lesson.
• k = 0 selects the least significant bit; k = 7 selects the leftmost visible bit. The mask construction is identical.
• If bit k already equals 1, OR does nothing. Clearing afterward removes that original bit rather than restoring the input.

Common mistakes

The classic bug is dropping x > 0 from the power-of-two test. Then zero passes, because 0 & -1 is zero. The algebra did exactly what you asked; the premise was wrong.

XOR is useful for toggling a bit, but it is not a clear operation. x ^ mask turns 1 into 0 and 0 into 1. Use x & ~mask when the postcondition must be "this bit is zero."

It is also easy to memorize x & (x - 1) without understanding the borrow. Watch the suffix: subtracting one flips the lowest 1 and every position below it, then AND deletes only that 1. Without the suffix argument, the trick is a magic spell and will be forgotten on schedule.

Finally, a bit index is not a mask. The index k = 2 names a position; the mask 1 << k = 4 selects it. Mixing those two values makes tests appear to work for a few inputs and fail everywhere else.

A note on simplification

This lesson accepts non-negative values from 0 through 255 and displays their low eight bits. Python integers have arbitrary precision, while JavaScript bitwise operators coerce values to signed 32-bit integers. The chosen range makes both snippets agree on every shown result. It does not model signed masks, overflow, or language-specific shift behavior outside that range.