Pass the coding test
Bit Manipulation Tricks For Coding Tests
Aarav is 22 minutes into an online round. Question 3: count the set bits in n . He has skipped bit manipulation all year because the & symbol scared him. He writes a slow loop that converts to a string. It just passes. Question 4 needs XOR. He loses 40 marks to a topic that takes one evening.
12 min readFree, no email neededUpdated 11 September 2026
What a bit actually is
Aarav is 22 minutes into an online round. Question 3: count the set bits in n. He has skipped bit manipulation all year because the & symbol scared him. He writes a slow loop that converts to a string. It just passes. Question 4 needs XOR. He loses 40 marks to a topic that takes one evening.
A bit is one switch. It is 0 (off) or 1 (on). Nothing more.
A number in your computer is just a row of these switches. In decimal, the digit positions mean 1, 10, 100, 1000. In binary the positions mean 1, 2, 4, 8, 16, 32 and so on, each one double the last.
So to read a binary number, add up the position values wherever there is a 1. That is the entire skill.
Vocabulary you will see in questions. The i-th bit means the bit worth 2 to the power i, counting from the right and starting at 0. So in 1101, bit 0 is 1, bit 1 is 0, bit 2 is 1, bit 3 is 1. A set bit is a bit that is 1. LSB is the rightmost bit, MSB the leftmost.
Nobody is born knowing this. It took Riya one Sunday. It will take you one too.
Reading 1011 as 11
Write the position values above the bits. Right to left: 1, 2, 4, 8.
So 1011 is 11. Going the other way, keep taking the biggest value that fits. For 13: 8 fits (5 left), 4 fits (1 left), 2 does not, 1 fits. So 13 is 1101.
Every number from 0 to 15
Powers of two have exactly one 1. Odd numbers end in 1. And 15 is 1111, one below 16 which is 10000 — a shape you will use. That second one is already a trick:
Even or odd, without the modulo
n & 1 (1 means odd, 0 means even)Only the last bit decides, because every other position is worth 2, 4, 8 — all even. Checked: 13 & 1 is 1 (odd), 10 & 1 is 0 (even).
Asked as a warm-up MCQ, and inside fast exponentiation (power in O(log n)).
AND, OR, XOR
Each one lines the two numbers up and works on one column of bits at a time. No carrying, no borrowing.
| a | b | a&b |
|---|---|---|
| 0 | 0 | 0 |
| 0 | 1 | 0 |
| 1 | 0 | 0 |
| 1 | 1 | 1 |
| a | b | a|b |
|---|---|---|
| 0 | 0 | 0 |
| 0 | 1 | 1 |
| 1 | 0 | 1 |
| 1 | 1 | 1 |
| a | b | a^b |
|---|---|---|
| 0 | 0 | 0 |
| 0 | 1 | 1 |
| 1 | 0 | 1 |
| 1 | 1 | 0 |
In words: AND keeps a 1 only if both are 1. OR keeps a 1 if either is 1. XOR keeps a 1 only if the two bits are different.
One symbol or two? && and || are the logical operators: they take whole conditions and give true or false. & and | are the bitwise ones on this page: they take numbers and work column by column. Different jobs, similar spelling. In an MCQ, read the number of symbols before you read anything else.
NOT and the two shifts
| a | ~a |
|---|---|
| 0 | 1 |
| 1 | 0 |
Flips every bit. Because computers store negatives in two's complement, flipping all the bits of n always gives -(n+1). So ~5 is -6 and ~12 is -13. That minus sign is not a bug; see the traps page.
a << k — left shift. Slide every bit k places left, pad the right with zeros. Each place doubles the number.
a >> k — right shift. Slide every bit k places right; bits that fall off the end are gone. Each place halves the number and throws the remainder away.
Multiply and divide by powers of two
n << k is n * 2^k n >> k is n / 2^kAdding a zero on the end multiplies by 2 in binary, the same way adding a zero multiplies by 10 in decimal. Checked: 13 << 1 is 26, 13 << 3 is 104, 13 >> 1 is 6 (the 0.5 is dropped).
Asked as mid = low + ((high - low) >> 1) in binary search, and segment-tree children 2*i and 2*i+1.
1 << i is the most used expression in this whole guide. It builds a mask: a number that is all zeros except a single 1 at position i.
The three XOR laws
Half the bit questions in campus tests are XOR questions wearing a costume. They all come from these three facts.
1. A number XOR itself is zero
a ^ a == 0Every column has two equal bits, and XOR gives 0 when the bits are the same. Checked: 7 ^ 7 is 0. This is why pairs cancel.
2. A number XOR zero is itself
a ^ 0 == aEvery column is a bit against 0, and XOR leaves it alone. Checked: 7 ^ 0 is 7. This is why you can start an XOR loop at 0.
3. Order does not matter
a ^ b == b ^ a and (a ^ b) ^ c == a ^ (b ^ c)Checked: 7 ^ 9 and 9 ^ 7 are both 14; (4 ^ 7) ^ 9 and 4 ^ (7 ^ 9) are both 10. So you may XOR an array in any order and pair the equal values up in your head.
Put them together: XOR every number in an array, and every value that appears twice erases itself. Whatever is left is the odd one out.
Check, set, clear, toggle
Four one-liners built on the mask 1 << i. Worked on n = 13, which is 1101.
Is the i-th bit set?
(n >> i) & 1 or n & (1 << i)Slide bit i down to the end, then keep only that last bit. Checked on 13: bit 0 gives 1, bit 1 gives 0, bit 2 gives 1, bit 3 gives 1 — exactly 1101.
Asked as subset generation, bitmask DP, "print all subsets of an array".
Set the i-th bit to 1
n | (1 << i)OR forces that one column to 1 and leaves every other column alone. Checked: 9 | (1 << 2) is 13, that is 1001 becoming 1101.
Asked as "mark this item as visited" inside bitmask problems.
Clear the i-th bit to 0
n & ~(1 << i)~(1 << i) is all ones with a single 0 at position i, so AND wipes just that column. Checked: 13 & ~(1 << 2) is 9.
Toggle the i-th bit
n ^ (1 << i)XOR with 1 flips a bit. Checked both ways: 13 ^ (1 << 2) is 9, and 9 ^ (1 << 2) is 13.
n & (n - 1)
The most useful line in the whole topic. It clears the lowest set bit of n and leaves everything else alone.
Why it works. Subtracting 1 turns the lowest 1 into a 0 and turns every 0 after it into a 1. Those two patterns share no 1s in that region, so AND wipes the lowest set bit and keeps every higher bit untouched.
Is n a power of two?
n > 0 and (n & (n - 1)) == 0A power of two has exactly one set bit. Clear that one bit and nothing is left. Checked: 16 True, 18 False, 1 True, 0 False. The n > 0 guard matters — without it, 0 wrongly passes.
Asked as LeetCode 231, and "is this a valid size for a segment tree".
Cousin trick: n & -n isolates the lowest set bit instead of clearing it. Checked: 12 gives 4, 6 gives 2, 20 gives 4. You will use it two pages from now.
Counting set bits
The naive way checks all 32 positions. Brian Kernighan's loop runs once per set bit, so a number with three 1s takes three turns, not thirty-two.
Asked as LeetCode 191 Number of 1 Bits, 338 Counting Bits, and "Hamming distance", which is just count_set_bits(a ^ b).
Swapping with XOR
Interviewers love this one because it swaps two numbers without a third variable.
Why it works. After line 1, a holds a^b. Line 2 computes (a^b)^b: the two b's cancel by law 1, leaving the old a. Line 3 computes (a^b)^a, leaving the old b. Verified with 5 and 9: they come out 9 and 5.
swap(arr, i, j)
where i == j
arr[i] ^= arr[j]
the element
becomes 0
# Python
a, b = b, a
// Java
int t = a;
a = b;
b = t;
Say this out loud in the interview. "It works, but if both sides are the same variable — swapping an element with itself inside a sort — it zeroes the value. Verified: swapping arr[0] with arr[0] on [3, 7] gives [0, 7]. It also saves nothing real, since a temporary variable lives in a register. So I know the trick, and I would not use it."
Find the single number
Every number appears twice except one. Find it in one pass, O(n) time, O(1) space.
Order does not matter (law 3), so mentally the array is 1^1 ^ 2^2 ^ 4. Each pair becomes 0 (law 1), and 0 ^ 4 is 4 (law 2).
Now the two singles. XOR everything: the pairs vanish and you are left with a ^ b. Any set bit in that result is a position where a and b differ. Split the array on that one bit; each half then holds exactly one single.
Asked as LeetCode 136 and 260, and "find the missing number in 1..n" (XOR the array with 1..n).
Four traps that cost marks
1. Java has three shift operators, Python has two
Java's >> keeps the sign; >>> shifts in zeros. Python has no >>> at all. Checked: -8 >> 1 is -4 in both languages. In Java, -8 >>> 1 is 2147483644 and -1 >>> 28 is 15. Also, Java takes the shift count mod 32 for an int, so 1 << 32 is 1, not 0.
2. ~ gives a negative number, and that is correct
~5 is -6, ~12 is -13, ~0 is -1. That is fine inside a mask like n & ~(1 << i), where the sign never reaches your answer. But never feed a negative number to the Kernighan loop in Python: Python integers have no fixed width, so n &= n - 1 starting at -5 walks -5, -6, -8, -16, -32 and never stops. Java's 32-bit int ends the same loop after 31 turns.
3. Precedence: & is weaker than ==
In Java, n & 1 == 0 parses as n & (1 == 0) and does not even compile. In Python it happens to parse the way you meant, as (n & 1) == 0 — checked, it returns True for 10. Write the brackets anyway: same code in both languages, no thinking, no surprises.
4. Java int overflows at 31 bits; Python never does
In Java, 1 << 31 is -2147483648, not 2147483648, because an int has 32 bits and the top one is the sign. Use 1L << 31 when you need the real value. Python prints 2147483648 quite happily, which means a bit solution that works in your Python practice can silently break in the Java version of the same test.
Want this on your phone?
Everything above, as a PDF built to read on a phone the morning of the interview. It costs nothing — we ask for an email so we can send it, and that is all.