Bitwise Operations

Left shift (<<): moves all bits left by n positions, filling with zeros on the right. Equivalent to multiplying by 2^n. Each position shift doubles the value.

Signed right shift (>>): moves all bits right by n positions, filling with the sign bit. Equivalent to dividing by 2^n (floor for positive, ceiling for negative in magnitude).

Unsigned right shift (>>>): always fills with 0 from the left, ignoring sign. Use this for treating numbers as unsigned 32-bit integers in JavaScript.

// Left shift: multiply by powers of 2
console.log(1 << 0);  // 1
console.log(1 << 1);  // 2
console.log(1 << 2);  // 4
console.log(5 << 1);  // 10 (multiply by 2)
console.log(5 << 2);  // 20 (multiply by 4)

// Signed right shift: integer divide by powers of 2
console.log(20 >> 1); // 10 (divide by 2)
console.log(20 >> 2); // 5  (divide by 4)
console.log(-8 >> 1); // -4 (sign bit preserved!)

// Unsigned right shift:
console.log(-1 >>> 0); // 4294967295 (all 32 bits set = max uint32)
console.log(-1 >> 0);  // -1 (sign bit preserved)

Fast power-of-2 operations: x << n is faster than Math.pow(2,n) and n * Math.pow(2,k). Used in hash functions, low-level algorithms, and memory addressing.

Common interview trick: mid = lo + ((hi - lo) >> 1) is safer than (lo+hi)/2 — avoids integer overflow risk in languages with fixed-width integers.

The least significant bit (LSB, bit 0) determines parity: if bit 0 is 1, the number is odd; if 0, it's even. AND with 1 to extract this bit.

This is faster than n % 2 because it's a single bitwise AND operation vs division. Modern CPUs often optimize % 2 similarly, but the bitwise version expresses intent clearly.

Knowing that odd/even correlates with the LSB is fundamental for many bit manipulation patterns.

function isEven(n) { return (n & 1) === 0; }
function isOdd(n)  { return (n & 1) === 1; }

// Examples:
console.log(4 & 1); // 0 => even (100 & 001 = 000)
console.log(7 & 1); // 1 => odd  (111 & 001 = 001)
console.log(0 & 1); // 0 => even
console.log(-3 & 1); // 1 => odd (works for negatives too: two's complement)

// Branchless even/odd check:
console.log(!!(n & 1) ? 'odd' : 'even');

Works for negative numbers: in two's complement representation, the LSB still correctly identifies even/odd for negative integers (e.g., -3 in binary ...11111101, LSB=1, odd).

LSB patterns appear frequently: checking if numbers in a loop are even (for batch processing), determining which half of a binary partition a number belongs to, etc.

XOR-swap uses the reversibility of XOR: a^b^b = a. Three XOR operations exchange two values without any extra memory. Works for integers of the same bit-width.

Steps: a^=b makes a = a^b; b^=a makes b = (a^b)^b = a (original); a^=b makes a = (a^b)^a = b (original).

Caveat: XOR-swap fails when a and b are the same variable or reference the same memory location — 3 XORed with itself gives 0.

// XOR swap
function swapXOR(a, b) {
  a = a ^ b; // a now holds a XOR b
  b = a ^ b; // b = (a^b)^b = a (original a)
  a = a ^ b; // a = (a^b)^a = b (original b)
  return [a, b];
}
// swapXOR(5, 3) => [3, 5] ✓
// swapXOR(7, 7) => [0, 0] ✗ (bug when same value AND same reference!)

// ES6 destructuring swap (cleaner and safe):
let x = 5, y = 3;
[x, y] = [y, x]; // swap (no temp variable needed in JS)

// Arithmetic swap (can overflow): a+=b; b=a-b; a-=b;

XOR-swap is historically used in low-level code (embedded, assembly) where temporary variables are expensive. Modern CPUs handle register swapping efficiently anyway.

In JavaScript, destructuring swap [a,b]=[b,a] is cleaner, safer, and more readable. Use XOR-swap only when demonstrating bit manipulation knowledge.

