⚡ Bit Manipulation – Comprehensive Study Guide

**Bit Manipulation** is a technique used to perform operations at the **bit level**. It is widely used in **competitive programming, encryption, networking, and optimizing algorithms**.

📌 Why is Bit Manipulation Important?

  • 🚀 **Faster Computation** – Performs **operations in O(1) time**.
  • ⚡ **Memory Efficient** – Uses **less space** compared to integer operations.
  • 🔢 **Used in Low-Level Programming** – Involves direct **hardware interaction**.
  • 📡 **Efficient in Cryptography & Networking** – Used in **data encryption** & **checksum calculations**.

🔢 Understanding Binary Representation

Every number in a computer is stored in **binary form (0s and 1s)**. Example: 


                Decimal:  5  →  Binary: 101
                Decimal: 10  →  Binary: 1010

🛠️ Common Bitwise Operators

Operator Symbol Description Example (5 & 3)
AND & Returns 1 if both bits are 1 101 & 011 = 001 (1)
OR | Returns 1 if at least one bit is 1 101 | 011 = 111 (7)
XOR ^ Returns 1 if the bits are different 101 ^ 011 = 110 (6)
NOT ~ Flips all bits ~5 = -6 (in 2’s complement)
Left Shift << Shifts bits to the left (multiplies by 2) 5 << 1 = 10
Right Shift >> Shifts bits to the right (divides by 2) 5 >> 1 = 2

⚡ Important Bit Manipulation Tricks

✅ 1. Check if a Number is Even or Odd

Use the **AND operator**:


                bool isEven(int n) {
                    return (n & 1) == 0; // If last bit is 0, the number is even
                }

✅ 2. Check if a Number is a Power of 2

Only **one bit** is set in powers of 2.


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

✅ 3. Count the Number of 1s in Binary (Hamming Weight)

Uses Brian Kernighan’s Algorithm.


                int countSetBits(int n) {
                    int count = 0;
                    while (n) {
                        n = n & (n - 1); // Removes the rightmost set bit
                        count++;
                    }
                    return count;
                }

✅ 4. Reverse Bits of a Number


                uint32_t reverseBits(uint32_t n) {
                    uint32_t result = 0;
                    for (int i = 0; i < 32; i++) {
                        result = (result << 1) | (n & 1);
                        n = n >> 1;
                    }
                    return result;
                }

✅ 5. Swap Two Numbers Without Using a Third Variable


                void swap(int &a, int &b) {
                    a = a ^ b;
                    b = a ^ b;
                    a = a ^ b;
                }

⏳ Time Complexity Analysis

Operation Time Complexity
Bitwise AND, OR, XOR O(1)
Checking Even/Odd O(1)
Finding Power of 2 O(1)
Counting Set Bits O(log n)
Reversing Bits O(32) = O(1)

🌍 Real-World Applications of Bit Manipulation

  • 📡 **Network Protocols** – Bitwise operations in **IP addresses & compression.**
  • 🔑 **Cryptography** – Encrypting & decrypting data using bit operations.
  • ⚡ **Graphics & Game Development** – Efficient color manipulation & animations.
  • 📉 **Stock Market Analysis** – Storing data in compact form.
  • 🖥️ **Operating Systems & Hardware** – CPU registers, cache optimization.

🔗 Next Topics