Bit Manipulation

Explore bit manipulation interview problems: XOR tricks, counting and reversing bits, and adding without plus, with every bit shown step by step.

The pattern

Bit Manipulation: work on the binary digits directly

Integers are rows of bits, and a few operations act on all of them at once: AND, OR, XOR, NOT and shifts. A handful of identities (x ^ x = 0, n & (n − 1), carries as (a & b) << 1) turn into one-line solutions with O(1) memory.

50101^ 50101= 00000a number XOR itself is 0

1XOR cancels pairs

x ^ x = 0 and x ^ 0 = x, in any order. XOR a list where everything appears twice except one number, and only that number survives.

n = 121100n − 11011& = 81000the lowest 1 (amber) is gone

2n & (n − 1) clears the lowest 1

Subtracting 1 flips the lowest 1 bit and every 0 below it. ANDing with the original keeps everything else. Repeat it to count or visit the 1 bits.

a = 30011b = 10001a ^ b0010carry0010repeat: 2 + 2 → 4

3Add with XOR and carries

a ^ b is the column sum ignoring carries; (a & b) << 1 is the carries, shifted into the next column. Keep adding those two until there's no carry.

Tricks worth knowing

  • x ^ x = 0: find the odd one out; compare two sets in O(1) memory.
  • n & (n − 1): clear the lowest set bit; n is a power of two if the result is 0.
  • (n >> i) & 1 reads bit i; res | (1 << i) sets it.
  • Python's integers have no fixed width: mask with 0xffffffff when 32-bit behaviour matters.

Reading the pictures

  • Small numbers are shown as 8 bits, with each bit's position under it. Blue cells are 1s.
  • 32-bit values are a 4 × 8 grid: the first row is bits 31–24, the last row bits 7–0.
  • Teal marks the bit being changed now; amber marks carries.

NeetCode 150 · Bit Manipulation

All 7 problems

Pick a problem to see it solved step by step. They're in NeetCode's order, roughly easiest first.

Single Number

Easy

Every number appears twice except one. Find that one, in linear time and constant extra space.

NeetCode's video solution Try it on LeetCode
Input

nums = [4, 1, 2, 1, 2]

nums

4
1
2
1
2

res (XOR so far)

0
7
0
6
0
5
0
4
0
3
0
2
0
1
0
0

variables

res
0

Press Play or Step to watch the solution run.

Step 0 / 7
900 ms

Brute force vs the pattern

On this input:

Pattern: O(n)
5 ops
Brute force
5 ops

On a bigger input (201 numbers):

Pattern
201 ops
Brute force
40,401 ops

For each number, count how many times it appears by scanning the whole list: O(n²). (A hash map is O(n) but uses O(n) memory.)

“ops” is an illustrative count of selected algorithm operations, with estimates for sorting. It excludes drawing and frame creation and is not a timing benchmark. The complexity describes the Python solution. On small inputs a brute-force search may find the answer sooner.

How it works: Single Number

Step by step

  • Number being XOR-ed
  • A 1 bit

Press Start or Step: the step the animation is on lights up below.

  1. 1

    res = 0

    res = 0
  2. 2

    XOR in the next number

    for n in nums: res = n ^ res
  3. 3

    The single one

    return res

x ^ x = 0, x ^ 0 = x, and XOR is commutative and associative. XOR everything: each pair cancels to 0, and 0 ^ single = single.

One pass, one variable: O(n) time and O(1) memory.

Spot it in an interview

  • “Every element appears twice except …”: XOR.
  • Cancelling pairs without storing them.
time O(n)space O(1)

One pass, one integer.

Credits

Learn more from NeetCode

The problem list and order come from the NeetCode 150 by NeetCode (neetcode.io). The solutions here follow the approaches NeetCode teaches in the linked videos; the animations, explanations and code were written for CodeQuest. If these help, NeetCode's videos and site are well worth your time.

Problem statements are summarised in our own words; the full versions are on LeetCode.