Bit Manipulation Tricks

Every integer is already a compact array of bits, and the CPU’s bitwise instructions operate on all of them at once — no loop required. That makes bit manipulation one of the few genuinely $O(1)$ -space, $O(1)$ -time tools in the whole CP toolkit: checking membership, toggling a flag, finding the one odd-one-out in a list, or enumerating every subset of up to ~20 items all reduce to a handful of bitwise operations.

What you’ll learn

Binary representation in Python — bin()bin(), zero-padded formatting, and bit_length()bit_length().
The five core operators: AND, OR, XOR, NOT, and shifts, and what each one means bit-by-bit.
The four bit-mask idioms: check, set, clear, and toggle a single bit.
Two O(1) one-liners: the lowest set bit (x & -xx & -x) and counting set bits (x.bit_count()x.bit_count()).
XOR tricks — finding the one non-duplicate in a list, and swapping two variables without a temporary.
Bitmask subset enumeration — looping over every subset of a small set by counting from 00 to 2^n - 12^n - 1.

Binary representation

Python integers are arbitrary-precision and always signed, but bin()bin() shows the underlying bit pattern the same way any language would.

binary_representation.py

x = 22
 
print("bin:", bin(x))                  # Python prefixes binary literals with "0b"
print("8-bit padded:", format(x, "08b"))
print("hex:", hex(x))
print("parsed back:", int("10110", 2))
print("bit_length:", x.bit_length())    # minimum bits needed to represent x, ignoring sign

binary_representation.py

x = 22
 
print("bin:", bin(x))                  # Python prefixes binary literals with "0b"
print("8-bit padded:", format(x, "08b"))
print("hex:", hex(x))
print("parsed back:", int("10110", 2))
print("bit_length:", x.bit_length())    # minimum bits needed to represent x, ignoring sign

The five core operators

bitwise_operators.py

a, b = 12, 10   # 0b1100, 0b1010
 
print("a & b:", bin(a & b))    # AND: 1 only where BOTH bits are 1
print("a | b:", bin(a | b))    # OR:  1 where EITHER bit is 1
print("a ^ b:", bin(a ^ b))    # XOR: 1 where the bits DIFFER
print("~a:", ~a)               # NOT: flips every bit -- equals -(a + 1) in two's complement
print("a << 2:", a << 2, " (multiply by 4)")
print("a >> 2:", a >> 2, " (integer-divide by 4)")

bitwise_operators.py

a, b = 12, 10   # 0b1100, 0b1010
 
print("a & b:", bin(a & b))    # AND: 1 only where BOTH bits are 1
print("a | b:", bin(a | b))    # OR:  1 where EITHER bit is 1
print("a ^ b:", bin(a ^ b))    # XOR: 1 where the bits DIFFER
print("~a:", ~a)               # NOT: flips every bit -- equals -(a + 1) in two's complement
print("a << 2:", a << 2, " (multiply by 4)")
print("a >> 2:", a >> 2, " (integer-divide by 4)")

Check, set, clear, toggle: the four bit-mask idioms

Every “does this flag exist / turn it on / turn it off / flip it” question reduces to shifting a single 11 into position ii and combining it with &&, ||, or ^^.

bit_masks.py

def get_bit(num, i):
    return (num >> i) & 1                # shift bit i down to position 0, mask off the rest
 
 
def set_bit(num, i):
    return num | (1 << i)                # OR with a 1 in position i -- forces it on
 
 
def clear_bit(num, i):
    return num & ~(1 << i)               # AND with a 0 in position i -- forces it off
 
 
def toggle_bit(num, i):
    return num ^ (1 << i)                # XOR with a 1 in position i -- flips it
 
 
n = 0b1010
print("bit 1 of 1010:", get_bit(n, 1))          # expect 1
print("set bit 0:", bin(set_bit(n, 0)))         # expect 0b1011
print("clear bit 1:", bin(clear_bit(n, 1)))     # expect 0b1000
print("toggle bit 3:", bin(toggle_bit(n, 3)))   # expect 0b10

bit_masks.py

def get_bit(num, i):
    return (num >> i) & 1                # shift bit i down to position 0, mask off the rest
 
 
def set_bit(num, i):
    return num | (1 << i)                # OR with a 1 in position i -- forces it on
 
 
def clear_bit(num, i):
    return num & ~(1 << i)               # AND with a 0 in position i -- forces it off
 
 
def toggle_bit(num, i):
    return num ^ (1 << i)                # XOR with a 1 in position i -- flips it
 
 
n = 0b1010
print("bit 1 of 1010:", get_bit(n, 1))          # expect 1
print("set bit 0:", bin(set_bit(n, 0)))         # expect 0b1011
print("clear bit 1:", bin(clear_bit(n, 1)))     # expect 0b1000
print("toggle bit 3:", bin(toggle_bit(n, 3)))   # expect 0b10

