Bit Masking & Complements

Imagine you're spray-painting a t-shirt. You cut out a stencil — maybe a star shape — and place it over the fabric. When you spray, only the star gets painted. The rest of the shirt is protected.

A bit mask is exactly that stencil. It's a pattern of bits that selects which bits of a number you want to modify, and which bits you want to leave alone.

Let's meet the 5 operations you can do with a mask. These are the spray cans in your toolkit:

Problem: Given a positive integer, flip every bit in its binary representation and return the result.

For n = 5 (binary 101), the complement is 010 = 2.

🤔 Let's Think About It

How do you flip a bit? You XOR with 1! Every bit XOR'd with 1 flips: 0→1, 1→0.

So we need a mask of all 1s that's the same length as our number. For 5 (101), we need 111. The trick: find the bit-length, then compute (1 << bitLength) - 1.

📋 Edge Cases to Consider

• n = 0: The complement should be 1 (since 0 has 1 bit, 0 ^ 1 = 1). But Math.log2(0) is -Infinity. Must handle n=0 as a special case.
• n = 1: Binary "1", bit length = 1. mask = (1 << 1) - 1 = 1. 1 ^ 1 = 0. Works!
• n = power of two: e.g., 8 (1000). bit length = 4. mask = (1 << 4) - 1 = 15 (1111). 8 ^ 15 = 7 (0111). Works!
• Large numbers (near 2^31): JavaScript bitwise ops truncate to 32-bit. (1 << 31) overflows. Use BigInt for larger values.

Brute Force — Build Mask Bit by Bit

function bitwiseComplement(n) {
  if (n === 0) return 1;

  // Find bit-length
  let bitLength = 0;
  let temp = n;
  while (temp > 0) {
    temp >>= 1;
    bitLength++;
  }

  // Build mask of all 1s
  let mask = 0;
  for (let i = 0; i < bitLength; i++) {
    mask = (mask << 1) | 1;   // 0 → 1 → 11 → 111
  }

  return n ^ mask;  // XOR flips every bit
}

bitwiseComplement(5);   // 2  (101 ^ 111 = 010)
bitwiseComplement(10);  // 5  (1010 ^ 1111 = 0101)
bitwiseComplement(0);   // 1

🔍 Real-Time Thinking — What Do I Know?

"I need to flip every bit of n. Flipping a bit is XOR with 1. So I need a mask of all 1s with the same bit length as n. How do I build that mask? If I find the bit length (say 3 for n=5, which is 101), then (1 << 3) = 1000, and (1 << 3) - 1 = 0111 = 111. That's my mask! Then n ^ mask flips everything. Let me check: 5 (101) ^ 7 (111) = 010 = 2. That's correct. The formula is: mask = (1 << bitLength) - 1."

✨ The Optimal One-Liner

Same idea, but we compute the mask in one shot:

function bitwiseComplement(n) {
  if (n === 0) return 1;
  const bitLength = Math.floor(Math.log2(n)) + 1;
  const mask = (1 << bitLength) - 1;   // e.g., 3 → 0b111
  return n ^ mask;
}

Edge Cases

• n = 0: complement is 1 (0 has 1 bit, 0 ^ 1 = 1)
• Power of two: e.g., 8 (1000) → 7 (0111). The mask must not clip the leading 1.
• Large numbers: JS bitwise works on 32-bit signed integers, so this works for integers up to 2³¹-1.

Problem: Given a positive integer, find the longest sequence of consecutive zeros between two 1s in its binary representation.

For n = 9 (1001), there are two 1s at positions 0 and 3. The gap between them is 3 - 0 = 3.

The Algorithm — Track Position of Last 1

We scan bits from right to left. When we find a 1, we check how far it is from theprevious 1 we saw. The maximum distance is our answer.

function binaryGap(n) {
  let lastPos = -1;      // position of the last 1 we saw
  let maxGap = 0;

  for (let pos = 0; n > 0; pos++) {
    if (n & 1) {          // current bit is 1
      if (lastPos !== -1) {
        maxGap = Math.max(maxGap, pos - lastPos);
      }
      lastPos = pos;
    }
    n >>= 1;              // move to next bit
  }

  return maxGap;
}

binaryGap(9);      // 3  (1001)
binaryGap(1041);   // 5  (10000010001)
binaryGap(6);      // 1  (110)
binaryGap(8);      // 0  (1000) — only one 1
binaryGap(1);      // 0  (1) — only one 1

