Bit Operations

🔢 Bit Manipulation: The Secret Language of Computers

The Story of Light Switches 💡

Imagine a row of 8 light switches on your wall. Each switch can be ON (1) or OFF (0). That’s exactly how computers store numbers! Instead of thinking about “42” or “7”, computers think in switches—bits!

Every single thing your computer does—playing games, showing videos, loading websites—happens because tiny switches flip ON and OFF, millions of times per second.

Today, you’ll learn to speak this secret switch language!

🧱 Bit Manipulation Fundamentals

What is a Bit?

A bit is the smallest piece of information a computer understands.

• 0 = OFF (no electricity flowing)
• 1 = ON (electricity flowing)

Think of it like:

• A single light bulb 💡
• A yes/no question
• A coin flip (heads/tails)

What is a Byte?

A byte = 8 bits together

One byte looks like: 01001010
                     ↑↑↑↑↑↑↑↑
                     8 switches!

Binary to Decimal Magic

Each switch position has a power value:

Position:   7    6    5    4    3    2    1    0
Value:    128   64   32   16    8    4    2    1

Example: What is 00001010 in decimal?

0×128 + 0×64 + 0×32 + 0×16 + 1×8 + 0×4 + 1×2 + 0×1
                             ↓         ↓
                             8    +    2    =  10

So 00001010 = 10 in decimal!

⚡ Bitwise Operations

These are the magic wands that change our switches. There are 6 main operations.

1. AND (&) — Both Must Be ON

AND only gives 1 if BOTH switches are ON.

Light Switch Analogy:
Two switches control ONE bulb.
Both must be ON for light!

    1 AND 1 = 1  ✓ Both on → Light!
    1 AND 0 = 0  ✗ One off → Dark
    0 AND 1 = 0  ✗ One off → Dark
    0 AND 0 = 0  ✗ Both off → Dark

JavaScript Example:

let a = 5;      // Binary: 0101
let b = 3;      // Binary: 0011
let result = a & b;  // Result: 0001 = 1

// Why?
//   0101  (5)
// & 0011  (3)
// ------
//   0001  (1)

2. OR (|) — At Least One ON

OR gives 1 if ANY switch is ON.

Light Switch Analogy:
Either switch can turn on the bulb!

    1 OR 1 = 1  ✓ At least one on
    1 OR 0 = 1  ✓ At least one on
    0 OR 1 = 1  ✓ At least one on
    0 OR 0 = 0  ✗ Both must be off

JavaScript Example:

let a = 5;      // Binary: 0101
let b = 3;      // Binary: 0011
let result = a | b;  // Result: 0111 = 7

3. XOR (^) — Exactly One ON

XOR gives 1 only when the switches are DIFFERENT.

The "Disagreement" Operator:
Only light up when switches disagree!

    1 XOR 1 = 0  Same → Dark
    1 XOR 0 = 1  Different → Light!
    0 XOR 1 = 1  Different → Light!
    0 XOR 0 = 0  Same → Dark

JavaScript Example:

let a = 5;      // Binary: 0101
let b = 3;      // Binary: 0011
let result = a ^ b;  // Result: 0110 = 6

4. NOT (~) — Flip All Switches

NOT flips every switch to its opposite.

let a = 5;      // Binary: 00000101
let result = ~a; // Flips: 11111010 = -6

⚠️ In JavaScript, ~n = -(n+1) due to how negative numbers work!

5. Left Shift (<<) — Multiply Power!

Shifts all bits LEFT. Each shift doubles the number!

Imagine pushing all switches LEFT:

   0101 << 1  →  1010
   (5)            (10)

   5 × 2 = 10  ✓

JavaScript Example:

let a = 3;           // Binary: 0011
let result = a << 2; // Shift 2: 1100 = 12
// 3 × 4 = 12 ✓ (2² = 4)

6. Right Shift (>>) — Divide Power!

Shifts all bits RIGHT. Each shift halves the number!

   1000 >> 1  →  0100
   (8)            (4)

   8 ÷ 2 = 4  ✓

JavaScript Example:

let a = 16;          // Binary: 10000
let result = a >> 2; // Shift 2: 00100 = 4
// 16 ÷ 4 = 4 ✓

🛠️ Bit Manipulation Techniques

These are your power tools for solving problems!

Technique 1: Check if Bit is Set

Question: Is the bit at position i turned ON?

function isBitSet(n, i) {
  return (n & (1 << i)) !== 0;
}

// Example: Is bit 2 set in 5?
// 5 = 0101
//     ↑ Position 2 is 1 → YES!
isBitSet(5, 2);  // true

Technique 2: Set a Bit (Turn ON)

function setBit(n, i) {
  return n | (1 << i);
}

// Turn ON bit 1 in number 4
// 4 = 0100 → 0110 = 6
setBit(4, 1);  // 6

Technique 3: Clear a Bit (Turn OFF)

function clearBit(n, i) {
  return n & ~(1 << i);
}

// Turn OFF bit 2 in number 5
// 5 = 0101 → 0001 = 1
clearBit(5, 2);  // 1

Technique 4: Toggle a Bit (Flip)

function toggleBit(n, i) {
  return n ^ (1 << i);
}