A power of 2 has exactly ONE bit set in binary (1, 10, 100, 1000...). n & (n-1) clears the lowest set bit. For a power of 2, this makes the result zero.

n-1 for a power of 2 gives all 1s below the single set bit (e.g., 8-1=7: 1000-1=0111). ANDing these gives 0.

Always check n > 0 first — 0 is not a power of 2 but 0 & (0-1) = 0 would incorrectly pass the test.

function isPowerOf2(n) {
  return n > 0 && (n & (n - 1)) === 0;
}
// isPowerOf2(1)  => true  (1 = 0001, n-1=0000, AND=0)
// isPowerOf2(2)  => true  (2 = 0010, n-1=0001, AND=0)
// isPowerOf2(4)  => true  (4 = 0100, n-1=0011, AND=0)
// isPowerOf2(6)  => false (6 = 0110, n-1=0101, AND=0100 ≠ 0)
// isPowerOf2(0)  => false (0 fails first condition n>0)
// isPowerOf2(-8) => false (negative numbers aren't powers of 2 here)

n & (n-1) clears the lowest set bit — this is the key primitive for counting set bits (Brian Kernighan) and detecting exactly-one-set-bit (power of 2).

Related: power of 4 has its one set bit at an even position. Check: isPowerOf2(n) && (n & 0xAAAAAAAA) === 0 (bits at odd positions only for powers of 4).

Brian Kernighan's algorithm: n & (n-1) clears the lowest set bit each iteration. Count iterations until n becomes 0. Time = O(number of set bits), not O(32).

Naive approach: check each bit with n & 1 and shift. O(32) always. Kernighan's is faster when set bits are sparse (few 1s).

Lookup table approach: precompute popcount for all 8-bit values (256 entries), sum four lookups for 32-bit number. O(1) per query after O(256) preprocessing.

// Brian Kernighan: O(set bits count)
function countSetBits(n) {
  let count = 0;
  while (n) {
    n &= (n - 1); // remove lowest set bit
    count++;
  }
  return count;
}
// countSetBits(13) => 3 (1101 has three 1s)
// Steps: 1101 → 1100 (removed bit0) → 1000 (removed bit2) → 0000 (removed bit3), count=3

// Naive approach (always O(32)):
function countBitsNaive(n) {
  let count = 0;
  while (n) { if (n & 1) count++; n >>>= 1; }
  return count;
}

n & (n-1) strips the lowest set bit in O(1) — this elegant one-liner is used in Kernighan's counting, power-of-2 checking, and many bit manipulation patterns.

In C/C++: __builtin_popcount(n) uses a hardware instruction (POPCNT) for O(1) direct hardware computation. In JS: no direct equivalent, but the bit patterns are the same.

XOR with a mask that has 1 at the target position. XOR with 1 flips the bit (0→1, 1→0) while XOR with 0 preserves it. This is why XOR is the toggle operator.

Bit position n means 2^n in decimal. Use 1 << pos to create the mask for position pos (0-indexed from right).

Toggling is useful in bitmasked state flags (toggle feature on/off), LED display patterns, and bitmask DP state transitions.

function toggleBit(n, pos) {
  return n ^ (1 << pos);
}
// toggleBit(5, 1) => 7  (101 ^ 010 = 111, bit 1 was 0 → 1)
// toggleBit(5, 0) => 4  (101 ^ 001 = 100, bit 0 was 1 → 0)
// toggleBit(5, 2) => 1  (101 ^ 100 = 001, bit 2 was 1 → 0)

// Summary of all single-bit operations:
const mask = 1 << pos;
const check  = (n & mask) !== 0;  // is this bit set?
const setB   = n | mask;           // set this bit to 1
const clear  = n & ~mask;          // clear this bit to 0
const toggle = n ^ mask;           // toggle this bit

XOR = toggle operator: x^1 flips bit, x^0 preserves bit. This is different from AND (clear) and OR (set). All three are needed for complete bit manipulation.