Dry Run — 9 (1001) Step by Step

Alternating Bits — The XOR Shift Trick

Problem: Check if a number's binary representation has alternating bits (no two adjacent bits are the same).

Here's the magic: n ^ (n >> 1) puts a 1 wherever adjacent bits differ. If ALL adjacent bits differ, the result is all 1s!

🔍 Real-Time Thinking — What Do I Know?

"I need to check if adjacent bits alternate. If I XOR n with n >> 1, I get 1 wherever adjacent bits differ. If ALL adjacent bits differ, the result is ALL 1s. How do I check if a number is all 1s? Well, if x is all 1s (like 111), then x+1 = 1000, and x & (x+1) = 0. That's exactly like the power-of-two check but inverted! So: n ^ (n>>1) gives the difference pattern. Then (x & (x+1)) === 0 means it's all 1s. Let me verify with 5 (101): 5 ^ 2 = 7 (111). 7 & 8 = 0. Yes, alternating!"

function hasAlternatingBits(n) {
  // XOR n with itself shifted right by 1
  // If bits alternate, every adjacent pair differs → all 1s
  const x = n ^ (n >> 1);

  // Check if x is all 1s: (x & (x + 1)) === 0
  // e.g., 5 (101) ^ 2 (10) = 7 (111)
  // 7 & (7+1) = 7 & 8 = 0 ✅
  return (x & (x + 1)) === 0;
}

hasAlternatingBits(5);   // true  101
hasAlternatingBits(7);   // false 111 (adjacent 1s)
hasAlternatingBits(10);  // true  1010
hasAlternatingBits(11);  // false 1011

Problem: Convert a 32-bit integer to its hexadecimal representation. Handle negative numbers via two's complement.

🤔 Bits to Hex: 4 Bits at a Time

Hexadecimal is base-16. Each hex digit represents exactly 4 bits. So we can extract 4 bits at a time using a mask of 0xF (which is 1111in binary), map them to a character, and repeat!

function toHex(num) {
  if (num === 0) return "0";

  const hexChars = "0123456789abcdef";
  let result = "";

  // >>> 0 converts to unsigned 32-bit (handles negatives!)
  let n = num >>> 0;

  while (n > 0) {
    const digit = n & 0xf;           // extract lowest 4 bits
    result = hexChars[digit] + result;
    n >>>= 4;                         // shift right by 4 bits
  }

  return result;
}

toHex(26);    // "1a"
toHex(255);   // "ff"
toHex(-1);    // "ffffffff"  (two's complement!)
toHex(0);     // "0"

Dry Run — 26 to Hex

Problem: Given two binary strings, return their sum as a binary stringwithout converting them to integers.

🤔 The Old-School Way

Remember adding numbers in elementary school? Line them up, add column by column, carry the overflow to the next column. Binary is EXACTLY the same — except overflow happens at 2 instead of 10.

Brute Force — Parse Then Add

function addBinaryBrute(a, b) {
  // Convert to integers, add, convert back
  // PROBLEM: JavaScript loses precision for large numbers!
  return (parseInt(a, 2) + parseInt(b, 2)).toString(2);
}

// Works for small strings:
addBinaryBrute("11", "1");     // "100"
// Fails for large strings — precision loss!

✨ The Column Addition Solution

function addBinary(a, b) {
  let i = a.length - 1;
  let j = b.length - 1;
  let carry = 0;
  let result = [];

  while (i >= 0 || j >= 0 || carry > 0) {
    const bitA = i >= 0 ? parseInt(a[i], 10) : 0;
    const bitB = j >= 0 ? parseInt(b[j], 10) : 0;

    const sum = bitA + bitB + carry;
    result.push(sum % 2);              // sum bit
    carry = Math.floor(sum / 2);       // carry to next column

    i--;
    j--;
  }

  return result.reverse().join("");
}

addBinary("11", "1");        // "100"
addBinary("1010", "1011");   // "10101"
addBinary("0", "0");         // "0"
addBinary("1111", "1");      // "10000"

Edge Cases & Carry Ripples

• Single carry: "1" + "1" = "10" (carry adds one bit)
• Ripple carry: "1" + "111" = "1000" (carry propagates through all bits)
• Equal length: "1010" + "0101" = "1111" (no carry at all)
• Result longer: "111" + "111" = "1110" (result is 1 bit longer than inputs)

Problem: A binary watch displays time using LEDs. The hour (0–11) uses 4 LEDs and the minute (0–59) uses 6 LEDs. Given a number of LEDs that are turned on, list all possible times.

