Bitwise Operations for Low-Level Manipulation

Concept 1: The Building Blocks - Logical Bitwise Operations

At the lowest level, all data is just a sequence of bits (0s and 1s). Logical bitwise operators allow us to perform Boolean logic on each pair of corresponding bits in two numbers.

Technical Explanation

The four main logical bitwise operators are AND (&), OR (|), XOR (^), and NOT (~). They work by comparing the bits at each position in their binary representations.

• AND (&): Returns a 1 in a bit position only if both corresponding bits are 1.
• OR (|): Returns a 1 if either of the corresponding bits is 1.
• XOR (^): (Exclusive OR) Returns a 1 if the corresponding bits are different.
• NOT (~): A unary operator that flips all the bits of a single number (0 becomes 1, 1 becomes 0).

A crucial point in Python: integers are signed. The ~ operator behaves according to a number's two's complement representation, which is a standard way computers represent negative numbers. For a positive integer x, ~x will always result in -(x+1). For example, ~5 is -6.

Metaphor: A Panel of Light Switches

Imagine a number is a long panel of light switches, where 1 is "ON" and 0 is "OFF". You have two such panels, A and B, aligned one above the other.

• A & B: A new panel where a switch is ON only if the switches in both A and B at that same position were ON.
• A | B: A new panel where a switch is ON if the switch in either A or B (or both) was ON.
• A ^ B: A new panel where a switch is ON only if exactly one of the corresponding switches in A or B was ON, but not both.
• ~A: Take panel A and just flip every single switch to its opposite state.

Python Code Snippet

a = 92  # Binary: 01011100
b = 51  # Binary: 00110011

# AND: Common ON switches
print(f"a & b = {a & b:3d}  # Binary: {a & b:08b}") # 00010000 -> 16

# OR: Any ON switches
print(f"a | b = {a | b:3d}  # Binary: {a | b:08b}") # 01111111 -> 127

# XOR: Different switches
print(f"a ^ b = {a ^ b:3d}  # Binary: {a ^ b:08b}") # 01101111 -> 111

# NOT: Flip all switches
# Remember ~a = -(a+1) in Python
print(f"~a    = {~a:3d} # In two's complement: 10100011")

Concept 2: Shifting Bits for Power - The Shift Operators

Bit shifts move all bits in a number to the left or right. These are not just for repositioning bits; they are the low-level equivalent of multiplication and division by powers of two.

Technical Explanation

• Left Shift (<<): x << k shifts all bits in x to the left by k positions. The newly opened positions on the right are filled with zeros. This is equivalent to multiplying x by $2^k$. For example, 12 << 1 is 24.
• Right Shift (>>): x >> k shifts all bits in x to the right by k positions. The k rightmost bits are discarded. This is equivalent to the integer division of x by $2^k$. For example, 13 >> 1 is 6.

A critical distinction for right shifts is how the new bits on the left are filled. This depends on whether the shift is arithmetic or logical.

• Logical Right Shift: Always fills the new left-side bits with 0.
• Arithmetic Right Shift: Fills the new left-side bits by copying the original sign bit (the most significant bit). This preserves the number's sign. If the number is positive (sign bit 0), it fills with 0s. If negative (sign bit 1), it fills with 1s.

Python's >> operator performs an arithmetic right shift. This ensures that x >> k behaves like x // (2**k) for both positive and negative numbers.

Metaphor: Sliding Seats on a Bus

Imagine bits are people sitting in seats on a bus.

• Left Shift (<< k): Everyone slides k seats to the left. k new empty seats appear on the right, and they are filled by new passengers (zeros). The k people on the very left fall off the bus.
• Arithmetic Right Shift (>> k): Everyone slides k seats to the right. The k people on the very right fall off. To fill the k new empty seats on the left, we look at the person who was originally in the driver's seat (the sign bit). If they were happy (0 for positive), we fill the empty seats with happy people (0s). If they were grumpy (1 for negative), we fill the empty seats with grumpy people (1s) to maintain the mood of the bus.

Python Code Snippet

x = 21  # Binary: 00010101