Two O(1) one-liners: lowest set bit and popcount

bit_tricks.py

x = 44   # 0b101100
 
print("lowest set bit:", bin(x & -x))     # isolates the rightmost 1 bit
print("set bit count:", x.bit_count())    # number of 1 bits (Python 3.10+)
 
 
def is_power_of_two(n):
    return n > 0 and (n & (n - 1)) == 0   # a power of two has exactly ONE set bit
 
 
for value in [1, 2, 3, 4, 16, 18]:
    print(value, is_power_of_two(value))

bit_tricks.py

x = 44   # 0b101100
 
print("lowest set bit:", bin(x & -x))     # isolates the rightmost 1 bit
print("set bit count:", x.bit_count())    # number of 1 bits (Python 3.10+)
 
 
def is_power_of_two(n):
    return n > 0 and (n & (n - 1)) == 0   # a power of two has exactly ONE set bit
 
 
for value in [1, 2, 3, 4, 16, 18]:
    print(value, is_power_of_two(value))

x & -xx & -x works because of two’s complement: -x-x is ~x + 1~x + 1, which flips every bit of xx up to (and including) its lowest set bit, then that +1+1 carries all the way back to re-set exactly that lowest bit. ANDing xx with that pattern cancels every other bit, leaving only the lowest 11.

n & (n - 1)n & (n - 1) clears the lowest set bit — so a value with exactly one set bit (a power of two) becomes 00 when that bit is cleared.

XOR tricks: cancellation is the whole trick

XOR’s defining property — x ^ x == 0x ^ x == 0 and x ^ 0 == xx ^ 0 == x — means that XOR-ing a list of numbers where every value appears twice except one leaves only that one behind: every pair cancels itself out, order doesn’t matter.

xor_tricks.py

def single_number(nums):
    result = 0
    for num in nums:
        result ^= num          # duplicates cancel: x ^ x == 0
    return result
 
 
print("the one that appears once:", single_number([4, 1, 2, 1, 2]))
 
a, b = 5, 9
a = a ^ b
b = a ^ b   # b becomes the original a
a = a ^ b   # a becomes the original b
print("swapped without a temp variable:", a, b)

xor_tricks.py

def single_number(nums):
    result = 0
    for num in nums:
        result ^= num          # duplicates cancel: x ^ x == 0
    return result
 
 
print("the one that appears once:", single_number([4, 1, 2, 1, 2]))
 
a, b = 5, 9
a = a ^ b
b = a ^ b   # b becomes the original a
a = a ^ b   # a becomes the original b
print("swapped without a temp variable:", a, b)

diagram XOR cancels every duplicate pair, leaving only the single number mermaid

  graph LR
    N0["start: 0"] -- "XOR 4" --> N1["4"]
    N1 -- "XOR 1" --> N2["5"]
    N2 -- "XOR 2" --> N3["7"]
    N3 -- "XOR 1" --> N4["6"]
    N4 -- "XOR 2" --> N5["4  (answer)"]

Running the XOR left to right over [4, 1, 2, 1, 2][4, 1, 2, 1, 2]: the two 11s and the two 22s each cancel out along the way, so whatever’s left at the end has to be the 44 — the only value without a partner.

Bitmask subset enumeration

For a small set of up to ~20 items, every possible subset corresponds to exactly one integer from 00 to 2^n - 12^n - 1 — bit ii set means “item ii is included.” Looping over that range enumerates every subset without any recursion.

bitmask_subsets.py

def subsets(nums):
    n = len(nums)
    result = []
    for mask in range(1 << n):                          # every mask from 0 to 2^n - 1
        subset = [nums[i] for i in range(n) if mask & (1 << i)]
        result.append(subset)
    return result
 
 
for subset in subsets([1, 2, 3]):
    print(subset)

bitmask_subsets.py

def subsets(nums):
    n = len(nums)
    result = []
    for mask in range(1 << n):                          # every mask from 0 to 2^n - 1
        subset = [nums[i] for i in range(n) if mask & (1 << i)]
        result.append(subset)
    return result
 
 
for subset in subsets([1, 2, 3]):
    print(subset)

sketch Enumerating every subset of {1, 2, 3} as masks 0..7 p5.js

Each mask lights up exactly the elements whose bit is set -- 8 masks cover every one of the 2^3 subsets.

Practice — real LeetCode problems

One trick each: clearing the lowest set bit, reusing an already-computed answer one bit to the right, and counting bits modulo 3 instead of modulo 2.

LC 191 — Number of 1 Bits · Easy

