L5: Bit Prerequisites for TRIE Problems

This chapter establishes the foundational bit-manipulation mechanics required to transition from standard string-based Trie problems to advanced bit-based Trie algorithms (such as finding maximum XOR pairs).

1. Why Do We Need Bit Manipulation in Tries?

• Transitioning Beyond Strings: Previous Trie problems focused on string prefix searches, character counts, and word insertion. The next phase of Trie problems combines Bit Manipulation and Tries to solve numeric optimization problems efficiently, most notably solving maximum XOR queries in logarithmic time.
• Computer-Level Representation: When dealing with integers in Trie structures, we cannot treat a number simply by its shorthand value (e.g., treating 9 as 11 in binary). Computers store integers fixed to a precise width—typically 32 bits for standard integers and 64 bits for long long types.

2. Core Mental Model: The 32-Bit Integer Array

When working with bit-level Tries, every number is viewed as a fixed-length binary sequence from index 0 to 31.

• Indexing Direction: Indexing runs from right to left, starting at 0 for the least significant bit (LSB) and ending at 31 for the most significant bit (MSB).
• Mathematical Weight:
  • The rightmost bit represents $2^0$.
  • The leftmost bits represent massive powers of two (up to $2^{31}$).
• Value Magnitude Rule: Numbers become significantly larger when bits are set on the left side (higher powers of two like $2^{28}$ or $2^{31}$) rather than the right side.

Index:    31 . . .    3        2        1        0
Binary:    0 0 . . .  0        0        1        0        1
Weight:   2^31        2^3      2^2      2^1      2^0

3. The XOR Operation Rule

The Exclusive-OR (XOR, denoted as ^) operator is central to bit-based Trie problems. Understanding its truth behavior is essential:

• Two-Operand Rule:
  • XOR of different bits yields 1.
  • XOR of similar bits yields 0.
• Multiple-Operand Rule (Parity):
  • If there are an even number of ones across the bits being XORed, the result is 0.
  • If there are an odd number of ones, the result is 1.

4. Checking If a Specific Bit Is Set

To check whether the bit at a specific index (e.g., the 3rd bit) of a number is 1 or 0, we use a combination of the Right Shift (>>) operator and the Bitwise AND (&) operator.

Step-by-Step Flow

1. Take the original number.
2. Right-shift the number by the target index positions (num >> index). This moves the target bit all the way to the 0th (rightmost) position.
3. Perform a bitwise AND with 1 ((num >> index) & 1).

Code Implementation (C++ / Java / Python Logic)

// Returns true if the bit at 'index' is set, false otherwise
bool checkBit(int num, int index) {
    if ((num & (1 << index)) != 0) {
        return true;
    }
    return false;
}

// Alternatively using right shift:
bool checkBitShift(int num, int index) {
    if (((num >> index) & 1) != 0) {
        return true;
    }
    return false;
}

5. Turning On (Setting) a Specific Bit

If a bit at a particular index is currently 0 and we need to force it to 1 without altering other bits, we use the Left Shift (<<) operator combined with the Bitwise OR (|) operator.

Step-by-Step Flow

1. Start with the number 1 (binary ...00001).
2. Left-shift 1 by the target index: 1 << index. This places a single 1 at the desired index position and zeros everywhere else.
3. Perform a bitwise OR between the original number and the shifted mask: num | (1 << index).

Code Implementation

// Turns on the bit at the specified index
int turnOnBit(int num, int index) {
    return num | (1 << index);
}

6. Summary of Bitwise Operators for Tries

7. Summary and Key Takeaways

• Fixed-Width Integers: Tries operating on numbers evaluate integers across fixed bit widths (32-bit for standard integers, 64-bit for longs) indexed right-to-left from 0 to 31.
• Significance of Left Bits: Higher powers of two reside on the left side; activating bits on the left results in substantially larger numeric values.
• XOR Fundamentals: XOR yields 1 for different bits and 0 for identical bits; parity rules dictate that an even number of ones yields 0 and an odd number yields 1.
• Bit Checking Formula: Use (num >> index) & 1 to isolate and verify whether a specific bit index is active (1) or inactive (0).
• Bit Setting Formula: Use num | (1 << index) to safely turn on a bit at any specific index position.
• Prerequisite Mastery: Mastering these five bit manipulation operations is mandatory before implementing advanced bitwise Trie algorithms.