Blueprint 16: "Core Code Optimization" 🔬

1. The Mission Briefing: Unleashing the Power of Bits

"To achieve the final level of efficiency, we must go to the lowest level: manipulating the individual bits of data directly."

At the heart of every piece of data in a computer lies a sequence of binary digits – bits (0s and 1s). While high-level programming languages abstract this away, understanding and manipulating these bits directly can unlock incredibly efficient solutions for certain types of problems. This is the realm of Bit Manipulation.

2. The Analogy: The Light Switches

Bit Manipulation is like having a panel of individual light switches. Each switch represents a bit: 0 for off, 1 for on. Bitwise operators (&, |, ^, ~, <<, >>) are like the actions you can perform on these switches – turning them on, turning them off, or toggling their state. Operating directly at the bit level is significantly faster than performing traditional arithmetic operations, as it leverages the fundamental way computers process information.

3. The Architect's Toolkit: Bitwise Operators

A. Logical Bitwise Operators

Operator	Name	Description	Example (A=5, B=3)
&	AND	Sets bit to 1 if both bits are 1.	0101 & 0011 -> 0001 (1)
\|	OR	Sets bit to 1 if either bit is 1.	0101 \| 0011 -> 0111 (7)
^	XOR	Sets bit to 1 if bits are different.	0101 ^ 0011 -> 0110 (6)
~	NOT	Inverts all bits.	~0101 -> ...1010 (-6)

B. Bitwise Shift Operators

Operator	Name	Description	Example (A=5)
<<	Left Shift	Shifts bits left, padding with zeros. (x << k is x * 2^k)	0101 << 2 -> 10100 (20)
>>	Right Shift	Shifts bits right. (floor(x / 2^k))	0101 >> 1 -> 0010 (2)

4. The Power of Bitmasking

A bitmask is an integer used to manipulate specific bits in another integer. By crafting the right mask, you can perform complex checks in a single operation.

Check if i-th bit is set: target & (1 << i)
Set i-th bit: target | (1 << i)
Clear i-th bit: target & ~(1 << i)
Toggle i-th bit: target ^ (1 << i)

5. Applications

Representing Sets: An integer's bits can represent a subset of n elements. This allows for fast set operations using bitwise logic.

Iterating Subsets: You can loop from 0 to 2^n - 1 to generate and inspect every possible subset of n items.

def get_all_subsets(nums):
    n = len(nums)
    subsets = []
    for i in range(1 << n):  # Iterate from 0 to 2^n - 1
        current_subset = []
        for j in range(n):
            # Check if the j-th bit is set in i
            if (i >> j) & 1:
                current_subset.append(nums[j])
        subsets.append(current_subset)
    return subsets