Bit Manipulation

Working on the binary digits of integers with AND, OR, XOR, NOT and shifts: single-bit recipes, XOR cancellation, bit counting and bitmask subsets.

Overview

Bit manipulation means working on the binary digits (bits) of an integer directly, with the bitwise operators. It tests whether you can think in binary: a handful of identities turn problems that look like they need a hash map or extra memory into O(1) space loops.

Bits are numbered from the right, starting at 0. Bit i is worth 2 to the power i, so 22 is 10110: bits 1, 2 and 4 are set (2 + 4 + 16).

The six operators

Each operator works on every bit position independently, except the shifts, which move bits.

AND & — 1 only if both are 1 — 5 & 3 = 101 and 011 — 001 = 1
OR \ — 1 if either is 1 — 5 \ — 3 — 111 = 7
XOR ^ — 1 if the bits differ — 5 ^ 3 — 110 = 6
NOT ~ — flips every bit — ~5 — -6, since ~x = -(x+1)
Left shift > — moves bits right — 20 >> 2 — 101 = 5

A left shift by n multiplies by 2 to the power n, and a right shift by n is floor division by 2 to the power n. Because it floors, -7 >> 1 is -4, not -3.

Recipes for one bit

Almost every problem is built from these. The examples use n = 22 (10110).

Is bit i set? — (n >> i) & 1 — i = 2 gives 1
Set bit i — n \ — (1 0 and n & (n - 1) == 0 — False

Why n & (n - 1) works: subtracting 1 turns the lowest 1 into 0 and every 0 below it into 1. The AND then keeps only the bits above, so exactly the lowest set bit disappears. A power of two has one set bit, so it becomes 0. Zero must be excluded by hand, because 0 & -1 is also 0.

XOR cancels pairs

XOR has three properties that make pairs vanish: a ^ a = 0, a ^ 0 = a, and the order does not matter. XOR every number together, and each value that appears twice cancels itself out.

Here is the trace for Single Number on [4, 1, 2, 1, 2], one row per number.

start — 000 — 0
1 — 4 — 100 — 4
2 — 1 — 101 — 5
3 — 2 — 111 — 7
4 — 1 — 110 — 6
5 — 2 — 100 — 4

The answer is 4, found in O(n) time and O(1) space. The same idea finds the missing number in 0 to n: XOR all the indices and all the values, and every present number cancels.

Two unique numbers: split by one bit

When two numbers x and y appear once and the rest twice, XOR of everything gives x ^ y. It is not zero, because x and y differ, so it has at least one set bit. Pick the lowest one with d & -d. That bit is set in exactly one of x and y, so it splits the array into two groups that each hold one unique number.

On [1, 2, 1, 3, 2, 5]: d = 3 ^ 5 = 6 (110), the lowest set bit is 2 (010). Group 1 is 2, 3, 2, which XORs to 3. Group 2 is 1, 1, 5, which XORs to 5.

Counting set bits

Brian Kernighan's method clears the lowest set bit until the number is 0, so the loop runs once per set bit rather than once per bit position. Kernighan and Ritchie gave it as an exercise in The C Programming Language (1988); Peter Wegner published it in 1960.

1 — 1100 (12) — 1011 — 1000 (8) — 1
2 — 1000 (8) — 0111 — 0000 (0) — 2

Python 3.10 added int.bit_count(), which returns the same count for non-negative numbers, and the absolute value's count for negative ones.

Bitmasks as sets

An integer of n bits can stand for a subset of n items: bit i set means item i is in. Counting from 0 to 2 to the power n, minus 1, visits every subset once. This is also how bitmask dynamic programming stores 'which items are used so far' in one integer.

0 — 000 — empty
1 — 001 — a
2 — 010 — b
3 — 011 — a, b
4 — 100 — c
5 — 101 — a, c
6 — 110 — b, c
7 — 111 — a, b, c

Listing all subsets this way costs O(n × 2^n) time.

Adding without +

XOR adds two numbers bit by bit but drops the carries. AND finds where both bits are 1, which is where a carry starts, and a left shift moves each carry to the next position. Repeat until there is no carry.

start — 101 (5) — 011 (3)
1 — 110 (6) — 010 (2)
2 — 100 (4) — 100 (4)
3 — 000 (0) — 1000 (8)
4 — 1000 (8) — 0

Python integers have no fixed width, so the Python version masks every step to 32 bits and converts the result back to a signed value at the end.

Negative numbers and language differences

Java and Python both treat negative integers as two's complement: -x equals ~x + 1. The details differ between Python and Java, and they are worth knowing.

Integer width — unbounded; acts as if it had infinite sign bits — int 32 bits, long 64 bits
>> on a negative number — floor division by 2^n (-8 >> 1 is -4) — copies the sign bit (-8 >> 1 is -4)
Shift that fills with zeros — none; mask first, e.g. n & 0xFFFFFFFF — >>> (-8 >>> 28 is 15)
Shift distance of 32 on an int — 1 << 32 is 4294967296 — only the low 5 bits count: 1 << 32 is 1
Negative shift distance — raises ValueError — masked to 0 through 31 like any other
Precedence of & and == — & binds tighter — == binds tighter: write (n & 1) == 1

This prints -4, 15, -2147483648, 1, 4294967296 and true. Note that 1 << 31 is already negative in Java; use 1L when you need bit 31 or higher.

One trap is the same in both languages: shifts bind looser than + and -, so 1 << n - 1 means 1 << (n - 1).

What you will be able to do

Read and write the check, set, clear and toggle recipes without thinking.
Explain why n & (n - 1) clears the lowest set bit, and use it to count bits and test powers of two.
Solve the Single Number family with XOR in O(1) space.
Enumerate subsets with a bitmask and describe bitmask DP state.
Handle negative numbers correctly in Python and in Java.

When to use it

Every value appears twice except one or two: XOR them
A missing number in a range: XOR indices with values
Testing for a power of two, or counting set bits
Listing all subsets of a small set (n up to about 20)
Storing a set of small integers or flags in one integer (bitmask DP)
Adding or combining numbers without arithmetic operators
Every value appears three times except one: count bits modulo 3
Comparing numbers bit by bit (Hamming distance, Gray code)

More Coding & DSA topics

Start free on Cariara · Coding problems · System design studio