Bit Manipulation Tricks for Interviews

Why bits matter#

Computers store integers in binary. Bit manipulation means working with those bits directly using bitwise operators. It produces some of the fastest and most memory-efficient solutions in programming, and it's a favourite interview topic. Real-world uses include permission flags, feature toggles, network subnet masks, compression, hashing and graphics.

13 in binary:   1    1    0    1
place value:    8    4    2    1      → 8 + 4 + 1 = 13

The bitwise operators#

a, b = 12, 10
print(f"a & b  = {a & b:2}  ({a & b:04b})")
print(f"a | b  = {a | b:2}  ({a | b:04b})")
print(f"a ^ b  = {a ^ b:2}  ({a ^ b:04b})")
print(f"~a     = {~a}")
print(f"a << 1 = {a << 1}")
print(f"a >> 2 = {a >> 2}")

Output:

a & b  =  8  (1000)
a | b  = 14  (1110)
a ^ b  =  6  (0110)
~a     = -13
a << 1 = 24
a >> 2 = 3

Why is ~12 equal to −13? Integers use two's complement, where -x == ~x + 1, so ~x == -x - 1.

Working with a single bit#

Bit positions are counted from 0 at the right. Build a mask with 1 << i:

A practical example — permission flags stored in a single integer:

READ, WRITE, DELETE, ADMIN = 1 << 0, 1 << 1, 1 << 2, 1 << 3

perms = READ | WRITE                  # grant read + write
print(f"{perms:04b}", "can write:", bool(perms & WRITE))

perms |= DELETE                       # grant delete
perms &= ~WRITE                       # revoke write
print(f"{perms:04b}", "can write:", bool(perms & WRITE), "can delete:", bool(perms & DELETE))

perms ^= ADMIN                        # toggle admin on
print(f"{perms:04b}", "is admin:", bool(perms & ADMIN))

Output:

0011 can write: True
0101 can write: False can delete: True
1101 is admin: True

Unix file permissions (chmod 755), Python's re.IGNORECASE | re.MULTILINE and many database "flags" columns work exactly like this.

Classic tricks#

def count_set_bits(n: int) -> int:
    """Brian Kernighan's algorithm: loops once per 1 bit, not once per bit."""
    count = 0
    while n:
        n &= n - 1          # drop the lowest set bit
        count += 1
    return count

for n in (0, 1, 6, 16, 255):
    power_of_two = n > 0 and n & (n - 1) == 0
    print(f"{n:>3} = {n:08b}  set bits: {count_set_bits(n)}  power of two: {power_of_two}  lowest bit: {n & -n}")

Output:

  0 = 00000000  set bits: 0  power of two: False  lowest bit: 0
  1 = 00000001  set bits: 1  power of two: True  lowest bit: 1
  6 = 00000110  set bits: 2  power of two: False  lowest bit: 2
 16 = 00010000  set bits: 1  power of two: True  lowest bit: 16
255 = 11111111  set bits: 8  power of two: False  lowest bit: 1

In Python 3.10+ you can also use n.bit_count().

XOR interview problems#

XOR has three properties that solve many puzzles:

• x ^ x = 0 (a number cancels itself)
• x ^ 0 = x
• XOR is commutative and associative (order doesn't matter)

Single number: every element appears twice except one. XOR everything — the pairs cancel out. O(n) time, O(1) space.

Missing number: an array contains 0..n with one number missing. XOR all indices and values; everything pairs up except the missing one.

from functools import reduce
from operator import xor

def single_number(nums):
    return reduce(xor, nums)

def missing_number(nums):
    result = len(nums)
    for i, value in enumerate(nums):
        result ^= i ^ value
    return result

print(single_number([4, 1, 2, 1, 2]))
print(missing_number([3, 0, 1]))
print(missing_number([9, 6, 4, 2, 3, 5, 7, 0, 1]))

Output:

4
2
8

Bitmasks for subsets#

Each integer from 0 to 2^n − 1 represents a subset: bit i set means "include element i". This gives a non-recursive way to generate all subsets — and is the basis of bitmask dynamic programming (e.g. travelling salesman on small inputs).

items = ["a", "b", "c"]
for mask in range(1 << len(items)):
    subset = [items[i] for i in range(len(items)) if mask >> i & 1]
    print(f"{mask:03b} → {subset}")

Output:

000 → []
001 → ['a']
010 → ['b']
011 → ['a', 'b']
100 → ['c']
101 → ['a', 'c']
110 → ['b', 'c']
111 → ['a', 'b', 'c']

Language notes#

• Python integers have unlimited size, so there's no overflow; negative numbers behave as if they had infinitely many leading 1s. Use n & 0xFFFFFFFF to simulate 32-bit behaviour.
• In Java, C and C++, integers are fixed-width; >> is arithmetic (keeps the sign) and Java's >>> is logical (fills with zeros).
• Operator precedence differs between languages: in C, C++, Java and JavaScript, n & 1 == 0 is parsed as n & (1 == 0) — a classic bug. Python gives bitwise operators higher precedence than comparisons, so it works there, but writing (n & 1) == 0 is clearer in every language.

Common mistakes#

• Precedence bugs when porting code — & binds looser than == in C-family languages; parenthesise bitwise expressions in comparisons.
• Assuming fixed width in Python — ~5 is −6, not a large positive number.
• Off-by-one bit positions — bit 0 is the rightmost (least significant).
• Over-optimising — n % 2 is perfectly clear and compilers optimise it anyway; use bit tricks where they simplify the solution.

Key takeaways#

• AND, OR, XOR, NOT and shifts operate on individual bits.
• Masks (1 << i) check, set, clear and toggle bits — the basis of permission flags.
• n & (n - 1) removes the lowest set bit; use it for power-of-two checks and counting bits.
• XOR cancels pairs, solving "single number" and "missing number" in O(1) space.
• Integers from 0 to 2ⁿ − 1 enumerate all subsets as bitmasks.