Combined operations example: toggle bits 0 and 2 in n=5: n ^ (1|4) = n ^ 5 = 5^5=0. Applying the same mask twice restores the original (toggle twice = no change).

XOR has the property that x^x=0 and x^0=x. XOR all expected values 1..n, then XOR all array elements. Paired values cancel out, leaving the single missing value.

This is O(n) time and O(1) space — better than the sum formula (which can overflow), equal in simplicity. Both methods are valid and often seen in interview answers.

The XOR approach works because duplicates cancel: each number from 1 to n XORed with itself (from the array) leaves 0. The missing number has no pair to cancel with.

function findMissing(arr, n) {
  let xor = 0;
  for (let i = 1; i <= n; i++) xor ^= i;      // XOR all 1..n
  for (const val of arr) xor ^= val;            // XOR all array elements
  return xor;                                    // remaining = missing number
}
// findMissing([1,2,4,5], 5) => 3
// Process: 1^2^3^4^5 ^ 1^2^4^5 = 3 (paired values cancel: 1^1=0, etc.)

// Alternative: sum formula O(n), O(1) space
function findMissingSum(arr, n) {
  return (n * (n + 1)) / 2 - arr.reduce((s,x) => s+x, 0);
}

XOR approach is overflow-safe — in fixed-width integer languages, the sum n*(n+1)/2 can overflow but XOR never does (it's bitwise, not arithmetic).

Extension: if there are TWO missing numbers (not one), the XOR approach extends: XOR gives a^b, use set-bit partitioning to find a and b separately.

Left-shifting by 1 position multiplies by 2. This works because shifting binary digits left is equivalent to multiplying by the base (2 in binary), just as shifting decimal digits left multiplies by 10.

More generally, n << k = n * 2^k. Right-shift n >> k = Math.floor(n / 2^k). These are the fastest integer multiply/divide operations.

Used in: hash functions, memory alignment calculations, converting between byte sizes, and anywhere you need fast power-of-2 arithmetic.

function multiplyBy2(n) { return n << 1; }    // n * 2
function multiplyBy4(n) { return n << 2; }    // n * 4
function multiplyBy8(n) { return n << 3; }    // n * 8
function divideBy2(n)   { return n >> 1; }    // Math.floor(n/2)
function divideBy4(n)   { return n >> 2; }    // Math.floor(n/4)

// Combine: multiply by non-power-of-2 (e.g., multiply by 6 = 4+2)
function multiplyBy6(n) { return (n << 2) + (n << 1); }

// Negate (two's complement): flip bits + add 1
function negate(n) { return ~n + 1; }
console.log(negate(5));  // -5
console.log(negate(-5)); // 5

Bit-shift arithmetic for arbitrary multipliers: any multiplication can be expressed as sum-of-shifts. Compilers already do this optimization for powers of 2.

Watch for overflow: left shift can lose bits. For 32-bit integers in JavaScript, shifting beyond 31 causes unexpected behavior. Use BigInt for large numbers.

Create a mask with only the target bit set: 1 << pos. AND the number with this mask — if the result is non-zero (truthy), the bit at position pos is 1.

Bit positions are 0-indexed from the right (LSB = position 0). For n=5 (binary 101): bit 0 is 1, bit 1 is 0, bit 2 is 1.

This pattern is the foundation: check, set, clear, and toggle bits all use (1 << pos) as the mask.

function isBitSet(n, pos) {
  return (n & (1 << pos)) !== 0;
}
// isBitSet(5, 0) => true  (101 bit 0 = 1)
// isBitSet(5, 1) => false (101 bit 1 = 0)
// isBitSet(5, 2) => true  (101 bit 2 = 1)

// Set a bit: n | (1 << pos)
// Clear a bit: n & ~(1 << pos)
// Toggle a bit: n ^ (1 << pos)

Four bit operations: check (AND), set (OR), clear (AND NOT), toggle (XOR). These four cover all single-bit manipulation needs.

~(1 << pos) creates a mask with all bits 1 EXCEPT position pos. ANDing with it clears that bit while leaving all others unchanged.

XOR all elements: the result = a^b (the two unique numbers, since all pairs cancel). Then find a set bit in a^b (the lowest set bit: a^b & -(a^b)). This bit is 1 in one of a or b but not the other.

Use this bit to partition elements into two groups and XOR each group independently — each group's XOR gives one of the two unique elements.

This elegant solution uses O(1) space and O(n) time — no sorting or hash maps needed.

function twoNonRepeating(arr) {
  let xor = 0;
  for (const n of arr) xor ^= n;  // xor = a^b
  // Get rightmost set bit (differs between a and b)
  const diffBit = xor & (-xor);   // isolate lowest set bit
  let a = 0, b = 0;
  for (const n of arr) {
    if (n & diffBit) a ^= n;       // group with diffBit set
    else b ^= n;                    // group without diffBit
  }
  return [a, b];
}
// twoNonRepeating([1,2,3,4,2,3]) => [1,4] (order may vary)

Lowest set bit trick: n & (-n) isolates the rightmost 1 bit. -n in two's complement flips all bits and adds 1, so only the rightmost set bit survives the AND.

Extension: if three numbers don't repeat, use bit counting (count each bit position, take modulo 3) — pure XOR no longer works for three uniques.

The rightmost set bit is the lowest-order bit that is 1. Use n & (-n) to isolate it, then take log base 2 or count trailing zeros to get its position.

n & (n-1) clears the lowest set bit. So n XOR (n&(n-1)) gives only the lowest set bit in one operation.

This is a building block for many bit manipulation problems, including counting set bits (Brian Kernighan) and XOR-based partitioning.

// Method 1: n & (-n) isolates rightmost set bit
function rightmostSetBit(n) {
  const bit = n & (-n);
  return Math.log2(bit); // position (0-indexed)
}
// rightmostSetBit(12) => 2 (12=1100, rightmost 1 is bit 2)
// rightmostSetBit(8)  => 3 (8=1000, rightmost 1 is bit 3)

// Method 2: count trailing zeros
function trailingZeros(n) {
  if (n === 0) return -1;
  let pos = 0;
  while ((n & 1) === 0) { n >>>= 1; pos++; }
  return pos;
}
// trailingZeros(12) => 2 (12 = ...1100)

n & (-n) is the fastest single-expression approach — two's complement makes -n have all trailing zeros flipped to zero and the first 1 preserved.

Modern CPUs have a CTZ (count trailing zeros) hardware instruction. In competitive programming, __builtin_ctz(n) in C++ or Number.prototype.toString based methods in JS achieve similar speed.

Use XOR for sum without carry, AND for the carry bits, and shift carry left by 1. Repeat until carry becomes 0. This mirrors how binary addition works at the hardware level.

XOR gives the sum of bits without carry (like adding binary digits independently). AND & left shift gives the carry that needs to propagate to the next bit.

This requires multiple iterations as carries can cascade left — like how 999+1=1000 requires multiple carries.

function addWithoutPlus(a, b) {
  while (b !== 0) {
    const carry = (a & b) << 1;  // bits where both are 1 = carry
    a = a ^ b;                      // sum without carry
    b = carry;                       // carry to add in next iteration
  }
  return a;
}
// addWithoutPlus(5, 3) => 8
// Step 1: carry=(101&011)<<1=010<<1=100, a=101^011=110, b=100
// Step 2: carry=(110&100)<<1=100<<1=1000, a=110^100=010, b=1000
// Step 3: carry=(010&1000)<<1=0, a=010^1000=1010=10, b=0 => 10 ✓

XOR = sum without carry, AND = carry positions — these are the two fundamental binary addition operations implemented in hardware adder circuits.

In JavaScript, << on signed 32-bit integers may cause issues for very large numbers. Use BigInt for arbitrary precision or be mindful of 32-bit overflow.

Extract the LSB of n, shift it into the result from the MSB position. Repeat 32 times. Alternative: split into bytes, reverse each byte's bits (can use lookup table), then swap byte positions.

For JavaScript: numbers are 64-bit floats but bitwise ops treat them as signed 32-bit integers. Use >>> 0 for unsigned treatment.

Used in data compression, cryptography, digital signal processing, and implementing endian conversion.

function reverseBits(n) {
  let result = 0;
  for (let i = 0; i < 32; i++) {
    result = (result << 1) | (n & 1); // shift result left, add LSB of n
    n >>>= 1;                            // shift n right (unsigned)
  }
  return result >>> 0; // ensure unsigned 32-bit
}
// reverseBits(0b00000010100101000001111010011100)
//           => 0b00111001011110000010100101000000
//           => 964176192

// More explicit:
// n=43261596=0b00000010100101000001111010011100
// reversed =  0b00111001011110000010100101000000

>>> operator is unsigned right shift in JavaScript. Use n >>>= 1 to ensure 0 is shifted in from the left, not the sign bit.

Optimization: if the same n is reversed multiple times, cache using a Map. For competitive programming, precompute all 256 reversed-byte values in a lookup table.

The sign bit (MSB) is 1 for negative numbers, 0 for positive. XOR the sign bits of both numbers: if result is 1, they have opposite signs.

The sign bit is bit 31 for 32-bit integers. XOR (a, b) has bit 31 set if and only if one of a or b (but not both) is negative.

Handles edge cases: 0 is treated as positive. In JavaScript, use >>> for unsigned treatment since >> would propagate the sign bit.

function hasOppositeSigns(a, b) {
  return (a ^ b) < 0;
}
// In JS, if (a^b)'s sign bit is 1 (i.e., result is negative), opposite signs
// hasOppositeSigns(-1, 5) => true  (-1 XOR 5 has MSB=1)
// hasOppositeSigns(3, 5)  => false (both positive, XOR MSB=0)
// hasOppositeSigns(0, -5) => true

// Explicit version:
function hasOppositeSigns2(a, b) {
  return ((a ^ b) >>> 31) === 1; // check bit 31
}
// >>> 31 shifts the sign bit to position 0 for clean comparison

XOR sign bit check: positive XOR negative = negative (MSB differs), positive XOR positive = positive. Single operation, no conditional needed.

Real-world use: graphics programming checks if line intersection crosses sign boundary for clipping algorithms. Optimized for inner loops where avoiding branches improves CPU pipeline efficiency.

Pattern in XOR(1..n): repeat every 4 numbers. XOR(1..n) = n if n%4==0, 1 if n%4==1, n+1 if n%4==2, 0 if n%4==3. O(1) solution without looping.

This pattern emerges because XOR of 4 consecutive numbers starting at a multiple of 4 always equals 0: 4^5^6^7 = 0, 8^9^10^11 = 0, etc.

Crucial for range XOR queries: XOR(l..r) = XOR(1..r) ^ XOR(1..l-1) using this O(1) formula.

function xorUpToN(n) {
  switch (n % 4) {
    case 0: return n;
    case 1: return 1;
    case 2: return n + 1;
    case 3: return 0;
  }
}
// xorUpToN(4) => 4 (1^2^3^4=4)
// xorUpToN(5) => 1 (1^2^3^4^5=1)
// xorUpToN(6) => 7 (1^2^3^4^5^6=7)
// xorUpToN(7) => 0 (1^2^3^4^5^6^7=0)

// Range XOR (l to r):
function rangeXOR(l, r) {
  return xorUpToN(r) ^ xorUpToN(l - 1);
}
// rangeXOR(3, 5) => 3^4^5 = 2

O(1) formula using mod 4 pattern: avoids O(n) loop entirely for prefix XOR. Range XOR query follows the same prefix XOR approach as prefix sum.

Used in competitive programming to answer multiple XOR range queries efficiently after O(1) preprocessing.

Given an XOR array where arr[i] = original[i] ^ original[i+1], recover original. With n-1 XOR differences and the first element, XOR-prefix-scan recovers each element.

XOR has the property that a^b^b = a, so XOR-ing back along the chain reverses the XOR encoding.

A broader application: XOR-based difference arrays are used in cryptography and error correction codes.

function decode(encodedArr, first) {
  const original = [first];
  for (let i = 0; i < encodedArr.length; i++) {
    original.push(original[i] ^ encodedArr[i]);
  }
  return original;
}
// encoded = [1^2, 2^3, 3^4] = [3, 1, 7], first=1
// decode([3,1,7], 1) => [1, 1^3=2, 2^1=3, 3^7=4] => [1,2,3,4]
// Verify: 1^2=3 ✓, 2^3=1 ✓, 3^4=7 ✓

// Reconstruct even-indexed first element from full XOR array:
// Given encoded is XOR of consecutive pairs, use XOR(1..n) relationships

XOR-decoding prefix scan: each element is the XOR of the previous element and the encoded difference. Simple iterative scan recovers the entire array.

This is essentially running XOR on the "derivative" array (like undoing differentiation). XOR of XOR = identity, which makes the recovery clean.

For each number in [L, R], count set bits and check if odd. Or more efficiently, use the XOR pattern: numbers 0..n with odd set bits follow a predictable pattern (half of all numbers for large ranges).

Brian Kernighan counting + scanning is O((R-L+1) * log(maxValue)). For very large ranges, prefix counting with pattern observation is O(log n).

A number has odd set bits iff its population count (popcount) is odd — equivalent to the XOR of its bits being 1.

function countOddBits(n) {
  // Count of numbers [0..n] with odd number of set bits
  let count = 0;
  for (let i = 0; i <= n; i++) {
    let bits = i, setBits = 0;
    while (bits) { bits &= bits-1; setBits++; }
    if (setBits % 2 === 1) count++;
  }
  return count;
}

// Efficient: using XOR parity pattern
function hasOddSetBits(n) {
  // Check if n has odd popcount
  let x = n;
  x ^= x >> 16; x ^= x >> 8; x ^= x >> 4;
  x ^= x >> 2; x ^= x >> 1;
  return (x & 1) === 1; // parity of all bits
}
// hasOddSetBits(7) => false (7=111, 3 bits, 3%2=1... wait, true)
// hasOddSetBits(5) => false (5=101, 2 bits set)

Parity XOR reduction: XOR all bits together gives the parity. Fold the 32-bit number by XOR-ing its two halves repeatedly until a single bit remains.

Lookup table approach: precompute parity for all 8-bit values (256 entries), then combine parities for each 8-bit chunk of the number using XOR.

For n elements, there are 2^n subsets. Each number from 0 to 2^n-1 is a bitmask where bit i being 1 means element i is included in the subset.

This approach directly maps binary representation to subset membership — no recursion needed. O(2^n * n) time to generate all subsets.

More memory-efficient than recursive backtracking for listing all subsets, as no call stack is used.

function allSubsets(arr) {
  const n = arr.length;
  const result = [];
  for (let mask = 0; mask < (1 << n); mask++) {
    const subset = [];
    for (let i = 0; i < n; i++) {
      if (mask & (1 << i)) subset.push(arr[i]); // bit i is set
    }
    result.push(subset);
  }
  return result;
}
// allSubsets([1,2,3]) generates all 8 subsets:
// mask=0 (000): []
// mask=1 (001): [1]
// mask=2 (010): [2]
// mask=3 (011): [1,2]
// mask=4 (100): [3]
// mask=5 (101): [1,3]
// mask=6 (110): [2,3]
// mask=7 (111): [1,2,3]

Bitmask to subset mapping: bit i = 1 means include arr[i]. This pattern is used in: DP on subsets (TSP, set cover), game theory (bitmask DP), and combinatorial optimization.

Bitmask DP: for subset-sum variant problems, use dp[mask] = best value achievable using the elements in the mask. Iterate over all 2^n subsets.