156
n
Integers are bit vectors. A handful of identities — XOR cancels equal pairs, AND masks and tests, n & (n-1) erases the lowest set bit — collapse problems that look hard into a single tight loop with O(1) extra space and O(32) time.
Stop seeing an integer as a number and start seeing it as a fixed-width row of switches you flip in parallel — one bitwise instruction does to all 32 columns at once what a loop would do one element at a time.
An intis really a row of 32 light switches. The bitwise operators don't do arithmetic — they flip every switch simultaneously according to a fixed rule. Each operator has exactly one job, and once you assign it that job you stop thinking about magnitude entirely:
& AND = keep / test — a column survives only if both inputs are on. Mask with it.| OR = turn on — force columns on.^ XOR = controlled toggle— a column flips wherever the other input is on, and stays put where it's off.<< / >> = slide the whole row left or right.Two facts carry half of all bit problems: a ^ a === 0 (anything XORed with itself vanishes) and a ^ 0 === a (XOR with nothing is a no-op). Because XOR is commutative and associative, you can throw a whole list at it in any order — everything that appears an even number of times annihilates, and only the odd-one-out is left standing.
Watch a column of values cancel down to the lone survivor:
nums = [ 4, 1, 2, 1, 2 ] one number is unpaired.
stack them as bit rows and XOR straight down each column:
4 : 1 0 0
1 : 0 0 1
2 : 0 1 0
1 : 0 0 1
2 : 0 1 0
------- XOR each column (1s cancel in pairs)
xor: 1 0 0 = 4 ◄ the only value without a twin
The 1s, 2s each appear an even number of times → they pair off to 0.
4 has no partner, so its bits are the only ones left standing.O(1) space and never overflows. Missing Number is the same idea: XOR the indices 0..n against the values so each present number cancels its index, and the gap is what remains.Subtracting 1 from n flips its lowest set bit to 0 and turns every 0 below it into a 1 (borrow propagation). AND that against the original and only the lowest 1 disappears — every higher bit is untouched:
n = 0 1 0 1 1 0 0 (88)
n - 1 = 0 1 0 1 0 1 1 ◄ lowest 1 became 0, the 0s under it became 1
--------------- AND them together:
n &(n-1) = 0 1 0 1 0 0 0 (80) ◄ exactly the lowest 1 got snipped
Each AND-with-(n-1) deletes ONE set bit. Loop until n hits 0 and you
have looped once per 1-bit — that count IS the popcount.So a loop of n &= n - 1 deletes set bits one at a time and runs exactly popcount iterations, not 32. Building a result the other direction — pulling one bit off and shifting it into a bucket — is the same idea in reverse:
reverse the low 4 bits of n = 1 0 1 1 step pull n&1 result so far (shift left, OR the bit in) ---- -------- --------------------------------------- 0 1 0 0 0 1 1 1 0 0 1 1 2 0 0 1 1 0 3 1 1 1 0 1 ◄ bits emerged in reverse order result = (result << 1) | (n & 1); n >>>= 1; repeat. Reading n low→high while writing result high→low reverses it.
n, so n > 0 && (n & (n - 1)) === 0.Faced with a bit problem, don't reach for a 32-iteration loop reflexively. Ask what the problem is really doing to the bits, in this order:
XOReverything. Single Number, Missing Number, and “find the duplicate by parity” all collapse to one accumulator line.1 << k. Test with (n >> k) & 1, set with n | (1 << k), clear with n & ~(1 << k).n & (n - 1) loop. Counting Bits, Hamming weight, power-of-two — all popcount in disguise.result = (result << 1) | (n & 1), then n >>>= 1. Reverse Bits, or any “assemble an integer”.look at what the problem is really asking about the bits:
"find the odd one out / pairs cancel?" -> XOR everything
result = 0; for n in nums: result ^= n
"test / set / clear bit k?" -> mask with (1 << k)
test : (n >> k) & 1
set : n | (1 << k)
clear : n & ~(1 << k)
"walk the 1-bits only?" -> n & (n - 1) loop
while n != 0: n &= n - 1; count++
"build a number bit by bit?" -> shift-and-OR
result = (result << 1) | (n & 1); n >>>= 1Before writing the loop, state the invariant as a sentence. If you can say what each operator is for, you can't reach for the wrong one:
resultholds only the unpaired bits.”n &= n - 1removes exactly one set bit, so the iteration count equals the number of 1s.”a ^ b is the sum with carries ignored; (a & b) << 1is the carries — loop until there are no carries left.”nhas strictly fewer set bits after every iteration.” That single fact proves the loop both terminates and counts correctly.The mental model assumes a clean unsigned row of bits, but JavaScript coerces every bitwise operand to a 32-bit signed integer. The top switch is the sign bit, and two things go wrong because of it:
>> is an arithmetic shift — it copies the sign bit inward, so -1 >> 1 stays -1. When you want a clean zero-fill (reverse bits, popcount, building results) use >>> instead.>>> 0each pass, and normalize Reverse Bits' output the same way.>>> 0. If the numbers can exceed 32 bits at all, the whole bit-vector model is off the table — switch to BigInt or plain arithmetic.n & (n−1) snips the lowest set bit.It's the one bit trick to truly memorize: it turns "count / clear bits" into a loop that runs once per 1-bit, not once per bit. The Visualize tab shows each lowest 1 vanishing.Every integer is a compact array of 0s and 1s. The four bitwise operators each have a single, memorable job:
a ^ b (XOR) — bits that differ. Crucially, a ^ a === 0 and a ^ 0 === a, so XOR-ing a sequence cancels every duplicate and leaves the survivor.a & b (AND) — bits that are both set. Use it to test a bit (n & 1 checks parity) or to mask out all but certain bits.a | b (OR) — sets bits. Use it to turn a bit on in a mask or accumulate flags.a << k / a >> k — shifts, equivalent to multiplying or dividing by powers of two.a ^ a = 0, a ^ 0 = a. XOR-accumulate a list — every element that appears an even number of times cancels, leaving only the odd-count survivor. Used in Single Number and Missing Number.n & (n - 1) clears the lowest set bit of n. Loop until n === 0 and you count exactly as many iterations as there are set bits — O(k) instead of O(32).Power-of-two test falls out for free: n > 0 && (n & (n - 1)) === 0 is true iff exactly one bit is set.
Both are technically O(1) for fixed-width integers, but the Kernighan loop is the expected answer in interviews because it demonstrates you understand the trick.
JavaScript coerces operands to 32-bit signed integers before every bitwise operation and returns a signed 32-bit result. This means:
1 << 31 is -2147483648 (the sign bit), not a large positive number.>> is an arithmetic right-shift — it copies the sign bit. For bit reversal or popcount you almost always want >>> (zero-fill / unsigned).carry >>> 0 to force it back to unsigned and avoid an infinite loop.Rule of thumb: whenever your result should be treated as an unsigned 32-bit value, append >>> 0 to normalize it.
156 = 10011100. Naively you'd test all 8 bits; instead, n&(n−1) snips the lowest 1 so we loop once per 1-bit.Reach for bit manipulation when the problem is fundamentally about individual binary digits of integers — detecting, counting, toggling, or exploiting the cancellation property of XOR. The problems are almost always O(1) space and O(n) or O(32) time.
| "every element appears twice except one" (or k times except one) | XOR-accumulate all values — pairs cancel, the singleton survives |
| "count set bits" / "Hamming weight" / "number of 1-bits" | n &= (n-1) loop (Brian Kernighan) — O(k) iterations |
| "add / sum two integers without using + or -" | XOR for digit sum + (AND << 1) for carry, loop until carry is 0 |
| "find the missing number in range 0..n" | XOR all indices and all values — only the missing index survives |
| "reverse the bits of a 32-bit unsigned integer" | shift result left, OR in low bit of n, repeat 32 times; use >>> to avoid sign extension |
| "is the number a power of two?" | n > 0 && (n & (n-1)) === 0 — a power of two has exactly one set bit |
| "enumerate all subsets" / "bitmask DP" | iterate 0..(1<<n)-1; bit k set ↔ element k included in the subset |
n % 2 === 0 is preferred over (n & 1) === 0. Use bit tricks in interviews, but flag the tradeoff.>> sign-extends in JS, which can corrupt a reverse-bits or popcount result. Audit every shift — if you need zero-fill, switch to >>>.When → Every element appears an even number of times except exactly one. XOR all values — every duplicate pair annihilates, the lone survivor remains. For missing number, also XOR the complete index set 0..n.
// Single number / missing number via XOR accumulation
function singleNumber(nums: number[]): number {
let result = 0;
for (const n of nums) {
result ^= n; // a ^ a === 0, so every duplicate pair cancels
}
return result; // only the unpaired value survives
}
// Missing number 0..n: XOR all indices AND all values — the missing index survives
function missingNumber(nums: number[]): number {
let xor = nums.length; // start with n (the "extra" index not present in nums)
for (let i = 0; i < nums.length; i++) {
xor ^= i ^ nums[i]; // each present value cancels its matching index
}
return xor;
}x ^ x = 0; the unpaired element contributes x ^ 0 = x.When → You need the number of set bits in an integer (Hamming weight), or you want to check whether an integer is a power of two. Also the basis of the DP recurrence for Counting Bits.
// Count set bits using Brian Kernighan's trick: n & (n-1) clears the lowest set bit
function hammingWeight(n: number): number {
let count = 0;
while (n !== 0) {
n &= n - 1; // drops the rightmost 1-bit each iteration
count++;
}
return count; // O(k) where k = number of set bits, not O(32)
}
// DP approach for Counting Bits (all values 0..n):
// bits[i] = bits[i >> 1] + (i & 1)
function countBits(n: number): number[] {
const dp = new Array(n + 1).fill(0);
for (let i = 1; i <= n; i++) {
dp[i] = dp[i >> 1] + (i & 1); // right-shift reuses a solved sub-problem
}
return dp;
}dp[i] = dp[i >> 1] + (i & 1). Shifting right by one reuses a previously computed sub-problem; the last bit is the only new contribution.When → The problem forbids + or -. XOR gives the digit-wise sum without carry; AND shifted left gives the carry bits. Repeat until the carry is zero.
// Add without + operator: XOR gives sum-without-carry; AND<<1 gives the carry
function getSum(a: number, b: number): number {
while (b !== 0) {
const carry = (a & b) << 1; // compute carry bits (need to shift left by 1)
a = a ^ b; // add without carry
b = (carry) >>> 0; // mask to 32 bits — CRITICAL to avoid infinite loop
// In JS a negative carry stays negative; >>> 0 forces it unsigned so loop terminates
}
return a;
}>>> 0 to force it unsigned each iteration.When → You must process every one of the 32 bit-positions — reversing bits, building a result bit-by-bit, or checking each position with a mask. Use >>> for the input shift to avoid sign extension.
// Reverse all 32 bits — iterate, shift result left, OR in the low bit of n
function reverseBits(n: number): number {
let result = 0;
for (let i = 0; i < 32; i++) {
result = (result << 1) | (n & 1); // grab the low bit of n, append to result
n >>>= 1; // unsigned right-shift to avoid sign extension
}
return result >>> 0; // force unsigned 32-bit for correct output
}
// Power of two check — true iff exactly one bit is set
function isPowerOfTwo(n: number): boolean {
return n > 0 && (n & (n - 1)) === 0; // n & (n-1) clears the single set bit → 0
}result >>> 0 converts the JS signed integer back to an unsigned 32-bit representation, matching what LeetCode expects for Reverse Bits.All JS bitwise ops silently truncate to 32-bit signed integers. A large positive number like 1 << 31 becomes -2147483648. Wherever your algorithm treats the result as unsigned — especially in Reverse Bits and any carry computation — append >>> 0 to reinterpret it as unsigned.
>> copies the sign bit (arithmetic shift), so -1 >> 1 is still -1. >>> zero-fills from the left. For popcount loops, bit-reversal, and any situation where you want a logical shift, always use >>> or ensure your input is non-negative.
If (a & b) << 1 produces a negative JS integer, the loop condition b !== 0 can cycle forever because the carry never reaches zero through signed arithmetic. Fix: assign b = (carry) >>> 0 so the value is treated as an unsigned 32-bit integer on every iteration.
The Kernighan loop guard should be while (n !== 0), not while (n), to handle the case n = 0 correctly in TypeScript strict mode (n is a number, not a boolean). Also note that the power-of-two check must start with n > 0 — zero satisfies (n & (n - 1)) === 0 but is not a power of two.