Bit Manipulation Basics
📖 Concept
Bit manipulation operates directly on binary representations of numbers. It's extremely fast (single CPU instruction) and appears in interviews, systems programming, and optimization.
Key operators:
&(AND): Both bits must be 1 → 1|(OR): Either bit is 1 → 1^(XOR): Bits must differ → 1 (same → 0)~(NOT): Flip all bits<<(Left shift): Multiply by 2ⁿ>>(Right shift): Divide by 2ⁿ>>>(Unsigned right shift): Like >> but fills with 0
Essential tricks:
- Check if even:
(n & 1) === 0 - Check if power of 2:
n > 0 && (n & (n-1)) === 0 - Swap without temp:
a ^= b; b ^= a; a ^= b; - Get i-th bit:
(n >> i) & 1 - Set i-th bit:
n | (1 << i) - Clear i-th bit:
n & ~(1 << i) - Toggle i-th bit:
n ^ (1 << i)
XOR properties (crucial for interviews):
- a ^ a = 0 (any number XOR itself is 0)
- a ^ 0 = a (XOR with 0 is identity)
- XOR is commutative and associative
- This means XOR of all elements with one missing → finds the missing one!
🏠 Real-world analogy: Bits are like light switches — AND means both must be ON, OR means at least one ON, XOR means exactly one ON. Bit shifting is like moving decimal places in binary.
💻 Code Example
1// BASIC OPERATIONS2console.log(5 & 3); // 1 (101 & 011 = 001)3console.log(5 | 3); // 7 (101 | 011 = 111)4console.log(5 ^ 3); // 6 (101 ^ 011 = 110)5console.log(~5); // -6 (flips all bits, two's complement)6console.log(5 << 1); // 10 (101 → 1010, multiply by 2)7console.log(5 >> 1); // 2 (101 → 10, divide by 2)89// CHECK EVEN/ODD — faster than modulo10function isEven(n) { return (n & 1) === 0; }11function isOdd(n) { return (n & 1) === 1; }1213// CHECK POWER OF 214function isPowerOfTwo(n) {15 return n > 0 && (n & (n - 1)) === 0;16}17// Why? Powers of 2 have exactly one bit set:18// 8 = 1000, 7 = 0111 → 1000 & 0111 = 0000 ✓1920// FIND SINGLE NUMBER (all others appear twice)21function singleNumber(nums: number[]): number {22 let result = 0;23 for (const num of nums) {24 result ^= num; // XOR cancels pairs: a^a=0, 0^b=b25 }26 return result;27}28// [2,1,4,5,1,4,2] → 2^1^4^5^1^4^2 = 52930// COUNT SET BITS (Brian Kernighan's algorithm)31function countBits(n: number): number {32 let count = 0;33 while (n) {34 n &= (n - 1); // Removes lowest set bit35 count++;36 }37 return count;38}3940// BIT MANIPULATION ON i-th BIT41function getBit(n, i) { return (n >> i) & 1; }42function setBit(n, i) { return n | (1 << i); }43function clearBit(n, i) { return n & ~(1 << i); }44function toggleBit(n, i) { return n ^ (1 << i); }4546// SWAP WITHOUT TEMP VARIABLE47function swap(a, b) {48 a ^= b;49 b ^= a;50 a ^= b;51 return [a, b];52}5354// FIND MISSING NUMBER (0 to n, one missing)55function missingNumber(nums: number[]): number {56 let xor = nums.length;57 for (let i = 0; i < nums.length; i++) {58 xor ^= i ^ nums[i];59 }60 return xor;61}
🏋️ Practice Exercise
Practice Problems:
- Check if a number is even using bit manipulation (not modulo)
- Find the only number that appears once in an array where others appear twice
- Count the number of 1 bits in a number's binary representation
- Check if a number is a power of 2 using bit manipulation
- Find the missing number from 0 to n using XOR
- Swap two numbers without using a temp variable
- Find the XOR of all numbers from 1 to n without a loop
- Given two numbers, find the number of bits you need to flip to convert one to the other
- Reverse the bits of a 32-bit integer
- Check if two numbers have opposite signs using XOR
⚠️ Common Mistakes
Forgetting that JavaScript numbers are 64-bit floats — bitwise operators convert to 32-bit integers first
Using bit shifts for multiplication/division when clarity matters more than micro-optimization
Not understanding two's complement — ~5 is -6, not what you might expect
Forgetting that XOR swap fails when a and b are the same variable (reference)
Using signed right shift (>>) when you need unsigned (>>>) for negative numbers
💼 Interview Questions
🎤 Mock Interview
Practice a live interview for Bit Manipulation Basics