// Flip bit 0 in number 4
// 4 = 0100 → 0101 = 5
toggleBit(4, 0);  // 5

📊 Count Set Bits

Problem: How many switches are ON in a number?

Method 1: Loop Through Each Bit

function countSetBits(n) {
  let count = 0;
  while (n > 0) {
    count += n & 1;  // Check last bit
    n = n >> 1;      // Move to next bit
  }
  return count;
}

countSetBits(7);   // 7 = 0111 → 3 bits
countSetBits(10);  // 10 = 1010 → 2 bits

Method 2: Brian Kernighan’s Trick ⚡

Magic idea: n & (n-1) removes the rightmost 1-bit!

function countSetBitsFast(n) {
  let count = 0;
  while (n > 0) {
    n = n & (n - 1);  // Remove last 1
    count++;
  }
  return count;
}

// How it works with 7 (0111):
// Step 1: 0111 & 0110 = 0110 (count=1)
// Step 2: 0110 & 0101 = 0100 (count=2)
// Step 3: 0100 & 0011 = 0000 (count=3)
// Done! Answer: 3

✨ Power of Two Check

Problem: Is this number a power of 2? (like 1, 2, 4, 8, 16…)

Secret: Powers of 2 have exactly ONE bit set!

1  = 0001  ✓ One bit
2  = 0010  ✓ One bit
4  = 0100  ✓ One bit
8  = 1000  ✓ One bit
6  = 0110  ✗ Two bits

The One-Line Magic:

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

// Why does this work?
// 8     = 1000
// 8 - 1 = 0111
// 1000 & 0111 = 0000 ✓ Power of 2!

// 6     = 0110
// 6 - 1 = 0101
// 0110 & 0101 = 0100 ≠ 0 ✗ Not power of 2

🔍 Single Number XOR

Problem: In an array where every number appears twice except one, find the unique number!

XOR Magic Properties:

a ^ a = 0    (same numbers cancel out!)
a ^ 0 = a    (zero doesn't change anything)

Solution:

function singleNumber(nums) {
  let result = 0;
  for (let num of nums) {
    result ^= num;
  }
  return result;
}

// Example: [4, 1, 2, 1, 2]
// 0 ^ 4 = 4
// 4 ^ 1 = 5
// 5 ^ 2 = 7
// 7 ^ 1 = 6  (1 cancelled!)
// 6 ^ 2 = 4  (2 cancelled!)
// Answer: 4 ✓

🔬 Single Number II

Problem: Every number appears THREE times except one. Find the unique one!

Idea: Count bits at each position. If count % 3 ≠ 0, that bit belongs to our answer!

function singleNumberII(nums) {
  let result = 0;

  for (let i = 0; i < 32; i++) {
    let bitSum = 0;

    // Count 1s at position i
    for (let num of nums) {
      bitSum += (num >> i) & 1;
    }

    // If not divisible by 3, it's our number's bit
    if (bitSum % 3 !== 0) {
      result |= (1 << i);
    }
  }

  return result;
}

// Example: [2, 2, 3, 2]
// Bit 0: 0+0+1+0 = 1 → 1 % 3 = 1 → Set bit 0
// Bit 1: 1+1+1+1 = 4 → 4 % 3 = 1 → Set bit 1
// Result: 11 = 3 ✓

🎯 Missing Number using XOR

Problem: Array has numbers 0 to n, but ONE is missing. Find it!

Clever Idea: XOR all numbers AND all indices. Pairs cancel, leaving the missing one!

function missingNumber(nums) {
  let result = nums.length;  // Start with n

  for (let i = 0; i < nums.length; i++) {
    result ^= i ^ nums[i];
  }

  return result;
}

// Example: [3, 0, 1] (missing 2)
// result = 3
// i=0: 3 ^ 0 ^ 3 = 0
// i=1: 0 ^ 1 ^ 0 = 1
// i=2: 1 ^ 2 ^ 1 = 2 ✓ Missing!

Why this works:

XOR everything:
(0 ^ 1 ^ 2 ^ 3) ^ (3 ^ 0 ^ 1)
  ↑ expected      ↑ actual

= 0^0 ^ 1^1 ^ 2 ^ 3^3
= 0 ^ 0 ^ 2 ^ 0
= 2 ← The missing number!

🎓 Summary: Your Bit Manipulation Toolkit

graph LR
    A["Bit Operations"] --> B["AND &"]
    A --> C["OR |"]
    A --> D["XOR ^"]
    A --> E["NOT ~"]
    A --> F["Left Shift <<"]
    A --> G["Right Shift >>"]

    H["Common Tricks"] --> I["Check Bit"]
    H --> J["Set Bit"]
    H --> K["Clear Bit"]
    H --> L["Toggle Bit"]

    M["Classic Problems"] --> N["Count Set Bits"]
    M --> O["Power of Two"]
    M --> P["Single Number"]
    M --> Q["Missing Number"]

🏆 Quick Reference Card

You did it! 🎉 You now speak the secret language of computers. Every time you toggle a bit, you’re talking directly to the machine’s heart—tiny switches flipping on and off, creating the digital world we live in.

Keep practicing, and these operations will become second nature!