We use necessary cookies to run the site (sign-in and language). If you accept, we also load Google Analytics to see which pages are used, and Google reCAPTCHA to keep spam off the contact and bug-report forms. Privacy policy

← Blog
How to prepare

Bit manipulation: the table, eight tricks to memorise and Python code

· 2026-11-18

Short answer. Bit manipulation treats a number as a row of zeros and ones. Six operations: and, or, xor, not, shift left, shift right. With them, "find the single number" and "count the ones" run in O(1) or O(log n). No extra memory. Below: the table, eight tricks worth memorising, Python code and the mistakes.

What is bit manipulation?

The number 13 in binary is 1101. Each position is a bit, zero or one. Bit manipulation changes or checks those positions directly.

And keeps a one where both have one. Or sets a one where either has one. Xor sets a one where the bits differ.

Shift left by k multiplies by 2 to the k. Shift right divides, rounding down.

Finding the number without a pair with XOR
findUnique([5, 3, 5, 6, 3])
nums
5
3
5
6
3
bits (column = what the bit is worth)
8421
acc0000
acc = 0

Every number appears twice except one. acc starts at 0, and a XOR b flips the bits of a wherever b has a 1.

Speed race
Counting the set bits of the same 32-bit number: test all 32, or clear one set bit per step

Bars: the 32 bits of the number, highest on the left, a tall bar for 1. Checking every bit only reads them; Kernighan's trick clears each 1 it counts, so its bars end at zero.

One operation is one step of the loop: one bit tested or one bit cleared. Every frame, each lane does the same number of operations, so the slow one falls behind.

Check every bit O(n)
0 operations
Kernighan's trick O(k)
0 operations

 

And with more numbers

Operations for n numbers, and roughly how long they take at 100 million simple operations a second. An estimate from the same count, not a measurement.

n = 1,000
Check every bit1K · under 1 ms
Kernighan's trick250 · under 1 ms
n = 100,000
Check every bit100K · 1 ms
Kernighan's trick25K · under 1 ms
n = 10,000,000
Check every bit10M · 100 ms
Kernighan's trick2.5M · 25 ms

The pattern page: when to use it, and a template in six languages

Which bit operations does Python have?

OperationSyntaxExampleMeaning
Anda & b12 & 10 = 81100 & 1010 = 1000
Ora | b12 | 10 = 141100 | 1010 = 1110
Xora ^ b12 ^ 10 = 61100 ^ 1010 = 0110
Not~a~12 = -13In Python it is -a - 1
Shift lefta << k3 << 2 = 12Multiply by 4
Shift righta >> k12 >> 2 = 3Divide by 4

Which bit manipulation tricks should you know by heart?

  • x & 1 gives the last bit: parity.
  • x & (x - 1) clears the lowest set bit.
  • x & (x - 1) == 0, with x positive, means a power of two.
  • x & -x isolates the lowest set bit.
  • x ^ x = 0 and x ^ 0 = x: pairs cancel.
  • 1 << i is the mask for bit i. Test with x & (1 << i).
  • x | (1 << i) sets bit i. x & ~(1 << i) clears it.
  • Subsets of n items are the numbers from 0 to 2ⁿ - 1.

The last trick is called a bitmask. It replaces a list of boolean flags with one integer.

When does a problem need bit manipulation?

  • "Every number appears twice except one."
  • "Count the ones in the binary form", "Hamming weight".
  • "Without using the plus sign", "without extra memory".
  • "All subsets" with n under 20, "a state made of flags".

What does one example look like?

Array [4, 1, 2, 1, 2]. Find the number that appears once. Xor everything: 4 ^ 1 ^ 2 ^ 1 ^ 2. The pairs 1 ^ 1 and 2 ^ 2 give 0. What remains is 4.

Count the ones in 13 = 1101. Step 1: 13 & 12 = 12 = 1100. Step 2: 12 & 11 = 8 = 1000. Step 3: 8 & 7 = 0. Three steps, three ones.

How do you write the bit tricks in Python?

def single_number(nums):
    result = 0
    for x in nums:
        result ^= x                 # pairs cancel
    return result

def count_ones(x):
    count = 0
    while x:
        x &= x - 1                  # clear the lowest set bit
        count += 1
    return count                    # or bin(x).count("1")

def is_power_of_two(x):
    return x > 0 and x & (x - 1) == 0

def subsets(nums):
    n = len(nums)
    out = []
    for mask in range(1 << n):      # each mask is one subset
        out.append([nums[i] for i in range(n) if mask >> i & 1])
    return out

def add(a, b):                      # addition without plus, 32 bits
    mask = 0xFFFFFFFF
    while b:
        a, b = (a ^ b) & mask, ((a & b) << 1) & mask
    return a if a < 0x80000000 else ~(a ^ mask)

The add function shows why the mask exists. Python integers have no fixed width, so negative numbers need manual trimming.

How do you solve Single Number II?

Every number appears three times except one. Xor no longer helps. For each of the 32 bits, count the numbers that have it set. The count modulo 3 gives that bit of the answer. Time O(32 · n), memory O(1).

How do you enumerate subsets with a bitmask?

A set of n items. A number from 0 to 2ⁿ - 1 encodes a subset. Bit i set means item i taken. A loop over all numbers visits every subset. It is shorter than backtracking and works well for DP over masks.

What mistakes break bit manipulation?

  • Precedence: x & 1 == 0 parses as x & (1 == 0). Use brackets.
  • Forgetting that ~x in Python is -x - 1, not a 32-bit flip.
  • Shifting a negative number right and expecting C behaviour.
  • Counting ones through a string inside a loop over a million numbers.

How do you explain bit manipulation in an interview?

Name the operation and its property in one sentence. "Xor cancels pairs, so the single one remains." That is enough.

Then show the binary form on a small number. The interviewer sees you are not just reciting a trick.

Drill this pattern on the bit manipulation page. The whole map of patterns lives in LeetCode patterns.

FAQ

How do you swap two variables without a third?

a ^= b, b ^= a, a ^= b. It works, but in Python a, b = b, a is simpler. Interviews ask it to test your grasp of xor.

What is Gray code?

A sequence where neighbours differ in one bit. The formula is i ^ (i >> 1). It appears in the Gray Code problem.

How do you find two single numbers among pairs?

Xor everything to get a ^ b. Isolate any set bit with x & -x. Split the numbers by that bit into two groups. Xor each group.

Where does bit manipulation show up in real systems?

File permissions, where each bit is one right. Network masks. Compiler flags, and graphics where a colour is packed into one integer.