Problem. Return the number of set bits in the binary representation of a positive integer (its Hamming weight).

Constraints. 1 <= n <= 2**31 - 11 <= n <= 2**31 - 1.

Examples. n = 11n = 11 (binary 10111011) gives 33 · n = 128n = 128 (binary 1000000010000000) gives 11 · n = 2147483645n = 2147483645 gives 3030

Editorial · approach, complexity, follow-ups

Three solutions, and the interviewer wants to hear why the second is better than the first.

Shift and test. Loop 32 times, checking n & 1n & 1 each time. Always 32 iterations.

Brian Kernighan. n & (n - 1)n & (n - 1) clears the lowest set bit. Why: n - 1n - 1 flips that lowest 1 to a 0 and all the zeros below it to 1s, so the AND keeps every higher bit and wipes everything from the lowest set bit down. The loop therefore runs once per set bit — 1 iteration for 128128, not 32.

Built-in. bin(n).count("1")bin(n).count("1"), or n.bit_count()n.bit_count() on Python 3.10 and later. Mention it, but show the trick first — the question exists to test the trick.

Time $O(\text{popcount})$ , at most 32. Space $O(1)$ .

n = 0n = 0 returns 0 and the loop body never runs. LeetCode’s constraints start at 1, but the test includes 0 because a shift-based loop with a bad terminating condition can hang or miscount there.
42949672954294967295 is 32 ones and returns 32 — the maximum. It is above LeetCode’s stated bound and included on purpose: Python integers are arbitrary precision, so nothing overflows, which is worth knowing when the same code is asked for in C.
Negative inputs are where the language matters. In Python -1-1 has infinitely many conceptual leading ones and this loop would never terminate; in C it is 32 ones and returns 32. If negatives are possible, mask with n & 0xFFFFFFFFn & 0xFFFFFFFF first.

Follow-ups you should expect: “Count bits for every number from 0 to nn (LC 338)?” — next problem, and the answer is DP, not 32 independent counts. “Hamming distance between two numbers (LC 461)?” — popcount of a ^ ba ^ b. “Is nn a power of two (LC 231)?” — n > 0 and n & (n - 1) == 0n > 0 and n & (n - 1) == 0: exactly one set bit. “Constant time, no loop?” — the SWAR bit-twiddling sequence with masks 0x555555550x55555555, 0x333333330x33333333 and so on; worth knowing that it exists. “Do it in $O(1)$ for a 64-bit word?” — that is what hardware POPCNTPOPCNT is for.

LC 338 — Counting Bits · Easy

Problem. Given nn, return an array ansans of length n + 1n + 1 where ans[i]ans[i] is the number of set bits in ii.

Constraints. 0 <= n <= 10**50 <= n <= 10**5.

Examples. n = 2n = 2 gives [0,1,1][0,1,1] · n = 5n = 5 gives [0,1,1,2,1,2][0,1,1,2,1,2]

Editorial · approach, complexity, follow-ups

The point of the problem is the linear-time solution. Calling popcount n + 1n + 1 times is $O(n \log n)$ and is what the follow-up (“can you do it in one pass, in $O(n)$ ?”) is fishing for.

Time $O(n)$ , one array write each. Space $O(n)$ for the output, which does not count as extra.

Three equivalent recurrences, all fine to present:

dp[i] = dp[i >> 1] + (i & 1)dp[i] = dp[i >> 1] + (i & 1) — strip the lowest bit. The most common form.
dp[i] = dp[i & (i - 1)] + 1dp[i] = dp[i & (i - 1)] + 1 — strip the lowest set bit, using Kernighan from the previous problem. The neatest link between the two.
dp[i] = dp[i - highest_power_of_two] + 1dp[i] = dp[i - highest_power_of_two] + 1 — strip the highest bit, tracking the current power of two as you go.
n = 0n = 0 must return [0][0], a list of length 1. The loop simply does not run.
The array has n + 1n + 1 entries, not nn. Off by one here is the usual failure.
i >> 1 < ii >> 1 < i for all i >= 1i >= 1, which is exactly the guarantee that an ascending loop respects the dependency order. That sentence is the proof of correctness.

Follow-ups you should expect: ” $O(1)$ extra space?” — impossible: the output itself is $O(n)$ . “The single value only?” — LC 191. “Count set bits in all numbers up to $10^{18}$ ?” — digit DP over bit positions, since you cannot enumerate. “Which numbers in the range have an even popcount?” — the same DP with a parity test; that sequence is the Thue-Morse sequence. “Sort by popcount (LC 1356)?” — this array as a sort key.

LC 137 — Single Number II · Medium

Problem. Every element appears three times except one, which appears once. Find that one. Use linear time and constant extra space.

