Pattern 3: Bit fundamentals
The section's second module begins. Here we stop thinking of numbers as quantities and start seeing them as what they are inside: sequences of bits (0s and 1s). Operating on these bits solves certain problems with unbeatable elegance.
Try it first: Number of 1 Bits
Before reading the theory, try to solve it. You can start with brute force, you can fail β the point is to feel the problem. The theory comes right below.
Given a non-negative integer n, count how many 1 bits there are in its binary representation (the "Hamming weight").
Example: n = 11 (binary 1011) β 3. n = 128 (binary 10000000) β 1.
Tried it? You may have converted the number to a binary string and counted the '1's β that works! The theory below shows how to do it operating directly on the bits, and introduces a trick worth gold:
n & (n-1).
The theory: thinking in binary
An integer is stored as bits. 13 is 1101 in binary: 8 + 4 + 0 + 1. Each
position is a power of 2. The bitwise operations work on all positions at
once:
| Operator | Name | Does | Example (4 bits) |
|---|---|---|---|
a & b | AND | 1 only where both are 1 | 1100 & 1010 = 1000 |
a | b | OR | 1 where either is 1 | 1100 | 1010 = 1110 |
a ^ b | XOR | 1 where they differ | 1100 ^ 1010 = 0110 |
~a | NOT | flips all the bits | ~1100 = ...0011 |
a << k | left shift | pushes k places (Γ 2α΅) | 0011 << 1 = 0110 |
a >> k | right shift | pulls k places (Γ· 2α΅) | 0110 >> 1 = 0011 |
See it in practice (edit and try other values):
The three tricks you'll use the most
From the operators, ready-made patterns are born:
| I want to... | I do | Why |
|---|---|---|
| test the last bit | n & 1 | isolates bit 0; gives 1 if odd |
| look at bit i | (n >> i) & 1 | brings bit i to position 0 |
| turn on bit i | n | (1 << i) | OR with a one-bit mask |
| clear the rightmost 1 bit | n & (n - 1) | the star of this lesson π |
Example β Number of 1 Bits (with the n & (n-1) trick)
"How many 1 bits are there in n?" The direct solution: look bit by bit
(n & 1, then n >>= 1), 32 times β O(number of bits). It works. But there's
something smarter.
The trick: n & (n - 1) clears exactly the rightmost 1 bit of n. Why?
Subtracting 1 turns that bit into 0 and all the 0s to its right into 1; the
AND with n zeroes precisely that bit (and keeps the rest). So each
n = n & (n-1) removes one 1 bit β just count how many times until n
hits zero.
Watch the bits of n disappear one by one:
Why is this efficient?
The bit-by-bit version always does 32 steps (the width of the integer). The
n & (n-1) version does exactly as many steps as there are 1 bits β if
n has only 3 bits set, that's 3 iterations, not 32. In both cases it's
O(integer width) = O(1) for fixed-size integers, but the trick usually does
much less work. O(1) space.
π§ Review quiz
0/41. Which operator results in 1 only at positions where the two bits differ?
2. How do you test whether the last bit of n is set (n is odd)?
3. What does n & (n - 1) do to n?
4. Counting 1 bits with n & (n-1) does how many iterations for n = 11 (binary 1011)?
Summary
- Numbers are bits;
& | ^ ~ << >>operate on all positions at once. - Essential tricks:
n & 1(test the last bit),(n>>i)&1(look at bit i),n | (1<<i)(turn on bit i),n & (n-1)(clear the rightmost 1 bit). - Counting 1 bits with
n & (n-1)does only as many steps as there are set bits.
Next lesson: the operator that deserves a lesson all to itself β XOR.