DSA · Bit Manipulation

One integer is thirty-two switches

Q: What do people mean by bit manipulation?

Working on a number as the row of binary digits the machine actually stores, using AND, OR, XOR, NOT and the two shifts instead of arithmetic. One 32-bit int is 32 independent yes/no switches, and a single instruction can read or change any of them. It matters because problems like "find the value that appears once" collapse to one pass with no extra memory.

Q: Convert 13 to binary and back for me.

13 is 1101 , which is 00001101 in eight bits. The method is divide by 2 and keep the remainders: 13 gives 6 remainder 1, 6 gives 3 remainder 0, 3 gives 1 remainder 1, 1 gives 0 remainder 1, and you read the remainders bottom to top. Going back, add the place values of the 1s: 8 + 4 + 1 = 13. In practice you recognise 8 + 4 + 1 on sight and skip the division.

Q: What is the difference between OR and XOR?

OR gives 1 when at least one input is 1. XOR gives 1 only when the two inputs differ, so 1 ^ 1 is 0. That is why OR can only ever add 1s to a number while XOR can also take them away, and why x ^ x = 0 but x | x = x . In practice: OR sets a bit, XOR flips it.

Q: How do you check whether the i-th bit is set?

(n >> i) & 1 gives it to you as 0 or 1, and (n & (1 << i)) != 0 gives it as a boolean. Both are O(1). Keep the brackets in the second form: in C, C++ and Java & binds looser than != , so n & 1 << i != 0 does not mean what it looks like.

Q: How do you set, clear and toggle it?

n | (1 << i) sets, n & ~(1 << i) clears, n ^ (1 << i) toggles. Clear is the one that needs the complement, because you want to keep everything except position i: ~(1 << 2) is 11111011 , so ANDing preserves every other bit and forces bit 2 to 0. On 13 that gives 9.

Q: What does n & (n − 1) do?

It clears the lowest set bit. Subtracting 1 turns the lowest 1 into a 0 and every 0 below it into a 1, and leaves the bits above alone, so ANDing the two loses exactly that one bit. On 13: 13 & 12 = 12 , 12 & 11 = 8 , 8 & 7 = 0 — three rounds, because 13 has three set bits.

Q: Naive bit counting versus Brian Kernighan — what are the complexities?

The naive loop tests every position, so it is O(w): 32 rounds for a 32-bit int even when n is 1. Kernighan runs once per set bit, so it is O(popcount) — anywhere from 0 to 32 rounds. Same worst case, when every bit is set, but much cheaper on the sparse numbers you actually meet. If you treat the word width as a constant, both are O(1).

Q: How do you test whether a number is a power of two, and why the extra guard?

n > 0 && (n & (n − 1)) == 0 . A power of two has exactly one set bit, so one round of clearing the lowest 1 must empty the number. Without the guard, 0 passes because 0 & −1 is 0, and the most negative int passes too — it also has exactly one bit set.

Q: Why does XOR find the element that appears once?

Because x ^ x = 0 , x ^ 0 = x , and the order does not matter. XOR the whole array into one accumulator: every value with a partner cancels against it, and what survives is the value that had none. One pass, O(n) time, O(1) space — 13 ^ 9 ^ 13 is 9.

Q: Is n << 1 the same as n * 2?

For non-negative numbers that still fit, yes: n << k is n times 2 to the k, and n >> k is n divided by 2 to the k rounded down. Two catches. Shifting can push bits off the top and lose them silently, and rounding down is not the same as truncating: −7 >> 1 is −4 while −7 / 2 is −3. In Java, >> keeps the sign bit and >>> does not.

A number is already a row of bits, and one mask lets you read or change any single position without disturbing the rest. You will convert 13 by hand, check, set and clear its bit 2, then count set bits the way Brian Kernighan does — one round per 1, not one per position.

Flip bits on an 8-cell row and watch the decimal move →

n = 1300001101 · bit 2 is 1

→

clear bit 2n & ~(1 << 2)

→

n = 900001001 · bit 2 is 0

01 The idea

The number is already a row of switches

Your computer does not store 13 as a 1 followed by a 3. It stores a fixed row of switches — 32 of them in an int — and 13 is the pattern 00001101 in the last eight of them. Counting from the right-hand end, the positions are worth 1, 2, 4, 8, 16 and so on, and the switches that are on add up to the number: 8 + 4 + 1 = 13.

Once you can see that row, a whole family of questions stops needing a loop. Is position 2 on? Turn position 2 off. How many are on? The six operators that do this work on every position at once. AND, OR and XOR line two numbers up and compare them bit by bit, NOT flips every bit of one number, and the two shift operators slide the whole row left or right. The only thing you have to supply is a mask — a number built so that the positions you care about hold 1 and every other position holds 0.

