Bit manipulation

Why it matters

Bit manipulation is a smaller interview topic than graphs or DP, but it is everyday material in low-level and systems work (flags and permissions, packed formats, hashing, network masks, checksums) and a tool inside other algorithms (subset enumeration, bitmask DP, Bloom filters). Interviewers mostly check that you read and write mask expressions correctly and know where your language's integer model differs from the textbook one.

Core ideas

Masks. For bit k: test with (x >> k) & 1, set with x | (1 << k), clear with x & ~(1 << k), toggle with x ^ (1 << k). The low k bits are (1 << k) - 1.

Two's complement. In w-bit two's complement the top bit has weight -2^(w-1), so -x == ~x + 1. Consequences: x & -x keeps only the lowest set bit, x & (x - 1) clears it, and x > 0 with (x & (x - 1)) == 0 means x is a power of two. For non-negative x, repeating x &= x - 1 counts set bits in as many steps as there are ones; prefer built-ins when allowed (int.bit_count in Python 3.10+, Integer.bitCount in Java, std::popcount in C++20).

XOR. XOR is associative and commutative, x ^ x is 0 and x ^ 0 is x, so XOR-ing a collection cancels every value that appears an even number of times. When values repeat three times, count each bit position modulo 3 instead.

Subsets as integers. For n up to about 20, iterate masks from 0 to 2^n - 1 and include element i when bit i is set; a DP over subsets typically costs around O(2^n · n). The submasks of a mask can be walked with sub = (sub - 1) & mask; over all masks this totals O(3^n).

Shifts. A left shift by k multiplies by 2^k while nothing overflows. Right-shifting a negative number is arithmetic (sign-extending) in Java's >>, in Python and, since C++20, in C++; Java's >>> fills with zeros. Java masks shift distances to the low five bits for int, so 1 << 32 is 1, not 0.

Language pitfalls.

• Python integers are unbounded: ~x is -x - 1, negatives behave as if they had infinitely many leading ones, and nothing overflows. To emulate 32-bit arithmetic, mask with & 0xFFFFFFFF and convert back to signed when bit 31 is set. A loop that adds without + by propagating carries can run forever on inputs such as -1 and 1 unless you mask.
• Java has fixed-width int and long with silent wraparound; use 1L << k for bits above 31.
• In C and C++, shifting by a negative amount or by at least the bit width is undefined behavior, as is signed overflow. Left-shifting a negative value is undefined in C and was until C++20, so use unsigned types for bit work.
• Precedence: in C and C++, == binds tighter than &, ^ and |, so x & 1 == 0 silently means x & (1 == 0); Java rejects it at compile time, and Python reads it as intended. Parenthesize every bitwise subexpression.

Common misconceptions

• "x >> 1 equals x / 2 for every integer." For negative odd numbers, the arithmetic shift rounds toward negative infinity while Java and C division rounds toward zero: -3 >> 1 is -2 but -3 / 2 is -1.
• "Bit tricks are always faster." Compilers already turn multiplication and division by constants into shifts where that is valid; readable code with built-ins usually wins.
• "~5 is a large positive number." In Python it is -6, because Python integers have no fixed width.
• "1 << 31 is a large positive int in Java." It is Integer.MIN_VALUE; use long when you need 32 or more bits.

How to approach it

State the bit width and signedness before writing anything. Name your masks, test with 0, 1, a power of two, -1 and the most negative value, and compare against a plain arithmetic version on small random inputs. For low-level roles, be ready to explain what your language does on overflow and on shifts by large or negative amounts.