Module 34
Bit Manipulation
Work directly on binary: the six operators, two's complement, XOR tricks, masks, counting bits and adding without +.
Every int in Java is 32 bits. Bit manipulation reads and changes those bits directly with &, |, ^, ~, << and >>. It turns some problems into one-liners (is n a power of two?), finds the odd one out with no extra memory, and lets an int act as a set of up to 32 flags, which is what bitmask DP (Module 32) is built on.
This module explains binary and two's complement, the operators and their traps, the standard tricks (lowest set bit, clear lowest bit, test/set/clear bit i), XOR identities, and a set of classic problems.
Best after: Java for DSA
Part 1
Learn the ideas
- 34.1Binary, Two's Complement and the OperatorsJava ints are 32-bit two's complement. & | ^ ~ work bit by bit; << shifts left; >> shifts right keeping the sign; >>> shifts right filling with zeros.14 min
- 34.2Everyday Bit TricksTest, set, clear and toggle bit i; isolate or remove the lowest set bit; count bits. Each is one expression.12 min
- 34.3XOR Identitiesx ^ x = 0, x ^ 0 = x, and XOR is commutative and associative, so XOR-ing a list cancels every value that appears an even number of times.10 min
Part 2
Solve the problems
In order of difficulty. Each one shows the pattern it teaches.
XOR cancels pairs in O(1) space.
Brian Kernighan's loop: n & (n − 1) removes one set bit per step.
A DP over numbers: bits(i) = bits(i >> 1) + (i & 1).
A power of two has exactly one set bit.
Build a result bit by bit with shifts, treating the int as 32 unsigned bits.
Count each bit position modulo 3.
Split by one differing bit to isolate two singles.
Addition as XOR (sum without carry) plus AND-shift (the carries), repeated.
A 26-bit mask per word turns "no common letters" into one AND.
The AND of a range keeps only the common binary prefix of its ends.