To work on bit i, build the mask 1 << i. AND with it to read that bit, OR with it to switch the bit on, AND with its complement to switch it off, XOR with it to flip it. Nothing outside position i ever moves.

Bit and place valuePosition p is worth 2^p, counting from 0 at the right-hand end. In 13, bit 0 is 1, bit 1 is 0, bit 2 is 1 and bit 3 is 1 — and 1 + 4 + 8 is 13.

MaskA number you build so the positions you want to touch hold 1 and the rest hold 0. 1 << i is the mask with a single 1 at position i; for i = 2 it is 00000100, which is 4.

Set bitA bit that is 1. The number of set bits is the population count, or popcount. 13 has three set bits, so its popcount is 3 — a number you will use twice in this lesson.

02 Worked example

Check, set and clear bit 2 of 13

One number, n = 13, and one position, bit 2. Each row below is the same eight cells; the labels on the left say which number the row is showing. Read the cells right to left, because bit 0 sits at the right-hand end. Only the sixth cell from the left — position 2 — is ever in play.

bit index76543210

n = 13000011018 + 4 + 1 = 13

mask 1<<200000100one 1 at position 2 = 4

n & mask00000100= 4, not 0 · bit 2 is 1

n | mask00001101= 13 · it was already 1

~mask11111011= 251 · all but bit 2

n & ~mask00001001= 9 · bit 2 cleared

Toggle would have landed on 9 as well: 13 ^ 4 flips bit 2 from 1 to 0. When the bit is already 1, toggle agrees with clear; when it is 0, toggle agrees with set. Toggle is the only one of the three you can undo by repeating it — 9 ^ 4 is 13 again.

One mask did all three jobs, and the operator you paired it with decided what happened. AND read the position, OR forced it on, AND with the complement forced it off. Nothing else in the number moved: 13 and 9 differ in exactly one bit, and the decimal changed by exactly 4 — the place value of bit 2. That is the invariant the four one-liners below are built to protect.

03 The code

Four one-liners, one mask

Start with the tables the one-liners rest on, then read the four masks side by side. Only one of the four changes shape, and that is clear, which needs the complement.

Truth tables, one bit at a time

These operators do not treat the number as a whole. They line the two numbers up and apply the table below to each of the 32 positions independently.

a	b	a & b (AND)	a \| b (OR)	a ^ b (XOR)	~a (NOT)
0	0	0	0	0	1
0	1	0	1	1	1
1	0	0	1	1	0
1	1	1	1	0	0

Read them as sentences. AND gives 1 only when both inputs are 1, so it keeps a bit and drops everything else. OR gives 1 when at least one is 1, so it can only add 1s. XOR gives 1 only when the two inputs differ, which is why 1 ^ 1 is 0 and why XOR is the only one of the three that can remove a 1. NOT takes one input and flips every position of it.

Shifting slides the whole row

Expression	Binary	Decimal	What happened
13 << 1	00011010	26	Every bit moved one place left, a 0 slid in at the right. That is ×2.
13 << 2	00110100	52	Two places left. That is ×4.
13 >> 1	00000110	6	One place right; the 1 that was in bit 0 falls off the end. 13 ÷ 2 rounded down.
13 >> 2	00000011	3	Two places right, two bits lost. 13 ÷ 4 rounded down.
1 << 2	00000100	4	A lone 1 walked up to position 2. This is the mask.

The four one-liners, with mask = 1 << i

Goal	One-liner	Mask in binary, i = 2	On n = 13
Read bit i	(n & mask) != 0	00000100	13 & 4 = 4, so the bit is 1
Switch bit i on	n \| mask	00000100	13 \| 4 = 13, no change
Switch bit i off	n & ~mask	11111011	13 & 251 = 9
Flip bit i	n ^ mask	00000100	13 ^ 4 = 9

Why clear is the odd one out. The other three want to act on position i, and a mask with a single 1 there is enough. Clear wants to preserve everything except position i, so its mask has to be 1 everywhere else — that is exactly ~mask, 11111011. AND then copies every other bit through untouched and forces bit 2 to 0. One caveat on the numbers: across eight cells ~mask reads 11111011 = 251, but in a real 32-bit int the 1s keep going up to bit 31, so ~(1 << 2) is −5, not 251. It makes no difference to the result — 13 & 251 and 13 & −5 are both 9 — which is why the eight cells are safe to reason in.

Counting the set bits

Now the same shifts and masks, put to work on a real question: how many 1s does n have? The version on the left asks about every position. The version on the right asks once per answer.

Naive — test every position

count = 0for p in 0 .. 31:    count = count + ((n >> p) & 1)return count   # 32 rounds, every time