# Left shift by 2 (multiply by 2^2 = 4)
# 00010101 -> 01010100
print(f"x << 2 = {x << 2}  # Expected: {21 * 4}")

# Right shift by 2 (integer divide by 2^2 = 4)
# 00010101 -> 00000101
print(f"x >> 2 = {x >> 2}  # Expected: {21 // 4}")

# Arithmetic right shift on a negative number
y = -21
# -21 // 4 = -6
print(f"y >> 2 = {y >> 2}  # Expected: {-21 // 4}")

Concept 3: Precision Surgery - Bitmasking

Bitmasking is the technique of using bitwise operations to selectively read or modify specific bits within a number, leaving the others untouched. This is one of the most common and powerful applications of bitwise logic.

Technical Explanation

A bitmask is a specially crafted number used to target specific bits. By combining this mask with a logical or shift operator, we can perform precise manipulations.

1. Get a bit (Check if a bit is set): To check the $i$-th bit, we create a mask with only the $i$-th bit set (1 << i). Then we AND it with the number. If the result is non-zero, the bit was set.
   is_set = (number & (1 << i)) != 0
   A common optimization is to shift the number right and check the last bit: (number >> i) & 1 which gives you a clean 1 or 0.

2. Set a bit (Turn a bit ON): To force the $i$-th bit to 1, we OR the number with the mask 1 << i.
   number = number | (1 << i)

3. Clear a bit (Turn a bit OFF): To force the $i$-th bit to 0, we need a mask with every bit set except the $i$-th bit. We can create this by inverting our simple mask: ~(1 << i). Then we AND this with our number.
   number = number & ~(1 << i)

4. Toggle a bit (Flip a bit): To flip the $i$-th bit, we XOR the number with the mask 1 << i.
   number = number ^ (1 << i)

Metaphor: The Configuration Panel

Imagine your number represents a set of 8 boolean configuration flags for an application, stored in a single byte to save space. Bit 0 is enable_logging, bit 1 is use_https, bit 2 is show_debug_info, etc.

• Get bit 2: "Is the show_debug_info flag turned on?"
• Set bit 1: "I need to turn on use_https, without touching any other settings."
• Clear bit 0: "I need to turn off enable_logging."
• Toggle bit 2: "The user pressed a key to flip the show_debug_info setting."

Python Code Snippet

# Our 'configuration' byte
# 10101100 -> Logging OFF, Caching ON, DarkMode ON, ...
config = 0b10101100 
print(f"Initial Config: {config:08b}")

# 1. Get bit 3 (is DarkMode ON?)
# Mask: 1 << 3 -> 00001000
is_dark_mode = (config >> 3) & 1
print(f"Is DarkMode ON? {'Yes' if is_dark_mode else 'No'}")

# 2. Set bit 0 (Enable logging)
# Mask: 1 << 0 -> 00000001
config |= (1 << 0)
print(f"Enable Logging:   {config:08b}") # Becomes 10101101

# 3. Clear bit 6 (Disable caching)
# Mask: ~(1 << 6) -> ~(01000000) -> 10111111
config &= ~(1 << 6)
print(f"Disable Caching:  {config:08b}") # Becomes 00101101

# 4. Toggle bit 5 (Flip UI mode)
# Mask: 1 << 5 -> 00100000
config ^= (1 << 5)
print(f"Toggle UI Mode:   {config:08b}") # Becomes 00001101

Concept 4: The XOR Trick - Solving "Single Number"

Now let's apply this knowledge. The "Single Number" problem is a classic interview question where bitwise operations provide an elegant and highly efficient solution.

Technical Explanation

Problem: Given a non-empty array of integers, every element appears twice except for one. Find that single one.
Example: [4, 1, 2, 1, 2] -> The single number is 4.

Solution: The XOR operator has two key properties:

1. A number XORed with itself is zero: x ^ x = 0.
2. A number XORed with zero is itself: x ^ 0 = x.

If we XOR all the numbers in the array together, every number that appears twice will cancel itself out (a ^ b ^ a = (a ^ a) ^ b = 0 ^ b = b). The only number remaining will be the one that appeared just once.

