Bit Operations

🔮 The Secret Language of Computers: Bit Manipulation

A Journey Into the Magical World of 1s and 0s

Imagine you have a secret code that uses only two symbols: 1 and 0. That’s exactly how computers talk! Every number, every letter, every picture on your phone is made of these tiny switches called bits.

Today, we’re going to learn how to speak this secret language and do magic tricks with numbers that would take normal math forever!

🌟 What is Bit Manipulation?

Think of a light switch. It can only be ON (1) or OFF (0). Now imagine you have 8 light switches in a row. Together, they can make 256 different patterns!

Light Switches:  [ON][OFF][ON][ON][OFF][OFF][ON][OFF]
As bits:           1   0   1   1   0   0   1   0
This equals:      128+0 +32+16+0  +0  +2 +0  = 178

Bit manipulation means playing with these switches directly—flipping them, checking them, or combining them in clever ways.

🛠️ The Six Magic Wands: Bitwise Operations

We have six special wands to manipulate bits. Let’s meet each one!

1. AND (&) — The “Both Must Agree” Wand

Two friends voting YES means both say yes.

Rule: 1 AND 1 = 1, everything else = 0

     1 0 1 1  (11)
AND  1 1 0 1  (13)
  =  1 0 0 1  (9)

Python:

result = 11 & 13  # Result: 9

Use it for: Checking if a specific bit is ON.

2. OR (|) — The “Anyone Can Say Yes” Wand

If either friend says yes, the answer is yes!

Rule: 0 OR 0 = 0, everything else = 1

    1 0 1 1  (11)
OR  1 1 0 1  (13)
 =  1 1 1 1  (15)

Python:

result = 11 | 13  # Result: 15

Use it for: Turning a specific bit ON.

3. XOR (^) — The “Disagreement” Wand

Only says YES when friends disagree!

Rule: Same = 0, Different = 1

     1 0 1 1  (11)
XOR  1 1 0 1  (13)
  =  0 1 1 0  (6)

Python:

result = 11 ^ 13  # Result: 6

Magic property: a ^ a = 0 and a ^ 0 = a

4. NOT (~) — The “Opposite Day” Wand

Every 1 becomes 0, every 0 becomes 1!

NOT 0 0 0 0 0 1 0 1  (5)
  = 1 1 1 1 1 0 1 0  (-6 in Python)

Python:

result = ~5  # Result: -6

5. Left Shift (<<) — The “Multiply by 2” Express

Push all bits left, add zeros on right.

    0 0 1 1  (3)
<<1 0 1 1 0  (6)  ← Doubled!
<<2 1 1 0 0  (12) ← Doubled again!

Python:

result = 3 << 1  # 3 × 2 = 6
result = 3 << 2  # 3 × 4 = 12

6. Right Shift (>>) — The “Divide by 2” Express

Push all bits right, bits fall off the edge.

    1 1 0 0  (12)
>>1 0 1 1 0  (6)   ← Halved!
>>2 0 0 1 1  (3)   ← Halved again!

Python:

result = 12 >> 1  # 12 ÷ 2 = 6
result = 12 >> 2  # 12 ÷ 4 = 3

🎩 Bit Manipulation Techniques

Now let’s learn some magic tricks!

Trick 1: Check if a Bit is ON

Want to know if bit position 2 is ON in number 5?

n = 5          # Binary: 101
pos = 2        # Check position 2
mask = 1 << pos  # Creates: 100

if n & mask:
    print("Bit is ON!")   # ✓ This runs!

Trick 2: Turn a Bit ON

n = 5          # Binary: 101
pos = 1        # Set position 1
n = n | (1 << pos)  # Now: 111 = 7

Trick 3: Turn a Bit OFF

n = 7          # Binary: 111
pos = 1        # Clear position 1
n = n & ~(1 << pos)  # Now: 101 = 5

Trick 4: Toggle a Bit (Flip It!)

n = 5          # Binary: 101
pos = 0        # Flip position 0
n = n ^ (1 << pos)  # Now: 100 = 4

🔢 Count Set Bits (Counting the 1s)

How many light switches are ON?

Number 13 = 1101 in binary
Count: 3 ones!

The Clever Way (Brian Kernighan’s Algorithm)