Brian Kernighan — clear the lowest 1

count = 0while n != 0:    n = n & (n − 1)   # kill the lowest 1    count = count + 1return count   # one round per set bit

Why n & (n − 1) removes exactly one bit. Subtracting 1 turns the lowest 1 into a 0 and turns every 0 below it into a 1; the bits above it are untouched. ANDing the before and the after therefore keeps every high bit, kills that lowest 1, and kills the borrowed 1s underneath it. On 13: 13 & 12 = 12, 12 & 11 = 8, 8 & 7 = 0 — three rounds, and 13 has three set bits.

Why the naive version cannot catch up. It asks a question about every position, so it costs 32 rounds whether n is 4294967295 or 1. Kernighan's loop asks a question per answer instead of per position, so it costs popcount(n) rounds. The worst case is the same — all 32 bits set — but on the sparse numbers you actually meet it is far cheaper.

The same trick tests a power of two. A power of two has exactly one set bit, so one round of clearing must empty it: n > 0 && (n & (n − 1)) == 0. Keep the guard. 0 has no bits at all and 0 & −1 is 0, and the most negative int has a single set bit too, so both would slip through without it. On our number, 13 & 12 = 12, which is not 0, so 13 is not a power of two.

Three XOR facts worth memorising: x ^ x = 0, x ^ 0 = x, and the order you XOR things in does not matter. Fold a whole array together with XOR and every value that appears twice cancels itself out, leaving the one that appears once. 13 ^ 9 ^ 13 is 9.

05 Cheat sheet

The lines worth knowing cold

Task	One-liner	Cost	On n = 13
Read bit i	(n >> i) & 1	`O(1)`	bit 2 → 1
Set bit i	n \| (1 << i)	`O(1)`	13 \| 4 = 13
Clear bit i	n & ~(1 << i)	`O(1)`	13 & 251 = 9
Toggle bit i	n ^ (1 << i)	`O(1)`	13 ^ 4 = 9
Clear the lowest 1	n & (n − 1)	`O(1)`	13 → 12
Isolate the lowest 1	n & −n	`O(1)`	13 & −13 = 1
Count set bits, every position	for p in 0..31	`O(w) = 32`	32 rounds
Count set bits, Kernighan	while n: n &= n − 1	`O(popcount)`	3 rounds
Power of two?	n > 0 && (n & (n − 1)) == 0	`O(1)`	false, 13 & 12 = 12
Multiply or divide by 2^k	n << k · n >> k	`O(1)`	26 and 6 for k = 1
Decimal to binary by hand	divide by 2, keep remainders	`O(log n)`	1, 0, 1, 1 → read up → 1101

Two's complementNegatives are not stored with a minus sign. ~n is −n − 1, so ~13 is −14, and −n is ~n + 1. Every trick involving a negative number rests on this.

Precedence trapIn C, C++ and Java, & binds looser than == and !=. So n & mask != 0 parses as n & (mask != 0). Bracket the AND, always.

Shifting is not dividing>> rounds towards minus infinity, integer division rounds towards zero: −7 >> 1 is −4 but −7 / 2 is −3. In Java, >> keeps the sign and >>> does not.

06 Where & why

Not faster arithmetic — a different data structure

Bit tricks are not a speed-up for maths. Every compiler already turns x * 2 into a shift, so writing x << 1 yourself buys nothing but a harder line to read. What bit manipulation actually gives you is one integer standing in for a whole set, and an operator that remembers pairs for free.

Reach for it when…

The universe is small and fixedUp to about 20 items, so a subset fits in one integer. Bitmask DP over subsets — travelling salesman, assignment, "visit every city once" — is only possible because a subset is an integer you can use as an array index.

You are packing flagsPermission bits, feature flags, a chess board, a protocol header. One integer replaces a whole boolean array, compares in one instruction, and travels over the wire as four bytes.

Elements pair up and one does notThe appears-once family. XOR folds the array into a single accumulator in O(n) time and O(1) space, where a hash map would need O(n) memory.

Memory is the real constraintA bitset holds a million booleans in 125 KB instead of a million bytes. That is what makes a large sieve of Eratosthenes and a Bloom filter fit in cache.

Use something else when…

Situation	Better choice	Why
The keys are arbitrary, or the set can grow	Hash set — HashSet, unordered_set, set()	An int mask caps you at 32 members and a long at 64. It cannot hold ids in the thousands at all.
You are writing x << 1 for speed	*Plain x 2**	The compiler emits the same instruction either way. You pay in readability and gain `O(1)` versus `O(1)`.
You need a popcount in production code	Integer.bitCount, __builtin_popcount, int.bit_count()	One CPU instruction beats an `O(popcount)` loop, and it is already tested. Write Kernighan in the interview, call the builtin at work.
Order or ranges matter — kth smallest, "at least x"	Sorted array with binary search, or a tree set	A mask has no order. Finding the kth member means walking all `O(w)` positions, and there is no range query at all.

