Bit Manipulation - Advanced Techniques

Master bit manipulation techniques, bitwise operations, bit masking, and advanced binary algorithms for competitive programming and interviews.

Understanding Bit Manipulation

Bit manipulation is the art of manipulating individual bits and using them to solve problems efficiently. It's a crucial skill in competitive programming and technical interviews because bitwise operations are significantly faster than arithmetic operations and can solve problems in elegant ways.

Bitwise Operations Fundamentals

AND (&) Operation

Example

1010 (A) & 1100 (B) ------ 1000 (Result: 1 only where both bits are 1)

C++ Implementation:

cpp example

#include <iostream>
using namespace std;

int main() {
    int a = 10, b = 12;  // Binary: 1010, 1100
    int result = a & b;   // Result: 1000 (8)
    cout << result << endl;  // Output: 8
    return 0;
}

OR (|) Operation

Example

1010 (A) | 1100 (B) ------ 1110 (Result: 1 where at least one bit is 1)

XOR (^) Operation

Example

1010 (A) ^ 1100 (B) ------ 0110 (Result: 1 where bits differ)

Python Example:

python example

a = 10  # 1010
b = 12  # 1100
print(a ^ b)  # Output: 6 (0110)

# XOR properties
# a ^ a = 0
# a ^ 0 = a
# a ^ b = b ^ a (commutative)

NOT (~) Operation

Flips all bits in a number.

Left Shift (<<) and Right Shift (>>)

Example

1010 << 1 = 10100 (multiply by 2) 1010 >> 1 = 101 (divide by 2)

Common Bit Manipulation Techniques

1. Check if Bit is Set

python example

def is_bit_set(n, i):
    """Check if i-th bit is set (1)"""
    return (n & (1 << i)) != 0

# Example
num = 10  # 1010
print(is_bit_set(num, 0))  # False (last bit is 0)
print(is_bit_set(num, 1))  # True  (second bit is 1)

2. Set a Bit

python example

def set_bit(n, i):
    """Set i-th bit to 1"""
    return n | (1 << i)

# Example: 10 (1010) -> set bit 0 -> 11 (1011)
print(set_bit(10, 0))  # Output: 11

3. Clear/Unset a Bit

python example

def clear_bit(n, i):
    """Clear i-th bit (set to 0)"""
    mask = ~(1 << i)
    return n & mask

# Example: 10 (1010) -> clear bit 1 -> 8 (1000)
print(clear_bit(10, 1))  # Output: 8

4. Toggle a Bit

python example

def toggle_bit(n, i):
    """Toggle i-th bit"""
    return n ^ (1 << i)

# Example: 10 (1010) -> toggle bit 0 -> 11 (1011)
print(toggle_bit(10, 0))  # Output: 11

5. Count Set Bits

python example

def count_set_bits(n):
    """Count number of 1s in binary representation"""
    count = 0
    while n:
        count += n & 1
        n >>= 1
    return count

# More efficient: Brian Kernighan's Algorithm
def count_set_bits_optimized(n):
    count = 0
    while n:
        n &= n - 1  # Remove rightmost 1 bit
        count += 1
    return count

# Example
print(count_set_bits(10))  # 1010 -> 2 ones
print(count_set_bits_optimized(10))  # Output: 2

6. Check Power of Two

python example

def is_power_of_two(n):
    """Check if number is power of 2"""
    # Power of 2 has only one set bit
    # n & (n-1) removes the rightmost 1 bit
    return n > 0 and (n & (n - 1)) == 0

# Examples
print(is_power_of_two(8))   # True (1000)
print(is_power_of_two(10))  # False (1010)

ASCII Art: Bit Manipulation Visual

Example

Bit Positions: 7 6 5 4 3 2 1 0 Number 42: 0 0 1 0 1 0 1 0 ↓ ↓ ↓ 1 1 1 (32) (8) (2) Bitwise AND Operation: 42 (00101010) & 15 (00001111) ----------- 10 (00001010) Bitwise XOR Application - Find Single Number: [1, 2, 2, 3, 3] 1 ^ 2 = 3 3 ^ 2 = 1 1 ^ 3 = 2 2 ^ 3 = 1 <- Answer!

Common Interview Problems

Problem 1: Single Number

Find the element that appears once when others appear twice.

Solution:

java example

public class Solution {
    public int singleNumber(int[] nums) {
        int result = 0;
        for (int num : nums) {
            result ^= num;  // XOR all numbers
        }
        return result;
    }
}
// Time: O(n), Space: O(1)

Problem 2: Number of 1 Bits

Count the number of 1s in binary representation.

Solution:

python example

def hammingWeight(n):
    """Count 1 bits (also called Hamming weight)"""
    count = 0
    while n:
        count += n & 1
        n >>= 1
    return count

# Test
print(hammingWeight(11))  # 1011 -> 3

Problem 3: Reverse Bits

Reverse bits of a 32-bit unsigned integer.

Solution:

python example

def reverseBits(n):
    result = 0
    for i in range(32):
        result = (result << 1) | (n & 1)
        n >>= 1
    return result

# Time: O(1), Space: O(1)

Time and Space Complexity Table

Operation	Time	Space	Notes
Check bit set	O(1)	O(1)	Direct comparison
Set/Clear/Toggle	O(1)	O(1)	Single bitwise op
Count set bits	O(log n)	O(1)	Depends on algorithm
Power of two check	O(1)	O(1)	Single AND operation
Reverse bits	O(32) = O(1)	O(1)	Fixed iterations

Real-World Applications

Permissions & Flags: Use bits to store multiple boolean flags efficiently
IP Addressing: Subnet masks and CIDR notation use bit manipulation
Graphics & Games: Color values (RGB), pixel manipulation
Cryptography: XOR operations in encryption algorithms
Compression: Huffman coding uses bit-level manipulation
Memory Optimization: Storing multiple booleans in single integer

Interview Questions & Answers

Q1: What's the difference between >> and >>>? A: >> is arithmetic shift (sign-extends for negative), >>> is logical shift (fills with 0s). In Python and Java, >> is arithmetic and >>> is logical.

Q2: How to swap two numbers without third variable? A: Use XOR: a = a ^ b; b = a ^ b; a = a ^ b;

Q3: What's the significance of n & (n-1)? A: It clears the rightmost set bit. Useful for checking powers of 2 or counting set bits efficiently.

Q4: How to multiply/divide by 2 using bit shift? A: Multiply: n << 1; Divide: n >> 1

Q5: What's a bitmask and why use it? A: A bitmask uses individual bits to represent boolean states. It's memory-efficient and enables fast operations using bitwise operations.

Understanding Bit Manipulation

Bitwise Operations Fundamentals

AND (&) Operation

Example

1010 (A) & 1100 (B) ------ 1000 (Result: 1 only where both bits are 1)

C++ Implementation:

cpp example

#include <iostream>
using namespace std;

int main() {
    int a = 10, b = 12;  // Binary: 1010, 1100
    int result = a & b;   // Result: 1000 (8)
    cout << result << endl;  // Output: 8
    return 0;
}

OR (|) Operation

Example

1010 (A) | 1100 (B) ------ 1110 (Result: 1 where at least one bit is 1)

XOR (^) Operation

Example

1010 (A) ^ 1100 (B) ------ 0110 (Result: 1 where bits differ)

Python Example:

python example

a = 10  # 1010
b = 12  # 1100
print(a ^ b)  # Output: 6 (0110)

# XOR properties
# a ^ a = 0
# a ^ 0 = a
# a ^ b = b ^ a (commutative)

NOT (~) Operation

Flips all bits in a number.

Left Shift (<<) and Right Shift (>>)

Example

1010 << 1 = 10100 (multiply by 2) 1010 >> 1 = 101 (divide by 2)

Common Bit Manipulation Techniques

1. Check if Bit is Set

python example

def is_bit_set(n, i):
    """Check if i-th bit is set (1)"""
    return (n & (1 << i)) != 0

# Example
num = 10  # 1010
print(is_bit_set(num, 0))  # False (last bit is 0)
print(is_bit_set(num, 1))  # True  (second bit is 1)

2. Set a Bit

python example

def set_bit(n, i):
    """Set i-th bit to 1"""
    return n | (1 << i)

# Example: 10 (1010) -> set bit 0 -> 11 (1011)
print(set_bit(10, 0))  # Output: 11

3. Clear/Unset a Bit

python example

def clear_bit(n, i):
    """Clear i-th bit (set to 0)"""
    mask = ~(1 << i)
    return n & mask

# Example: 10 (1010) -> clear bit 1 -> 8 (1000)
print(clear_bit(10, 1))  # Output: 8

4. Toggle a Bit

python example

def toggle_bit(n, i):
    """Toggle i-th bit"""
    return n ^ (1 << i)

# Example: 10 (1010) -> toggle bit 0 -> 11 (1011)
print(toggle_bit(10, 0))  # Output: 11

5. Count Set Bits

python example

def count_set_bits(n):
    """Count number of 1s in binary representation"""
    count = 0
    while n:
        count += n & 1
        n >>= 1
    return count

