Basic Math & Bit Manipulation

Bit manipulation looks intimidating because of all the symbols (&, |, ^, <<, >>), but the underlying ideas are tiny. Once you can read binary like you read decimal and recognise five or six standard tricks, a whole class of "clever" interview problems becomes routine — and a lot of "normal" code (hashing, file permissions, flags) suddenly makes sense.

What "Bits" Actually Are

Computers store every value as a sequence of bits (0 or 1). 8 bits = 1 byte. Larger types (16-bit, 32-bit, 64-bit) are just longer strings of bits.

Each bit position carries a place value = 2 raised to its index, just like decimal places carry 10ⁿ:

` Bit position: 7 6 5 4 3 2 1 0 Place value: 128 64 32 16 8 4 2 1 `

Decoding 0b1101: 8 + 4 + 0 + 1 = 13. Encoding 22: 16 + 4 + 2 = 0b10110. Practice this enough that you do it without thinking — everything else builds on top.

The Six Bitwise Operators

` 1011 (11) 1011 (11) 1011 (11) & 1101 (13) | 1101 (13) ^ 1101 (13) ------ ------ ------ 1001 (9) 1111 (15) 0110 (6)

AND: both 1? OR: at least one 1? XOR: exactly one 1? `

` ~0101 = 1010 // flip every bit (NOT) 0101 << 1 = 1010 // shift left (multiply by 2) 0101 >> 1 = 0010 // shift right (integer divide by 2) `

That's it. Every "trick" later is one of these six in disguise.

The Five Patterns You'll Reuse Forever

For a single bit at position i:

Memorise these. Most "clever" bit problems are just one of these five applied to a counter.

Beginner Mistakes to Skip

1. Confusing == and &. if (n & 1) checks "is bit 0 set?" — *not* equality. 2. Operator precedence. n & 1 == 0 is parsed as n & (1 == 0) = n & 0 = 0. Always parenthesise: (n & 1) == 0. 3. Forgetting that << overflows. 1 << 32 in JS wraps to 1 (bitwise ops are 32-bit signed). For larger shifts use BigInt or multiplication. 4. Negative shifts. -8 >> 1 is -4 (arithmetic shift, sign preserved). -8 >>> 1 is a huge positive number (logical shift). Pick deliberately. 5. Treating XOR like AND. a ^ a = 0, not a. The most common trip-up. 6. Counting bits with a % loop. Works but slow; use Brian Kernighan's trick (below).

Intermediate: Two's Complement (Why -5 = 11111011)

Negative integers are stored using two's complement:

1. Write the positive number in binary. 2. Flip every bit (~). 3. Add 1.

` +5 = 00000101 ~5 = 11111010 (flip) -5 = 11111011 (add 1) `

Why this strange scheme? Because then the same hardware adder works for signed and unsigned, and there's only one zero (no +0 / -0 mess). The top (most significant) bit is the sign: 0 = positive, 1 = negative.

Range for n bits: -2^(n-1) to 2^(n-1) - 1. Useful identity: ~n = -(n + 1).

Intermediate: XOR Is the Star

XOR has algebraic properties no other op has:

Three classic problems collapse to "just XOR":

• Single number (every other element appears twice → find the unique). XOR everything; pairs cancel.
• Missing number in 0..n. XOR all indices and all values; everything cancels except the missing one.
• Swap two integers without a temp: a ^= b; b ^= a; a ^= b; — clever but useless in real code; great for showing off.

Intermediate: Shifts as Cheap Multiply/Divide

` n << k ≡ n × 2^k n >> k ≡ ⌊n / 2^k⌋ (for non-negative n) `

In tight loops on integers this is occasionally meaningful. In modern compilers the optimiser does this automatically, so prefer readable arithmetic in normal code; reach for shifts only when you specifically need bit-level meaning.

Intermediate: Three Mini-Tricks

Power of 2 check (only one bit set):

`js const isPow2 = (n) => n > 0 && (n & (n - 1)) === 0; `

Brian Kernighan's bit count (loops over set bits, not all 32):

`js function popcount(n) { let c = 0; while (n) { n &= (n - 1); c++; } return c; } `

Lowest set bit: n & -n isolates the rightmost 1. Used inside Fenwick (BIT) trees.

Advanced: Subsets via Bitmasks

A set of n items has 2ⁿ subsets. Represent each subset by an integer where bit i means "item i is in":

`js function subsets(arr) { const n = arr.length; const out = []; for (let mask = 0; mask < (1 << n); mask++) { const sub = []; for (let i = 0; i < n; i++) { if (mask & (1 << i)) sub.push(arr[i]); } out.push(sub); } return out; } `

For [a, b, c]: 000=[], 001=[a], 010=[b], …, 111=[a,b,c]. Time O(n · 2ⁿ). The same idea unlocks bitmask DP (e.g., Held–Karp TSP in O(2ⁿ · n²)).

Advanced: Bit Tricks That Show Up in Real Code

• Hash table size = power of 2 so hash & (cap - 1) replaces a modulo and is markedly faster.
• Unix file permissions rwx = 4·r + 2·w + 1·x, packed as 777 (octal). Same idea: bits as boolean flags.
• Bloom filters / bitsets store a million booleans in 125 KB — far better than 1M JS booleans.
• Fenwick / Binary Indexed Trees navigate by i & -i.
• GPU / SIMD code packs multiple lane masks into a single integer.

Advanced: Language Gotchas

• JavaScript does bitwise ops on 32-bit signed integers — even though numbers are 64-bit floats. (2 ** 31) << 1 overflows. >>> is the logical shift; everything else is arithmetic.
• Python has arbitrary-precision ints, so 1 << 100 just works. There's no >>>.
• Java has >>> for unsigned right shift; int is 32-bit, long is 64-bit; shifts are masked mod 32 (or 64).
• C/C++ unsigned vs signed shifts have different undefined-behaviour rules — read your compiler's docs before relying on it.

Advanced: Bit Manipulation in Competitive / Interview Settings

When you see n ≤ 20 and "all subsets / orderings", reach instantly for bitmasks.

Practice Path

1. By hand, write 0–15 in 4-bit binary. Repeat until you can do it in 30 seconds. 2. Implement isPow2(n) and popcount(n) (Brian Kernighan). Verify against Number.prototype.toString(2). 3. Solve Single Number (LC 136): XOR all elements. 4. Generate all subsets of [1, 2, 3] using a bitmask loop. Print the mask in binary alongside each subset; trace why the algorithm hits each.