Welcome to the Bit Manipulation module. Every integer in a computer is stored as a sequence of binary digits (bits)—zeros and ones. Bit manipulation operates directly on those binary digits using special bitwise operators, bypassing the usual arithmetic layer entirely.
Mastering bit manipulation lets you solve problems with space that would otherwise need hash sets or extra arrays, and unlocks powerful tricks for parity checking, power-of-two detection, and encoding subsets.
Before you start
- You know binary and hexadecimal — binary, hexadecimal.
- You know how integers are represented, including two’s complement — data representation.
After this lesson you will be able to:
- Use the standard operators — AND, OR, XOR, NOT, shifts — and say what each one is for.
- Apply the common idioms: test, set, clear and toggle a bit; isolate the lowest set bit; count set bits.
- Use XOR’s self-inverse property to solve problems that otherwise need extra space.
- Enumerate all subsets of a set with a bitmask, and say when that is and is not feasible.
Study route: read 1–5, attempt the prediction in section 4, then run the lab.
1. Real-World Motivation & Physical Metaphors
Think of an 8-bit integer as a row of 8 light switches:
Decimal 53: Binary = 0 0 1 1 0 1 0 1
↑ ↑
Bit 7 Bit 0
(Most (Least
Significant) Significant)
- Turning on switch 2 (OR): Sets bit 2 to 1, regardless of its current state.
- Turning off switch 2 (AND NOT): Forces bit 2 to 0.
- Flipping switch 2 (XOR): Toggles bit 2 between 0 and 1.
Real-World Applications:
- Network Subnet Masks:
IP & MASKextracts the network address portion using bitwise AND. - Permission Systems (Linux chmod): File permissions are stored as 3-bit groups (read=4, write=2, execute=1) operated on with OR, AND, XOR.
- Game Engine State Flags: Storing 32 independent boolean game states in a single 32-bit integer.
- Cryptography: XOR-based stream ciphers and hash functions.
2. Plain-English Terminology & Concept Table
| Operator | Symbol | Behavior | Example (4-bit) |
|---|---|---|---|
| AND | & | Output 1 only if both inputs are 1. | 1100 & 1010 = 1000 |
| OR | | | Output 1 if either input is 1. | 1100 | 1010 = 1110 |
| XOR | ^ | Output 1 only if inputs differ. | 1100 ^ 1010 = 0110 |
| NOT | ~ | Flips every bit (two’s complement: ~x = -x - 1). | ~0101 = 1010 |
| Left Shift | << | Shift bits left, fill 0s on right → multiplies by . | 0011 << 2 = 1100 |
| Right Shift | >> | Shift bits right, discard low bits → divides by (floor). | 1100 >> 1 = 0110 |
3. XOR — The Core Workhorse
XOR has three properties that drive most interview bit tricks:
x ^ 0 = x (XOR with 0 is identity — no change)
x ^ x = 0 (XOR with self cancels to 0)
XOR is commutative & associative (order doesn't matter)
The Consequence: XOR the entire array → every value that appears an even number of times cancels to 0, leaving only the odd-count survivor:
# Find the single non-duplicate element in O(n) time, O(1) space
def single_number(nums: list) -> int:
result = 0
for n in nums:
result ^= n
return result
# Example: [4, 1, 2, 1, 2]
# 4 ^ 1 ^ 2 ^ 1 ^ 2 = 4 ^ (1^1) ^ (2^2) = 4 ^ 0 ^ 0 = 4 ✓4. The Essential Bit Manipulation Idioms
# 1. Check if bit i is set (nonzero = True)
(x >> i) & 1 # Shift i right, then check lowest bit
# 2. Set bit i to 1
x | (1 << i) # Create mask with only bit i set, OR it in
# 3. Clear bit i to 0
x & ~(1 << i) # Create mask with bit i cleared, AND it in
# 4. Toggle (flip) bit i
x ^ (1 << i) # XOR with mask flips only bit i
# 5. Check if x is even or odd
x & 1 # 0 = even, 1 = odd
# 6. Check if x is a power of two (exactly ONE bit set)
x > 0 and (x & (x - 1)) == 0
# 7. Clear the LOWEST set bit (Brian Kernighan's trick)
x & (x - 1) # Subtracting 1 flips lowest set bit and all below it; AND erases them
# 8. Isolate the LOWEST set bit only
x & (-x) # All other bits zeroed out5. Deep Dive: Brian Kernighan’s Bit Count
KEY INSIGHT
x & (x - 1)always clears exactly the lowest set bit.When you subtract 1 from
x, the lowest set bit flips to 0 and all bits below it flip to 1. ANDing with the originalxthen clears that bit and all below it in one operation.
def count_set_bits(x: int) -> int:
"""O(number of set bits) — Brian Kernighan's Algorithm."""
count = 0
while x:
x &= (x - 1) # Clear lowest set bit each iteration
count += 1
return count
# Example: x = 12 = 1100₂
# Iteration 1: 1100 & 1011 = 1000 (cleared bit 2)
# Iteration 2: 1000 & 0111 = 0000 (cleared bit 3)
# count = 2 ✓ (12 has two set bits)6. Time & Space Complexity
| Technique | Time | Space | Benefit |
|---|---|---|---|
| Any single bit operation | Direct hardware instruction. | ||
| Brian Kernighan bit count | where = set bits | Faster than looping all 32 bits. | |
| XOR single-number trick | Eliminates need for hash set. | ||
| Bitmask DP (subset enumeration) | Encodes all subsets of ≤20 elements in integers. |
Implementation — complete runnable example
Runnable example: save as bits.py in any empty directory and run python3 bits.py. Standard library only; writes no files.
"""Bit operations: the idioms, why they work, and where they are used."""
import random
def b(n, width=8):
return format(n & ((1 << width) - 1), f"0{width}b")
def test_bit(x, i): return (x >> i) & 1
def set_bit(x, i): return x | (1 << i)
def clear_bit(x, i): return x & ~(1 << i)
def toggle_bit(x, i): return x ^ (1 << i)
def lowest_set(x): return x & -x
def clear_lowest(x): return x & (x - 1)
def count_bits_naive(x, c):
n = 0
while x:
c[0] += 1
n += x & 1
x >>= 1
return n
def count_bits_kernighan(x, c):
"""Loops once per SET bit, not once per bit position."""
n = 0
while x:
c[0] += 1
x = clear_lowest(x)
n += 1
return n
def single_number(xs):
"""Every value appears twice except one. XOR cancels the pairs."""
out = 0
for v in xs:
out ^= v
return out
def two_singles(xs):
"""Two values appear once. Split by a bit where they differ."""
all_xor = 0
for v in xs:
all_xor ^= v
bit = lowest_set(all_xor) # a bit where the two answers differ
a = c = 0
for v in xs:
if v & bit:
a ^= v
else:
c ^= v
return tuple(sorted((a, c)))
def subsets(items):
"""Each integer from 0 to 2^n - 1 IS a subset: bit i means 'include items[i]'."""
out = []
for mask in range(1 << len(items)):
out.append([items[i] for i in range(len(items)) if mask >> i & 1])
return out
if __name__ == "__main__":
print("Block 1 - the four single-bit idioms")
x = 0b0101_0010
print(f" x = {b(x)} ({x})")
for i in (1, 4):
print(f" bit {i}: test={test_bit(x,i)} set={b(set_bit(x,i))}"
f" clear={b(clear_bit(x,i))} toggle={b(toggle_bit(x,i))}")
assert test_bit(x, 1) == 1 and test_bit(x, 2) == 0
assert set_bit(x, 2) == x | 4 and clear_bit(x, 1) == x & ~2
print(" each is a mask (1 << i) combined with the right operator:")
print(" OR sets, AND-with-NOT clears, XOR toggles, shift-and-AND tests")
print()
print("Block 2 - the lowest set bit, and why x & -x works")
for v in (0b1011_0000, 0b0000_1000, 0b0000_0001):
print(f" x = {b(v)} -x = {b(-v)} x & -x = {b(lowest_set(v))}"
f" x & (x-1) = {b(clear_lowest(v))}")
assert lowest_set(0b10110000) == 0b10000
assert clear_lowest(0b10110000) == 0b10100000
print(" in two's complement, -x is ~x + 1, which flips every bit ABOVE the")
print(" lowest set bit and leaves that bit set - so the AND isolates exactly it.")
print(" x & (x-1) does the opposite: it CLEARS the lowest set bit.")
print()
print("Block 3 - counting bits: Kernighan's loop runs once per SET bit")
print(" value bits set naive iterations Kernighan iterations")
for v in (0b1111_1111, 0b1000_0000, 0xFFFFFFFF, 1 << 40):
cn, ck = [0], [0]
n1 = count_bits_naive(v, cn)
n2 = count_bits_kernighan(v, ck)
assert n1 == n2 == bin(v).count("1")
print(f" {v:>18,} {n1:8} {cn[0]:16} {ck[0]:20}")
c = [0]
count_bits_kernighan(1 << 40, c)
assert c[0] == 1
print(" a single high bit costs Kernighan ONE iteration and the naive loop 41.")
print(" Python has int.bit_count() now; the idiom still matters in C and in")
print(" understanding what the hardware POPCNT instruction replaced.")
print()
print("Block 4 - XOR's self-inverse property does real work")
print(f" a ^ a = 0 and a ^ 0 = a, so XOR cancels pairs and order does not matter")
xs = [4, 1, 2, 1, 2]
print(f" {xs} -> the unpaired value is {single_number(xs)}")
assert single_number(xs) == 4
rng = random.Random(20260910)
for _ in range(500):
pairs = [rng.randint(0, 1000) for _ in range(rng.randint(0, 20))]
odd = rng.randint(2000, 3000)
arr = pairs + pairs + [odd]
rng.shuffle(arr)
assert single_number(arr) == odd
print(" 500 random arrays: always finds the unpaired value, O(1) space")
xs2 = [1, 2, 1, 3, 2, 5]
print(f" two unpaired: {xs2} -> {two_singles(xs2)}")
assert two_singles(xs2) == (3, 5)
print(" with TWO singles, XOR everything to get a^b, take any bit where they")
print(" differ, and split the array on that bit - each half now has one single.")
print()
print(" the classic swap-without-a-temp, and why not to use it:")
a, bb = 3, 7
a ^= bb; bb ^= a; a ^= bb
print(f" 3, 7 -> {a}, {bb}")
assert (a, bb) == (7, 3)
print(" it fails when both operands are the SAME variable (x ^= x zeroes it),")
print(" and modern compilers emit better code for a plain temporary. A curiosity.")
print()
print("Block 5 - bitmasks enumerate subsets")
items = ["a", "b", "c"]
print(f" items {items}: {1 << len(items)} subsets")
for mask in range(1 << len(items)):
sel = [items[i] for i in range(len(items)) if mask >> i & 1]
print(f" mask {b(mask, 3)} -> {sel}")
assert len(subsets(items)) == 8
assert sorted(map(len, subsets(list(range(4))))) == [0,1,1,1,1,2,2,2,2,2,2,3,3,3,3,4]
print(" every integer below 2^n IS a subset - bit i means 'include item i'.")
print(" n=20 -> 1,048,576 subsets: fine")
print(" n=40 -> over a trillion: not fine. Bitmask enumeration is O(2^n),")
print(" so it is a technique for n <= about 20-25, and never a general answer.")
print()
print("bits: passed")Expected output:
Block 1 - the four single-bit idioms
x = 01010010 (82)
bit 1: test=1 set=01010010 clear=01010000 toggle=01010000
bit 4: test=1 set=01010010 clear=01000010 toggle=01000010
each is a mask (1 << i) combined with the right operator:
OR sets, AND-with-NOT clears, XOR toggles, shift-and-AND tests
Block 2 - the lowest set bit, and why x & -x works
x = 10110000 -x = 01010000 x & -x = 00010000 x & (x-1) = 10100000
x = 00001000 -x = 11111000 x & -x = 00001000 x & (x-1) = 00000000
x = 00000001 -x = 11111111 x & -x = 00000001 x & (x-1) = 00000000
in two's complement, -x is ~x + 1, which flips every bit ABOVE the
lowest set bit and leaves that bit set - so the AND isolates exactly it.
x & (x-1) does the opposite: it CLEARS the lowest set bit.
Block 3 - counting bits: Kernighan's loop runs once per SET bit
value bits set naive iterations Kernighan iterations
255 8 8 8
128 1 8 1
4,294,967,295 32 32 32
1,099,511,627,776 1 41 1
a single high bit costs Kernighan ONE iteration and the naive loop 41.
Python has int.bit_count() now; the idiom still matters in C and in
understanding what the hardware POPCNT instruction replaced.
Block 4 - XOR's self-inverse property does real work
a ^ a = 0 and a ^ 0 = a, so XOR cancels pairs and order does not matter
[4, 1, 2, 1, 2] -> the unpaired value is 4
500 random arrays: always finds the unpaired value, O(1) space
two unpaired: [1, 2, 1, 3, 2, 5] -> (3, 5)
with TWO singles, XOR everything to get a^b, take any bit where they
differ, and split the array on that bit - each half now has one single.
the classic swap-without-a-temp, and why not to use it:
3, 7 -> 7, 3
it fails when both operands are the SAME variable (x ^= x zeroes it),
and modern compilers emit better code for a plain temporary. A curiosity.
Block 5 - bitmasks enumerate subsets
items ['a', 'b', 'c']: 8 subsets
mask 000 -> []
mask 001 -> ['a']
mask 010 -> ['b']
mask 011 -> ['a', 'b']
mask 100 -> ['c']
mask 101 -> ['a', 'c']
mask 110 -> ['b', 'c']
mask 111 -> ['a', 'b', 'c']
every integer below 2^n IS a subset - bit i means 'include item i'.
n=20 -> 1,048,576 subsets: fine
n=40 -> over a trillion: not fine. Bitmask enumeration is O(2^n),
so it is a technique for n <= about 20-25, and never a general answer.
bits: passed
Block 4 is the one with real reach: XOR’s self-inverse property turns “find the unpaired element” into a single pass with two variables.
7. Common Pitfalls & Traps
- Operator Precedence Trap: Bitwise operators bind looser than
==and+. Always parenthesize:- Wrong:
x & 1 == 0(evaluates asx & (1 == 0)=x & False= 0) - Correct:
(x & 1) == 0
- Wrong:
- Python Arbitrary Precision: Python integers have unlimited bit width with no natural 32-bit overflow. Problems requiring 32-bit behavior (like “Reverse Bits”) need explicit
& 0xFFFFFFFFmasking. ~xis-x - 1in Two’s Complement: In Python,~5 = -6, not2(which you might expect in 4-bit arithmetic).- XOR only works for odd-count uniqueness: If the “unique” element appears 3 times (not just once) among elements appearing 2 times, plain XOR won’t isolate it. You need bit-count-mod-3 tricks.
8. Check Your Understanding (University Self-Assessment)
-
Question: Using only XOR (
^), how would you swap two integer variablesaandbwithout using a temporary variable?-
Click for Answer
Answer:a = a ^ bb = a ^ b(now b = original a)a = a ^ b(now a = original b)
-
-
Question: Why does
x & (x - 1)clear exactly the lowest set bit ofx?-
Click for Answer
Answer: Subtracting 1 fromxflips the lowest set bit from 1 → 0, and sets all bits below it to 1 (binary borrowing). ANDing with the originalxthen zeros out that bit and all bits below it (which were already 0 inx).
-
-
Question: How would you check if an integer
xis a power of two using bit manipulation?-
Click for Answer
Answer:x > 0 and (x & (x - 1)) == 0. Powers of two have exactly one set bit.x & (x - 1)clears the lowest set bit, so the result is 0 if and only ifxhad exactly one set bit.
-
Practice — independent task
Implement subset_sum_bitmask(nums, target) and then improve it with meet in the middle.
- Enumerate all subsets with a bitmask, and report which sum to
target. Measure where this becomes too slow on your machine and report the . - Now split
numsin half. Enumerate the subset sums of each half separately, sort one, and for each sum in the other binary-search for the complement. Total . - Verify both give the same answers for up to 20.
- Report the real gain. At , the naive version needs operations; meet-in-the-middle needs about . Confirm the second actually runs, and state the ratio.
- Then use bitmask DP on a different problem: the travelling salesman for cities, with state
(mask of visited cities, current city). Report the state count and explain why is already out of reach.
Edge cases: an empty nums; target = 0 (the empty subset); negative numbers (does your binary search still work?); duplicate values.
Done when: both subset-sum versions agree up to , meet-in-the-middle runs at , and you can state the TSP state count for and .
Before moving on
You can use all the single-bit idioms, explain x & -x, apply XOR cancellation, and enumerate subsets with masks.
Recap: 1 << i is the mask; OR sets, AND-with-NOT clears, XOR toggles, shift-and-AND tests; x & -x isolates the lowest set bit and x & (x-1) clears it, which makes Kernighan’s count run once per set bit; a ^ a = 0 and a ^ 0 = a, so XOR cancels pairs regardless of order; an integer below is a subset, making bitmask enumeration natural but — good to about .
Next: Math and Geometry, or back to the algorithms index.
Related Modules
- Number Theory Basics — Arithmetic cousin (GCD, primality, modular arithmetic)
- Algorithms & Complexity Analysis — Space vs. time tradeoffs
Software engineering
Infrastructure & security
Computer science
Hardware & engineering