This approach has a time complexity of $O(n)$ because we iterate through the array once, and a space complexity of $O(1)$ because we only use a single variable to store the accumulated XOR result. This is vastly more efficient than a hash map solution which would require $O(n)$ space.

Metaphor: The Light Switch Tally

Imagine a room with a bank of light switches, one for each possible number. A group of people enters. Each person who is part of a pair goes to their assigned switch and flips it twice (ending up in the original state). The one person who is alone goes to their switch and flips it only once. To find the "single" person, you just need to find the one switch that is in a different state from how it started. The final XOR result is like looking at the state of all switches simultaneously.

Python Code Snippet

def find_single_number(nums: list[int]) -> int:
    """
    Finds the single element in an array where every other element appears twice.
    """
    single = 0
    for num in nums:
        single ^= num
    return single

# Example
my_nums = [4, 1, 2, 9, 1, 4, 2]
print(f"The array is: {my_nums}")
print(f"The single number is: {find_single_number(my_nums)}") # Should be 9

Concept 5: Reversing the Flow - Solving "Reverse Bits"

This final problem combines bit shifting and masking to perform a complete transformation of a number's binary representation.

Technical Explanation

Problem: Reverse the bits of a given 32-bit unsigned integer.
Example: Input n = 43261596 (binary 00000010100101000001111010011100) should become 964176192 (binary 00111001011110000010100101000000).

Solution: We can build the reversed number bit by bit.

1. Initialize a result to 0.
2. Loop 32 times (for a 32-bit integer).
3. In each loop:
   a. Left-shift the result by 1 (result <<= 1). This "makes room" for the next bit from the input.
   b. Get the last bit of the input number n using a mask: n & 1.
   c. Add (or OR) this last bit to our result.
   d. Right-shift the input number n by 1 (n >>= 1) to discard the last bit and expose the next one for the following iteration.

Metaphor: Reversing a Stack of Books

Imagine you have a stack of books n, and you want to create a new stack result with the books in reverse order.

1. You take the top book from stack n (n & 1).
2. You want to place this book at the bottom of your new stack, result.
3. To do this, you magically lift the entire result stack (result <<= 1) and slide the new book underneath (| (n & 1)).
4. You discard the book you just moved from stack n (n >>= 1).
5. You repeat this process until stack n is empty.

Python Code Snippet

def reverse_bits(n: int) -> int:
    """
    Reverses the bits of a 32-bit unsigned integer.
    """
    result = 0
    for i in range(32):
        # Make space in the result for the next bit
        result <<= 1
        
        # Get the last bit of n
        last_bit = n & 1
        
        # Add it to the result
        result |= last_bit
        
        # Move to the next bit of n
        n >>= 1
        
    return result

# Example from problem description
n_in = 43261596
n_out = reverse_bits(n_in)
print(f"Input : {n_in} ({n_in:032b})")
print(f"Output: {n_out} ({n_out:032b})")

Conclusion

Today, we journeyed from high-level algorithms down to the bare metal. You learned how to directly manipulate the binary representation of numbers, a powerful skill for optimization and for solving a specific, but important, class of algorithmic puzzles.

Key Takeaways:

• Logical Operators (&, |, ^, ~): These are the fundamental tools for performing boolean logic on individual bits.
• Shift Operators (<<, >>): These provide a highly efficient way to multiply and divide by powers of two and to move bits into position.
• Bitmasking: The core technique of combining logical and shift operators to precisely get, set, clear, or toggle specific bits, enabling applications like managing configuration flags.
• The XOR Trick: The unique properties of XOR (x ^ x = 0) make it a perfect tool for problems involving pairs, like finding the single unique element in an array.
• Iterative Bit Building: Many complex bit manipulation problems, like reversing bits, can be solved by iteratively building a new number while deconstructing an old one, bit by bit.

Preview of the Next Lesson

Having covered algorithmic foundations from complexity analysis to sorting and now low-level bit manipulation, we are ready to build up. In the next module, we'll start our exploration of Linear Data Structures. Our first lesson will be: Implement dynamic arrays with automatic resizing and analyze the amortized cost of insertions. We'll see how a simple array can be made flexible and powerful, and in doing so, we'll encounter another crucial concept in algorithm analysis: amortized complexity.