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.
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
a, b = 12, 10 # 001100, 001010 a & b # AND: 1 where both are 1 -> 8 a | b # OR: 1 where either is 1 -> 14 a ^ b # XOR: 1 where they differ -> 6 a << 1 # shift left: multiply by 2 -> 24 a >> 1 # shift right: divide by 2 -> 6 a & 1 # last bit: 0, so a is even
def isPowerOfTwo(n): # LeetCode 231
return n > 0 and n & (n - 1) == 0 # n - 1 flips the lowest 1 and the 0s below it
def missingNumber(nums): # LeetCode 268
res = len(nums) # XOR all indexes 0..n ...
for i, x in enumerate(nums):
res ^= i ^ x # ... with all values: pairs cancel
return res
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".
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".
| Operation | Time | Why |
|---|---|---|
| &, |, ^, ~, <<, >> | 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) loop | O(number of 1s) | Each turn clears the lowest 1-bit, so it skips the zeros entirely. |
| XOR over a list | O(n) | One XOR per element, O(1) space: the "no extra space" answer to find-the-odd-one-out. |
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.
Read, set or count bits with masks and shifts.
XOR everything; pairs disappear.
# 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