Interviews ask for these because they test whether you can see a number as its bits, not whether you can recall syntax. Learn the four one-liners, n & (n − 1) and the XOR cancellation, and be honest in the round that real code calls the builtin popcount — that answer scores better than pretending otherwise.

07 Interview questions

Twelve you should be able to answer cold

In the order an interview escalates: what the bits are and what the operators do, then the four one-liners, then n & (n − 1) with the two counting methods and the power-of-two test, and finally XOR, shifting, the lowest set bit, and what you would actually ship.

What do people mean by bit manipulation?

Working on a number as the row of binary digits the machine actually stores, using AND, OR, XOR, NOT and the two shifts instead of arithmetic. One 32-bit int is 32 independent yes/no switches, and a single instruction can read or change any of them. It matters because problems like "find the value that appears once" collapse to one pass with no extra memory.

Convert 13 to binary and back for me.

13 is 1101, which is 00001101 in eight bits. The method is divide by 2 and keep the remainders: 13 gives 6 remainder 1, 6 gives 3 remainder 0, 3 gives 1 remainder 1, 1 gives 0 remainder 1, and you read the remainders bottom to top. Going back, add the place values of the 1s: 8 + 4 + 1 = 13. In practice you recognise 8 + 4 + 1 on sight and skip the division.

What is the difference between OR and XOR?

OR gives 1 when at least one input is 1. XOR gives 1 only when the two inputs differ, so 1 ^ 1 is 0. That is why OR can only ever add 1s to a number while XOR can also take them away, and why x ^ x = 0 but x | x = x. In practice: OR sets a bit, XOR flips it.

How do you check whether the i-th bit is set?

(n >> i) & 1 gives it to you as 0 or 1, and (n & (1 << i)) != 0 gives it as a boolean. Both are O(1). Keep the brackets in the second form: in C, C++ and Java & binds looser than !=, so n & 1 << i != 0 does not mean what it looks like.

How do you set, clear and toggle it?

n | (1 << i) sets, n & ~(1 << i) clears, n ^ (1 << i) toggles. Clear is the one that needs the complement, because you want to keep everything except position i: ~(1 << 2) is 11111011, so ANDing preserves every other bit and forces bit 2 to 0. On 13 that gives 9.

What does n & (n − 1) do?

It clears the lowest set bit. Subtracting 1 turns the lowest 1 into a 0 and every 0 below it into a 1, and leaves the bits above alone, so ANDing the two loses exactly that one bit. On 13: 13 & 12 = 12, 12 & 11 = 8, 8 & 7 = 0 — three rounds, because 13 has three set bits.

Naive bit counting versus Brian Kernighan — what are the complexities?

The naive loop tests every position, so it is O(w): 32 rounds for a 32-bit int even when n is 1. Kernighan runs once per set bit, so it is O(popcount) — anywhere from 0 to 32 rounds. Same worst case, when every bit is set, but much cheaper on the sparse numbers you actually meet. If you treat the word width as a constant, both are O(1).

How do you test whether a number is a power of two, and why the extra guard?

n > 0 && (n & (n − 1)) == 0. A power of two has exactly one set bit, so one round of clearing the lowest 1 must empty the number. Without the guard, 0 passes because 0 & −1 is 0, and the most negative int passes too — it also has exactly one bit set.

Why does XOR find the element that appears once?

Because x ^ x = 0, x ^ 0 = x, and the order does not matter. XOR the whole array into one accumulator: every value with a partner cancels against it, and what survives is the value that had none. One pass, O(n) time, O(1) space — 13 ^ 9 ^ 13 is 9.

Is n << 1 the same as n * 2?

For non-negative numbers that still fit, yes: n << k is n times 2 to the k, and n >> k is n divided by 2 to the k rounded down. Two catches. Shifting can push bits off the top and lose them silently, and rounding down is not the same as truncating: −7 >> 1 is −4 while −7 / 2 is −3. In Java, >> keeps the sign bit and >>> does not.

What does n & −n give you?

Hard

Every value in an array appears twice except two distinct values, which appear once each. Return both, in O(n) time and O(1) extra space.

Follow-up

XORing everything gives you x ^ y, which is neither answer. The two loners must differ in at least one bit, and that single bit splits the whole array into two groups, each holding exactly one of them.

Show the hint

Take d = x ^ y, isolate one of its set bits with d & −d, then XOR the array into two accumulators depending on whether each value has that bit.