🔍 Real-Time Thinking — What Do I Know?

"I need to find all times where exactly k LEDs are lit. Hours: 0-11 (4 bits). Minutes: 0-59 (6 bits). Total combinations: 12 × 60 = 720 — that's tiny! I can brute force this by iterating over ALL hours and minutes and counting set bits. For each hour h and minute m, if popcount(h) + popcount(m) === k, I add the time to the result. Brute force IS the optimal solution here because the search space is so small."

🤔 The Combinatorial Approach

We need to find all pairs of (hour, minute) where the total number of 1-bits equalsturnedOn. The brute-force way: check EVERY possible hour (0–11) and EVERY possible minute (0–59), count their set bits, and collect valid pairs.

That's only 12 × 60 = 720 combinations — tiny! So brute force is the optimal solution here.

function readBinaryWatch(turnedOn) {
  const result = [];

  for (let h = 0; h < 12; h++) {
    for (let m = 0; m < 60; m++) {
      // Count set bits in hour + minute
      const bits = popcount(h) + popcount(m);

      if (bits === turnedOn) {
        const time = h + ":" + m.toString().padStart(2, "0");
        result.push(time);
      }
    }
  }

  return result;
}

// Brian Kernighan's algorithm — count set bits
function popcount(n) {
  let count = 0;
  while (n) {
    n &= n - 1;   // clear the lowest set bit
    count++;
  }
  return count;
}

readBinaryWatch(1);
// ["0:01","0:02","0:04","0:08","0:16","0:32",
//  "1:00","2:00","4:00","8:00"]

readBinaryWatch(9);  // [] — max 10 LEDs (4+6), can't have 9

Why Popcount Matters

The popcount (n & (n - 1)) is itself a bit masking trick! Each iteration clears the lowest set bit and increments the counter. For a number with k set bits, it runs k times instead of checking all 32 bit positions.

These tricks appear in dozens of LeetCode problems. Memorize them.They're the building blocks of every bit manipulation solution.

Set, Clear, Toggle, Check

// Check if k-th bit is set
(n >> k) & 1
// or: (n & (1 << k)) !== 0

// Set k-th bit to 1
n | (1 << k)

// Clear k-th bit to 0
n & ~(1 << k)

// Toggle k-th bit
n ^ (1 << k)

Power of Two Check

function isPowerOfTwo(n) {
  return n > 0 && (n & (n - 1)) === 0;
}

// Why? Powers of two have exactly ONE set bit.
// n & (n-1) clears the lowest set bit.
// If that makes n zero, there was only one set bit!
isPowerOfTwo(1);    // true  (2⁰)
isPowerOfTwo(16);   // true  (2⁴)
isPowerOfTwo(6);    // false (110 — two set bits)

Isolate Lowest Set Bit

// n & -n isolates the rightmost 1 bit
// Why? -n = ~n + 1 (two's complement)
// The +1 flips trailing 0s and the lowest 1,
// ~ flips higher bits — AND isolates the lowest 1

lowestSetBit(12);  // 4  (1100 → 0100)
lowestSetBit(10);  // 2  (1010 → 0010)
lowestSetBit(7);   // 1  (111 → 001)

Mask Lower N Bits

// Create N bits of 1s
const mask = (1 << N) - 1;

maskLowBits(3);  // 7   (0b111)
maskLowBits(4);  // 15  (0b1111)
maskLowBits(8);  // 255 (0b11111111)

1. Bit masking = using stencils. A mask selects which bits you operate on; the operator determines what you do.
2. Number complement: Build a mask of all 1s with (1 << bitLength) - 1, then XOR.
3. Binary gap: Track lastPos of each 1. The max distance between consecutive 1s is your answer.
4. Alternating bits: n ^ (n>>1) detects adjacent differences. All 1s means alternating.
5. Hex conversion: Extract 4 bits at a time with 0xF mask. >>> 0 handles negatives.
6. Add binary: Column addition with carry. sum % 2 for bit, Math.floor(sum/2) for carry.
7. Binary watch: Brute force 720 combinations, filter by popcount. Sometimes brute force IS the optimal answer.
8. n & (n-1) clears the lowest set bit — foundation of popcount and power-of-2 checks.
9. n & -n isolates the lowest set bit — two's complement magic.
10. Practice! Head to the Playground below and solve these problems. The only way masking clicks is by doing it 🥋