Bit Operations

🔮 Bit Manipulation: The Secret Language of Computers

Imagine you have a row of light switches. Each switch is either ON (1) or OFF (0). That’s exactly how computers store and manipulate numbers!

🌟 The Light Switch Analogy

Think of bits like a row of light switches in your room:

• ON = 1 (there’s light!)
• OFF = 0 (it’s dark!)

A number like 5 in binary is: 101

• First switch: ON (1)
• Second switch: OFF (0)
• Third switch: ON (1)

Bit manipulation is like becoming a master electrician who can flip switches super fast!

🎯 Bit Manipulation Fundamentals

What Are Bits?

A bit is the smallest piece of information a computer can store. It’s like a tiny light bulb that’s either:

• 1 = ON = true = yes
• 0 = OFF = false = no

8 bits together make a byte (like 8 light switches in a row).

Why Learn Bit Manipulation?

1. Speed - Bit operations are the FASTEST things a computer can do
2. Memory - Store lots of flags in one tiny number
3. Puzzles - Many coding interview questions use bit tricks!

// Number 5 in binary
int five = 5;  // Binary: 101
// That's: 1×4 + 0×2 + 1×1 = 5

⚡ Bitwise Operations

These are the 6 superpowers you can use on bits!

1. AND (&) - “Both Must Be ON”

Like asking: “Are BOTH switches ON?”

5 & 3 = 1
//  101 (5)
//  011 (3)
// -----
//  001 (1) ← Only where BOTH are 1

2. OR (|) - “Either One Works”

Like asking: “Is AT LEAST ONE switch ON?”

5 | 3 = 7
//  101 (5)
//  011 (3)
// -----
//  111 (7) ← 1 if EITHER is 1

3. XOR (^) - “Only One, Not Both”

Like asking: “Is EXACTLY ONE switch ON?”

5 ^ 3 = 6
//  101 (5)
//  011 (3)
// -----
//  110 (6) ← 1 only when DIFFERENT

Magic Property: a ^ a = 0 (anything XOR itself = 0!)

4. NOT (~) - “Flip Everything”

Flip ALL switches! ON becomes OFF, OFF becomes ON.

~5 = -6
// Flips all 32 bits in Java

5. Left Shift (<<) - “Move Left, Add Zeros”

Slide all bits LEFT. Empty spots fill with 0.

5 << 1 = 10
// 101 becomes 1010
// It's like multiplying by 2!

6. Right Shift (>>) - “Move Right, Lose Bits”

Slide all bits RIGHT. Bits that fall off are gone!

5 >> 1 = 2
// 101 becomes 10 (which is 2)
// It's like dividing by 2!

🛠️ Bit Manipulation Techniques

Setting a Bit (Turn ON)

Want to turn ON the bit at position i?

int setBit(int n, int i) {
    return n | (1 << i);
}
// Example: setBit(5, 1)
// 5 = 101, position 1
// 1<<1 = 010
// 101 | 010 = 111 = 7

Clearing a Bit (Turn OFF)

Want to turn OFF the bit at position i?

int clearBit(int n, int i) {
    return n & ~(1 << i);
}
// Example: clearBit(7, 1)
// 7 = 111, clear position 1
// ~(1<<1) = ~010 = 101
// 111 & 101 = 101 = 5

Toggling a Bit (Flip It!)

Flip whatever it was to the opposite:

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

Checking a Bit

Is the bit at position i ON or OFF?

boolean checkBit(int n, int i) {
    return (n & (1 << i)) != 0;
}

🔢 Count Set Bits (Brian Kernighan’s Algorithm)

Question: How many light switches are ON in a number?

The Clever Trick

Instead of checking every bit, use this magic:

n & (n-1) removes the rightmost 1 bit!

int countSetBits(int n) {
    int count = 0;
    while (n != 0) {
        n = n & (n - 1);  // Remove one 1-bit
        count++;          // Count it!
    }
    return count;
}

Example with 7 (binary 111):

1. 7 & 6 = 111 & 110 = 110 (6) → count = 1
2. 6 & 5 = 110 & 101 = 100 (4) → count = 2
3. 4 & 3 = 100 & 011 = 000 (0) → count = 3

Answer: 3 bits are ON!

🎲 Power of Two Check

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

The Secret Pattern

Powers of 2 have exactly ONE bit turned ON:

• 1 = 001
• 2 = 010
• 4 = 100
• 8 = 1000

The Magic Formula

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

Why does this work?

• 8 = 1000
• 7 = 0111
• 8 & 7 = 0000 ✓ It’s a power of 2!

Compare with 6:

• 6 = 110
• 5 = 101
• 6 & 5 = 100 ✗ Not zero, not a power of 2!

🎭 Single Number XOR

The Puzzle: In an array where every number appears TWICE except one, find that single number!

int[] nums = {2, 3, 2, 4, 3};
// 4 appears only once!

The XOR Magic

Remember: a ^ a = 0 and a ^ 0 = a

int singleNumber(int[] nums) {
    int result = 0;
    for (int num : nums) {
        result ^= num;
    }
    return result;
}

How it works:

0 ^ 2 = 2
2 ^ 3 = 1
1 ^ 2 = 3  (2 cancels out!)
3 ^ 4 = 7
7 ^ 3 = 4  (3 cancels out!)

All pairs cancel to 0. Only the single number remains!

🎭🎭 Single Number II

Harder Puzzle: Every number appears THREE times except one!

int[] nums = {2, 2, 3, 2};
// 3 appears only once!

The Bit Counter Approach

Count how many times each bit position has a 1. If it’s not divisible by 3, that bit belongs to our single number!

int singleNumber(int[] nums) {
    int result = 0;
    for (int i = 0; i < 32; i++) {
        int sum = 0;
        for (int num : nums) {
            sum += (num >> i) & 1;
        }
        if (sum % 3 != 0) {
            result |= (1 << i);
        }
    }
    return result;
}

Think of it like this:

• Each 1-bit from numbers appearing 3 times totals to a multiple of 3
• The leftover 1s (not divisible by 3) belong to our single number!

🔍 Missing Number using XOR

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

int[] nums = {3, 0, 1};
// Missing: 2 (from 0, 1, 2, 3)

The XOR Solution

XOR all numbers from 0 to n, then XOR with all array elements. Pairs cancel out, leaving the missing one!

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

Step by step for {3, 0, 1}:

Start: result = 3 (the length)
i=0: 3 ^ 0 ^ 3 = 0
i=1: 0 ^ 1 ^ 0 = 1
i=2: 1 ^ 2 ^ 1 = 2 ← The missing number!

🚀 Quick Reference Table

🎓 Key Takeaways

1. Bits are just light switches - 1 is ON, 0 is OFF
2. XOR is magical - Same numbers cancel to zero
3. n & (n-1) removes the rightmost 1-bit
4. Powers of 2 have exactly one 1-bit
5. Left shift × 2, Right shift ÷ 2

You’ve now unlocked the secret language of computers!

These bit tricks are like magic spells that make your code run lightning fast. Every time you use n & (n-1) or XOR to find a single number, you’re speaking the computer’s native tongue!

graph LR
    A["Bit Manipulation"] --> B["Bitwise Operators"]
    A --> C["Common Problems"]
    B --> D["& AND"]
    B --> E["| OR"]
    B --> F["^ XOR"]
    B --> G["~ NOT"]
    B --> H["<< Left Shift"]
    B --> I[">> Right Shift"]
    C --> J["Count Set Bits"]
    C --> K["Power of Two"]
    C --> L["Single Number"]
    C --> M["Missing Number"]