# More efficient: Brian Kernighan's Algorithm
def count_set_bits_optimized(n):
    count = 0
    while n:
        n &= n - 1  # Remove rightmost 1 bit
        count += 1
    return count

# Example
print(count_set_bits(10))  # 1010 -> 2 ones
print(count_set_bits_optimized(10))  # Output: 2

6. Check Power of Two

python example

def is_power_of_two(n):
    """Check if number is power of 2"""
    # Power of 2 has only one set bit
    # n & (n-1) removes the rightmost 1 bit
    return n > 0 and (n & (n - 1)) == 0

# Examples
print(is_power_of_two(8))   # True (1000)
print(is_power_of_two(10))  # False (1010)

ASCII Art: Bit Manipulation Visual

Example

Common Interview Problems

Problem 1: Single Number

Find the element that appears once when others appear twice.

Solution:

java example

public class Solution {
    public int singleNumber(int[] nums) {
        int result = 0;
        for (int num : nums) {
            result ^= num;  // XOR all numbers
        }
        return result;
    }
}
// Time: O(n), Space: O(1)

Problem 2: Number of 1 Bits

Count the number of 1s in binary representation.

Solution:

python example

def hammingWeight(n):
    """Count 1 bits (also called Hamming weight)"""
    count = 0
    while n:
        count += n & 1
        n >>= 1
    return count

# Test
print(hammingWeight(11))  # 1011 -> 3

Problem 3: Reverse Bits

Reverse bits of a 32-bit unsigned integer.

Solution:

python example

def reverseBits(n):
    result = 0
    for i in range(32):
        result = (result << 1) | (n & 1)
        n >>= 1
    return result

# Time: O(1), Space: O(1)

Time and Space Complexity Table

Operation	Time	Space	Notes
Check bit set	O(1)	O(1)	Direct comparison
Set/Clear/Toggle	O(1)	O(1)	Single bitwise op
Count set bits	O(log n)	O(1)	Depends on algorithm
Power of two check	O(1)	O(1)	Single AND operation
Reverse bits	O(32) = O(1)	O(1)	Fixed iterations

Real-World Applications

Permissions & Flags: Use bits to store multiple boolean flags efficiently
IP Addressing: Subnet masks and CIDR notation use bit manipulation
Graphics & Games: Color values (RGB), pixel manipulation
Cryptography: XOR operations in encryption algorithms
Compression: Huffman coding uses bit-level manipulation
Memory Optimization: Storing multiple booleans in single integer

Interview Questions & Answers

Q1: What's the difference between >> and >>>? A: >> is arithmetic shift (sign-extends for negative), >>> is logical shift (fills with 0s). In Python and Java, >> is arithmetic and >>> is logical.

Q2: How to swap two numbers without third variable? A: Use XOR: a = a ^ b; b = a ^ b; a = a ^ b;

Q3: What's the significance of n & (n-1)? A: It clears the rightmost set bit. Useful for checking powers of 2 or counting set bits efficiently.

Q4: How to multiply/divide by 2 using bit shift? A: Multiply: n << 1; Divide: n >> 1

Q5: What's a bitmask and why use it? A: A bitmask uses individual bits to represent boolean states. It's memory-efficient and enables fast operations using bitwise operations.

Understanding Bit Manipulation

Bitwise Operations Fundamentals

AND (&) Operation

OR (|) Operation

XOR (^) Operation

NOT (~) Operation

Left Shift (<<) and Right Shift (>>)

Common Bit Manipulation Techniques

1. Check if Bit is Set

2. Set a Bit

3. Clear/Unset a Bit

4. Toggle a Bit

5. Count Set Bits

6. Check Power of Two

ASCII Art: Bit Manipulation Visual

Common Interview Problems

Problem 1: Single Number

Problem 2: Number of 1 Bits

Problem 3: Reverse Bits

Time and Space Complexity Table

Real-World Applications

Interview Questions & Answers

Continue learning this concept

Understanding Bit Manipulation

Bitwise Operations Fundamentals

AND (&) Operation

OR (|) Operation

XOR (^) Operation

NOT (~) Operation

Left Shift (<<) and Right Shift (>>)

Common Bit Manipulation Techniques

1. Check if Bit is Set

2. Set a Bit

3. Clear/Unset a Bit

4. Toggle a Bit

5. Count Set Bits

6. Check Power of Two

ASCII Art: Bit Manipulation Visual

Common Interview Problems

Problem 1: Single Number

Problem 2: Number of 1 Bits

Problem 3: Reverse Bits

Time and Space Complexity Table

Real-World Applications

Interview Questions & Answers

Continue learning this concept