Foundation · Module 2 · Lesson 5
Bit operations
Set, clear, toggle, test, and count bits.
Lesson 11 of 123
1d streakBit Manipulation: Kernighan’s Algorithm & Low-Level Invariants
Bit manipulation leverages single-cycle CPU ALU operations to achieve maximum algorithmic efficiency. Essential bit invariants include: (1) n & (n - 1) clears the lowest set bit; (2) n & (-n) isolates the lowest set bit; (3) (n & (1 << k)) != 0 tests if the k-th bit is set; (4) n ^ (1 << k) toggles bit k; (5) n & (n - 1) == 0 verifies whether n is a positive power of two.
Architectural Boundary · Do Not Confuse
Modulo Loop: O(log N) Shifts
Kernighan’s Trick: O(K) Set Bits
Testing bits via while (n > 0) { if (n & 1) count++; n >>= 1; } runs in 32 iterations. Brian Kernighan’s algorithm n &= (n - 1) loops exactly K times where K is the number of 1-bits.
// Kernighan's Algorithm: Count set bits in O(number of 1s)
public int countSetBits(int n) {
int count = 0;
while (n != 0) {
n &= (n - 1); // Clears the lowest set bit
count++;
}
return count;
}
// Power of Two check in O(1)
public boolean isPowerOfTwo(int n) {
return n > 0 && (n & (n - 1)) == 0;
}
// Isolate lowest set bit (e.g. 12 = 0b1100 -> returns 4 = 0b0100)
public int lowestSetBit(int n) {
return n & (-n);
}Active Recall Checkpoint
Why does the operation n & (-n) isolate the lowest set bit in two’s complement representation?
Show answer & explanation
In two’s complement, -n is formed by inverting all bits (~n) and adding 1. Adding 1 flips all trailing 0s up to and including the lowest set bit. Bitwise ANDing n & (-n) cancels all higher bits while preserving only the lowest set bit.
Use it when
Use bit manipulation for compact bitmask state representation in DP (e.g. Traveling Salesperson), fast power-of-two validations, and Bloom filter hashing.
Reconsider when
Be vigilant about operator precedence in Java: equality (==) has higher precedence than bitwise AND (&). Always wrap bitwise expressions in parentheses: ((n & mask) != 0).
Cost Model
Complexity & Trade-offs
When to use it
- Counting, divisibility, modular cycles, masks, and overflow-safe arithmetic.
- Replacing simulation with a mathematical identity.
- Encoding compact state for search and dynamic programming.
Common mistakes
- Using an identity without checking its domain or overflow behavior.
- Forgetting how the language handles negative remainder and signed shifts.
- Confusing value magnitude with the number of input values.
Practice prompts
- Reproduce the worked Bit operations example without looking at the trace.
- Change one input condition and explain whether the Bit operations invariant still holds.
- Implement the approach, derive its cost, and compare it with a straightforward baseline.
Mastery check