Day 53: Bit Manipulation Techniques#

Welcome to Day 53 of our 60 Days of Coding Algorithm Challenge! Today, we’ll explore Bit Manipulation Techniques, a set of powerful tools that allow us to perform operations at the bit level, often leading to more efficient algorithms.

What is Bit Manipulation?#

Bit manipulation involves the use of bitwise operators to manipulate individual bits within a data type. These operations are often used to optimize performance, reduce memory usage, or solve certain types of problems more efficiently.

Basic Bitwise Operators#

1. AND (&): Returns 1 if both bits are 1, otherwise 0.
2. OR (|): Returns 1 if at least one bit is 1, otherwise 0.
3. XOR (^): Returns 1 if the bits are different, otherwise 0.
4. NOT (~): Inverts all the bits.
5. Left Shift («): Shifts bits to the left, filling with 0.
6. Right Shift (»): Shifts bits to the right, filling with the sign bit (arithmetic) or 0 (logical).

Common Bit Manipulation Techniques#

1. Check if a number is even or odd#

1def is_even(n):
2    return not (n & 1)
3
4# Example usage
5print(is_even(4))  # True
6print(is_even(7))  # False

2. Check if the i-th bit is set#

1def is_bit_set(n, i):
2    return bool(n & (1 << i))
3
4# Example usage
5print(is_bit_set(5, 0))  # True (5 is 101 in binary)
6print(is_bit_set(5, 1))  # False

3. Set the i-th bit#

1def set_bit(n, i):
2    return n | (1 << i)
3
4# Example usage
5print(bin(set_bit(5, 1)))  # 0b111 (7 in decimal)

4. Clear the i-th bit#

1def clear_bit(n, i):
2    return n & ~(1 << i)
3
4# Example usage
5print(bin(clear_bit(7, 1)))  # 0b101 (5 in decimal)

5. Toggle the i-th bit#

1def toggle_bit(n, i):
2    return n ^ (1 << i)
3
4# Example usage
5print(bin(toggle_bit(5, 1)))  # 0b111 (7 in decimal)

6. Count the number of set bits#

1def count_set_bits(n):
2    count = 0
3    while n:
4        count += n & 1
5        n >>= 1
6    return count
7
8# Example usage
9print(count_set_bits(7))  # 3 (7 is 111 in binary)

7. Find the rightmost set bit#

1def rightmost_set_bit(n):
2    return n & -n
3
4# Example usage
5print(bin(rightmost_set_bit(12)))  # 0b100

Advanced Bit Manipulation Techniques#

1. XOR Swap#

Swap two numbers without using a temporary variable:

 1def xor_swap(a, b):
 2    a ^= b
 3    b ^= a
 4    a ^= b
 5    return a, b
 6
 7# Example usage
 8x, y = 5, 10
 9x, y = xor_swap(x, y)
10print(x, y)  # 10 5

2. Isolate the rightmost 0 bit#

1def isolate_rightmost_zero_bit(n):
2    return ~n & (n + 1)
3
4# Example usage
5print(bin(isolate_rightmost_zero_bit(10)))  # 0b10 (10 is 1010 in binary)

3. Remove the last set bit#

1def remove_last_set_bit(n):
2    return n & (n - 1)
3
4# Example usage
5print(bin(remove_last_set_bit(14)))  # 0b1100 (12 in decimal)

4. Generate all possible subsets of a set#

 1def generate_subsets(s):
 2    subsets = []
 3    n = len(s)
 4    for i in range(1 << n):
 5        subset = [s[j] for j in range(n) if (i & (1 << j))]
 6        subsets.append(subset)
 7    return subsets
 8
 9# Example usage
10print(generate_subsets([1, 2, 3]))

Applications of Bit Manipulation#

1. Compression: Bit manipulation is used in various compression algorithms.
2. Cryptography: Many cryptographic algorithms rely heavily on bitwise operations.
3. Graphics: Image processing often involves bit-level operations for efficiency.
4. Network Protocols: IP addresses and subnet masks are often handled using bitwise operations.
5. Embedded Systems: In resource-constrained environments, bit manipulation can save memory and improve performance.

Exercise#

1. Implement a function to determine if a number is a power of 2 using bit manipulation.
2. Write a function to reverse the bits of a given 32-bit unsigned integer.
3. Implement a function to find the single number in an array where every element appears twice except for one.

Summary#

Today, we explored Bit Manipulation Techniques, a powerful set of tools for performing operations at the bit level. We covered basic bitwise operators, common bit manipulation techniques, and some advanced applications. These techniques are crucial for optimizing certain types of algorithms and are widely used in various fields of computer science and software engineering.

Understanding bit manipulation can lead to more efficient code and can be particularly useful in competitive programming, systems programming, and when working with low-level operations.

Solution#

 1# Exercise 1: Is n a power of 2? A positive power of 2 has exactly one set bit,
 2# so n & (n - 1) clears that bit and yields 0.
 3def is_power_of_two(n):
 4    return n > 0 and (n & (n - 1)) == 0
 5
 6# Exercise 2: Reverse the bits of a 32-bit unsigned integer.
 7def reverse_bits(n):
 8    result = 0
 9    for _ in range(32):
10        result = (result << 1) | (n & 1)  # Shift result, append n's low bit.
11        n >>= 1
12    return result
13
14# Exercise 3: Single number: every element appears twice except one.
15# XOR is associative and self-cancelling, so duplicates vanish.
16def single_number(nums):
17    result = 0
18    for x in nums:
19        result ^= x
20    return result
21
22print(is_power_of_two(16))                 # True
23print(is_power_of_two(18))                 # False
24print(reverse_bits(0b00000000000000000000000000000001))  # 2147483648
25print(single_number([4, 1, 2, 1, 2]))      # 4

Tomorrow, we’ll dive into the Power Set problem, which builds on some of the bit manipulation concepts we’ve learned today. Stay tuned!