Bit Manipulation

Question 1

Which property of XOR allows finding a unique number in pairs?

Accepted Answer

A ^ A = 0 — Since A ^ A = 0, all pairs cancel each other out, leaving only the unique number XORed with 0.

Question 2

To CHECK whether bit i of integer n is set, you compute…

Accepted Answer

n & (1 << i) — n & (1<<i) is nonzero iff bit i is 1. Setting uses |, clearing uses & ~(1<<i), toggling uses ^.

Question 3

What is the result of x ^ x (XOR of a value with itself)?

Accepted Answer

0 — XOR of identical bits is 0, so x ^ x = 0. Also x ^ 0 = x — these two identities power many bit tricks.

Question 4

In an array where every element appears twice except one, the UNIQUE element is found by…

Accepted Answer

By combining all array elements with exclusive-or — Because a^a=0 and XOR is associative/commutative, all duplicates cancel and the lone element remains — O(n) time, O(1) space.

Question 5

The expression n & (n − 1) does what?

Accepted Answer

It clears the lowest set bit of n — Subtracting 1 flips the lowest set bit and the zeros below it; AND-ing clears that lowest set bit — the basis of Brian Kernighan's bit-counting.

Question 6

How can you test whether n is a power of two (n > 0)?

Accepted Answer

Checking if (n & (n − 1)) equals 0, leaving no set bits — A power of two has exactly one set bit; clearing it yields 0, so (n & (n−1)) == 0 (for n > 0) identifies powers of two.

Question 7

Brian Kernighan's algorithm counts set bits in time proportional to…

Accepted Answer

Only the number of set bits — Repeatedly doing n &= (n−1) removes one set bit per step, so it loops once per set bit — faster than scanning all bit positions when few are set.

Question 8

Left-shifting an integer by 1 (n << 1) is equivalent to…

Accepted Answer

Multiplying the value by 2 — Each left shift moves bits to higher places, doubling the value (n << k = n × 2ᵏ). Right shift (n >> k) is integer division by 2ᵏ.

Question 9

To isolate the LOWEST set bit of n, you compute…

Accepted Answer

n & (−n) — n & (−n) yields a value with only the lowest set bit of n (using two's-complement negation) — the same 'lowbit' used in Fenwick trees.

Question 10

Swapping two integers WITHOUT a temporary can be done with…

Accepted Answer

Three XORs: a^=b, b^=a, a^=b — The XOR swap uses a^a=0 to exchange values in place — clever but rarely faster than a temp, and it fails if a and b alias the same variable.

Bit Manipulation

Which operator?

Test your knowledge

Which property of XOR allows finding a unique number in pairs?

Write the code

Single Number

Example Cases

The short version

In more depth

Bitwise Power

When to reach for this

Interview Questions

References & Further Reading

Love this visualization?