Constraints. 1 <= len(nums) <= 3 * 10**41 <= len(nums) <= 3 * 10**4, values fit in a 32-bit signed integer, and exactly one element appears once.

Examples. [2,2,3,2][2,2,3,2] gives 33 · [0,1,0,1,0,1,99][0,1,0,1,0,1,99] gives 9999

Editorial · approach, complexity, follow-ups

The lesson is that XOR is addition modulo 2, so it solves the appears-twice version (LC 136) and nothing else. Threes need arithmetic modulo 3, which means two bits of state per position — and onesones/twostwos are those two bits, maintained for all 32 positions simultaneously.

The state machine each bit position runs, as the same bit value arrives:

Occurrences	`onesones` bit	`twostwos` bit
0 (mod 3)	0	0
1	1	0
2	0	1

The & ~twos& ~twos in the first line stops a bit entering onesones while it is sitting in twostwos; the & ~ones& ~ones in the second uses the freshly updated onesones, which is what makes a third occurrence clear both and return the position to 0. The order of the two lines matters — swapping them breaks it.

Time $O(n)$ . Space $O(1)$ .

The line order is load-bearing. Compute twostwos first, and the transitions no longer close the cycle at three.
Negative numbers work in Python, but for a subtle reason: integers are arbitrary precision and ~~ behaves as two’s complement, so the sign bits track correctly. [1,1,1,-2][1,1,1,-2] returning -2-2 is the check for that.
Single-element input returns it directly — onesones becomes that value on the first iteration and nothing promotes it.

The far more explainable alternative, and a perfectly good interview answer: for each of the 32 bit positions, sum that bit across all numbers and take the sum modulo 3. What remains is the answer’s bit. It is $O(32n)$ — still linear — and much easier to justify at a whiteboard. In Python you must then re-apply the sign: if bit 31 is set, subtract $2^{32}$ . Offer this version first, then the two-variable one as the optimisation.

Follow-ups you should expect: “Appears twice instead (LC 136)?” — XOR everything. “Two numbers appear once (LC 260)?” — XOR everything, then split by any set bit of the result. “Appears kk times, one appears once?” — the mod-kk bit-sum method generalises directly; the two-variable trick does not, without care. “Appears three times, one appears twice?” — bit sums modulo 3 leave a residue of 2 in those positions. “Why not a hash map?” — it works and is what you would ship; the constant-space constraint is what makes this a puzzle.

LeetCode problem set

#	Problem	Difficulty	The twist
136	Single Number	Easy	The running-XOR trick above, applied directly
137	Single Number II	Medium	Every other number appears three times; needs per-bit counting mod 3 instead of a plain XOR
191	Number of 1 Bits	Easy	`x.bit_count()x.bit_count()`, or `n & (n - 1)n & (n - 1)` in a loop to count how many times the lowest set bit can be cleared
338	Counting Bits	Easy	`dp[i] = dp[i >> 1] + (i & 1)dp[i] = dp[i >> 1] + (i & 1)`, a DP built directly on the bit-mask idioms above
78	Subsets	Medium	The bitmask subset enumeration above, applied to `numsnums` directly
421	Maximum XOR of Two Numbers in an Array	Medium	Build each number’s prefix bit-by-bit in a trie (or a running prefix-mask set) to greedily maximize the XOR, bit by bit from the top

Recap

Five operators — & | ^ ~ << >>& | ^ ~ << >> — cover check/set/clear/toggle via a shifted 1 << i1 << i mask.
x & -xx & -x isolates the lowest set bit; n & (n - 1)n & (n - 1) clears it — the basis of popcount loops and power-of-two checks.
XOR’s cancellation (x ^ x == 0x ^ x == 0) finds a lone non-duplicate in a single pass with $O(1)$ extra space.
Counting from 00 to 2^n - 12^n - 1 enumerates every subset of nn items, each one an $O(n)$ bit-check away from a real list.

Next: Advanced DP Optimizations — digit DP, monotonic-deque-optimized DP, and a tour of the classic speedups (convex hull trick, divide and conquer, Knuth) that turn an $O(n^2)$ recurrence into something faster.

If this helped you, consider buying me a coffee ☕

Buy me a coffee

Bit Manipulation Tricks

What you’ll learn

Binary representation

The five core operators

Check, set, clear, toggle: the four bit-mask idioms

Two O(1) one-liners: lowest set bit and popcount

XOR tricks: cancellation is the whole trick

Bitmask subset enumeration

Practice — real LeetCode problems

LC 191 — Number of 1 Bits · Easy

LC 338 — Counting Bits · Easy

LC 137 — Single Number II · Medium

LeetCode problem set

Recap

Was this page helpful?