Bit Manipulation

No. 17 · SVG · Light switchesAND · OR · XOR · shifts · counting bits

Drag across the switches. Click it, then use ← → to step and Space to play.

Every integer is a row of binary digits, each a power of two. Bit tricks work on that row directly: & (AND), | (OR), ^ (XOR) and the shifts << and >> act on every column at once, so each is a single O(1) machine step. The star is XOR: equal bits give 0, so x ^ x == 0 and x ^ 0 == x, which means XORing a list cancels every pair.

FIG. 17 · Each row is one number drawn as switches: inked tiles are 1, blank tiles are 0, and the place value of each column is printed above it. The decimal value is on the right. Red marks the bits being read or surviving an operation. Dashed red marks two 1s in the same column: under XOR they cancel, and under AND they are the bits that collide.

Step 1 / 1
READY
Slides
Extra space
Window
Result
Codecount_ones
def count_ones(n):                 # Number of 1 Bits
    count = 0
    while n:
        count += n & 1
        n >>= 1
    return count

Examples

Bit trick · LeetCode 231

A power of two has exactly one 1-bit. n − 1 turns that bit off and every bit below it on, so n & (n − 1) is 0 exactly for powers of two. Runs on 16 (True) and 12 (False). Trigger: "power of two".

O(1) timeO(1) spaceone subtraction and one AND, no loop
XOR · LeetCode 268

nums = [3, 0, 1] holds 0..3 with one missing. XOR every index and every value: each present number appears twice and cancels, the missing one appears once. Answer: 2. Trigger: "no extra space".

O(n) timeO(1) spacea hash set would need O(n) memory

Time and space

OperationTimeWhy
&, |, ^, ~, <<, >>O(1)One machine instruction on all bits in parallel.
Counting bits (shift loop)O(bits)One turn per bit up to the highest 1: at most 32 for a 32-bit int.
n & (n − 1) loopO(number of 1s)Each turn clears the lowest 1-bit, so it skips the zeros entirely.
XOR over a listO(n)One XOR per element, O(1) space: the "no extra space" answer to find-the-odd-one-out.

Cheat sheet

n & 1 last bit (odd?) · n >> 1 divide by 2 · n << 1 multiply by 2 · a ^ b 1 where bits differ · n & (n − 1) clears the lowest 1-bit · n & -n keeps only the lowest 1-bit · (n >> i) & 1 reads bit i · n | (1 << i) sets bit i.

Trigger words: when the problem wants bit tricks

Bits directly

  • binary
  • bits
  • power of two

Read, set or count bits with masks and shifts.

XOR cancelling

  • every number appears twice except one
  • no extra space

XOR everything; pairs disappear.

Template

# n & 1   last bit (1 if odd)      n >> 1   divide by 2
# a ^ b   XOR (same bits -> 0)     n << 1   multiply by 2

def count_ones(n):                 # Number of 1 Bits
    count = 0
    while n:
        count += n & 1
        n >>= 1
    return count

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