def count_bits(n):
    count = 0
    while n:
        n = n & (n - 1)  # Magic! Removes rightmost 1
        count += 1
    return count

print(count_bits(13))  # Output: 3

Why it works:

13   = 1101
13-1 = 1100
AND  = 1100 (one 1 removed!)

12   = 1100
12-1 = 1011
AND  = 1000 (another 1 removed!)

8    = 1000
8-1  = 0111
AND  = 0000 (last 1 removed!)

Total: 3 ones found!

⚡ Power of Two Check

Is a number a power of 2? (Like 1, 2, 4, 8, 16…)

The Secret: Powers of 2 have exactly ONE bit set!

1  = 0001  ✓
2  = 0010  ✓
4  = 0100  ✓
6  = 0110  ✗ (two bits!)
8  = 1000  ✓

The Magic Formula:

def is_power_of_two(n):
    return n > 0 and (n & (n - 1)) == 0

print(is_power_of_two(8))   # True
print(is_power_of_two(6))   # False

Why it works:

8   = 1000
8-1 = 0111
AND = 0000  ← Zero means power of 2!

6   = 0110
6-1 = 0101
AND = 0100  ← Not zero, not a power of 2!

🎭 Single Number (XOR Magic)

The Puzzle: Every number appears twice except one. Find the lonely number!

nums = [2, 3, 2, 4, 3]
# 2 appears twice, 3 appears twice
# 4 appears once — it's the answer!

The XOR Solution:

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

def find_single(nums):
    result = 0
    for num in nums:
        result = result ^ num
    return result

print(find_single([2, 3, 2, 4, 3]))  # Output: 4

The Magic:

0 ^ 2 = 2
2 ^ 3 = 1
1 ^ 2 = 3
3 ^ 4 = 7
7 ^ 3 = 4  ← The lonely number!

Pairs cancel out, leaving only the single number!

🎭🎭 Single Number II (Harder!)

Now every number appears THREE times except one!

nums = [2, 2, 3, 2]  # 3 is the lonely one!

The Bit Counting Trick:

For each bit position, count how many 1s. If not divisible by 3, that bit belongs to our answer!

def single_number_ii(nums):
    result = 0
    for i in range(32):
        bit_sum = 0
        for num in nums:
            bit_sum += (num >> i) & 1
        if bit_sum % 3:
            result |= (1 << i)
    return result

print(single_number_ii([2, 2, 3, 2]))  # Output: 3

🔍 Missing Number (XOR Detective)

The Case: Numbers 0 to n are in an array, but ONE is missing!

nums = [3, 0, 1]
# Should have: 0, 1, 2, 3
# Missing: 2!

XOR Detective Method:

XOR all numbers AND all indices. Pairs cancel, missing remains!

def find_missing(nums):
    n = len(nums)
    result = n  # Start with n (the largest index)

    for i in range(n):
        result ^= i ^ nums[i]

    return result

print(find_missing([3, 0, 1]))  # Output: 2

The Logic:

Index: 0  1  2  (plus 3 for length)
Array: 3  0  1

XOR everything:
3 ^ (0^3) ^ (1^0) ^ (2^1)
= 3 ^ 0 ^ 3 ^ 1 ^ 0 ^ 2 ^ 1
= (3^3) ^ (0^0) ^ (1^1) ^ 2
= 0 ^ 0 ^ 0 ^ 2
= 2  ← The missing number!

🏆 Why Bit Manipulation is Awesome

🎯 Quick Reference

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

    B --> B1["Both 1 → 1"]
    C --> C1["Any 1 → 1"]
    D --> D1["Different → 1"]
    E --> E1["Flip all"]
    F --> F1["Multiply by 2"]
    G --> G1["Divide by 2"]

🌈 You Did It!

You now speak the secret language of computers! You can:

• ✅ Use all 6 bitwise operators
• ✅ Count bits like a pro
• ✅ Check powers of 2 instantly
• ✅ Find lonely numbers with XOR magic
• ✅ Solve missing number puzzles

Remember: Bits are just light switches. Once you see numbers as patterns of ON and OFF, bit manipulation becomes as natural as flipping a switch!

Happy bit-flipping! 🚀