Bit operations treat an integer as an array of bits, which gives O(1) set membership, compact flags and several classic interview tricks. The recurring patterns are testing a bit, setting or clearing it, counting set bits, and using XOR’s cancellation property.
Before you start
You should be comfortable with binary representation and integer arithmetic. This article uses Python’s arbitrary-precision integers; other languages need masking for fixed widths.
Step-by-step walkthrough
Step 1: Test, set and clear a bit
To test bit i, compute n & (1 << i) and compare to zero. To set it, use n | (1 << i); to clear it, use n & ~(1 << i); to toggle it, use n ^ (1 << i). These are the building blocks for flag fields and subset masks.
Step 2: Use XOR to cancel pairs
a ^ a == 0 and a ^ 0 == a, so XOR-ing a list cancels every value that appears an even number of times. Finding the single element that appears once in a list of pairs reduces to a single XOR fold, which is O(n) time and O(1) space.
Step 3: Count bits with the Kernighan trick
n & (n - 1) clears the lowest set bit, because subtracting one borrows through the trailing zeros. Looping until n is zero iterates once per set bit rather than once per bit position, which is faster for sparse numbers and is the basis of many bit-counting answers.
Worked scenario
The loop clears one set bit per iteration, so it runs exactly three times for 13.
def count_bits(n: int) -> int:
count = 0
while n:
n &= n - 1
count += 1
return count
print(count_bits(13)) # 3, because 13 is 1101 in binaryWalk through the example
13 is 1101: the loop clears the lowest set bit three times, reaching 1100, then 1000, then 0000, so count ends at 3. The number of iterations equals the number of set bits, not the bit width, which is the optimization over shifting through every position.
Common mistake
Forgetting that in fixed-width languages shifts and ~ operate on 32 or 64 bits, so a clear must mask, and a right shift of a negative number is arithmetic. In Python the width is unbounded, so an infinite loop is possible if the bit-clearing logic is wrong.
Verify the behavior
Test count_bits against a shift-and-mask implementation on values including 0 and all-ones. Assert the XOR fold returns the unique element on a small fixture and 0 when every value is paired. Check set, clear and toggle on bit 0 and a high bit to confirm the masks.
Interview exercise
Find the single number in an array where every other number appears twice.
Answer and reasoning
XOR every element together. Pairs cancel because a ^ a == 0, and zero is the identity, so the running result ends as the one unpaired value. It runs in O(n) time and O(1) space without a hash set, which is the expected optimal answer and the reason XOR is worth remembering.
Continue learning
Compare counting patterns in Hashmap counting and Prefix sums. Read the Bit manipulation reference and try the DSA interview questions.