☕ DSA Java Articles

Topics › Tries › Problems

Bit PreRequisites for TRIE Problems

Easy TUF ID 2390 A2Z

Java source ↗ Edit this article ↗

What this covers

The last two problems of the trie section, maximum XOR of two numbers and maximum XOR under a limit, store numbers in a trie instead of words. Each number is written as a fixed-length string of bits, and the trie branches on 0 or 1 at every level. To follow those solutions you need five small ideas, and this article covers each one with code that the Java file tests:

  1. Writing every number with the same number of bits, so that level d of the trie always means the same bit.
  2. Reading, setting, clearing and toggling bit i with shifts and masks.
  3. What XOR does, bit by bit, and its algebraic properties.
  4. Why the highest differing bit decides which of two numbers is larger. This is what makes a greedy walk correct.
  5. How these combine into a binary trie that finds the best XOR partner in 31 steps.

Numbers as fixed-length bit strings

A Java int is 32 bits. Bit i has weight 2^i and is counted from the right, starting at 0. So 13 = 8 + 4 + 1 is 1101: bits 3, 2 and 0 are set, bit 1 is not. Bit 31 is the sign bit in two’s complement, which is why -1 is 32 ones and Integer.MIN_VALUE is a single 1 followed by 31 zeros. Printing all 32 positions, most significant first, is a loop that reads one bit per step:

static String toBinary32(int n) {
    StringBuilder sb = new StringBuilder();
    for (int i = 31; i >= 0; i--) {
        sb.append((n >> i) & 1);
    }
    return sb.toString();
}

Why fixed length matters for a trie. A word trie compares letter 1 with letter 1, letter 2 with letter 2, and so on. A bit trie must do the same with bit positions. If 5 were stored as 101 and 25 as 11001, the first level would compare bit 2 of 5 with bit 4 of 25, which means nothing. Padding every number to the same width with leading zeros puts the same bit at the same depth for every number: the root’s children split on the highest bit, the next level on the next one, and so on down to bit 0.

How deep must the trie be? Deep enough for the largest value. For non-negative int inputs bit 31 is always 0, so bits 30 down to 0 (31 levels) suffice. If values are at most 10^9, which is below 2^30, 30 levels are enough. The number of bits needed for values up to maxValue comes from the count of leading zeros:

static int bitsNeeded(int maxValue) {
    return Math.max(1, 32 - Integer.numberOfLeadingZeros(maxValue));
}

Reading and writing one bit

All four single-bit operations use the mask 1 << i, the number with only bit i set.

static int getBit(int n, int i) {
    return (n >> i) & 1;                               // bring bit i down to position 0, mask the rest away
}

static int setBit(int n, int i) {
    return n | (1 << i);                               // OR with the mask turns bit i on
}

static int clearBit(int n, int i) {
    return n & ~(1 << i);                              // AND with the inverted mask turns bit i off
}

static int toggleBit(int n, int i) {
    return n ^ (1 << i);                               // XOR with the mask flips bit i and nothing else
}

Worked on 13 = 1101:

Call Mask Result Binary
getBit(13, 2) 0100 1  
getBit(13, 1) 0010 0  
setBit(13, 1) 0010 15 1111
clearBit(13, 2) 1011 (inverted) 9 1001
toggleBit(13, 0) 0001 12 1100

A trie walk builds its answer the other way round, one bit at a time from the top. Shifting the partial value left and OR-ing in the next bit appends that bit, the binary version of “multiply by 10 and add the digit”:

static int fromBits(int[] bitsHighToLow) {
    int value = 0;
    for (int b : bitsHighToLow) {
        value = (value << 1) | b;
    }
    return value;
}

In the trie solutions the same thing appears as result |= 1 << b whenever bit b of the answer turns out to be 1.

XOR, the operator behind every problem here

XOR (^) works on each bit position independently. A result bit is 1 when the two input bits differ and 0 when they are equal:

a b a ^ b
0 0 0
0 1 1
1 0 1
1 1 0

So 5 ^ 3 = 0101 ^ 0011 = 0110 = 6. Spelled out with the helpers above, XOR is “set bit i wherever the two inputs differ”:

static int xorBitByBit(int a, int b) {
    int result = 0;
    for (int i = 31; i >= 0; i--) {
        if (getBit(a, i) != getBit(b, i)) result = setBit(result, i);
    }
    return result;
}

The properties used over and over:

For maximising XOR, the property that matters is the truth table itself. To make bit i of x ^ y equal to 1, y must have the opposite bit to x at position i:

static int wantedBit(int x, int i) {
    return 1 - getBit(x, i);
}

Why the highest bit decides everything

Compare two non-negative numbers by scanning their bits from the top. At the first position where they differ, the number with the 1 is larger, whatever the lower bits are. The reason is one inequality: bit i is worth 2^i, and all the bits below it together are worth at most 2^(i-1) + ... + 2 + 1 = 2^i - 1, which is less. One higher bit outweighs every lower bit combined.

static int compareByBits(int a, int b) {
    for (int i = 30; i >= 0; i--) {
        int x = getBit(a, i), y = getBit(b, i);
        if (x != y) return x - y;                      // 2^i outweighs all lower bits together (2^i - 1)
    }
    return 0;
}

The Java file checks that this agrees with Integer.compare on every pair from a list of values, including 8 against 7, where 1000 beats 0111 although 7 has more ones.

The consequence is the greedy rule. When building x ^ y to be as large as possible, decide the bits from the top down. If some candidate y can make the current bit 1, choose it, and keep only the candidates that agree with every choice made so far. Choosing a 0 there in the hope of more 1s further down can never pay off, because those lower bits are worth less than the one given up. Each level then needs a single question: “among the numbers still possible, does any have the opposite bit here?” Answering that quickly is exactly what a trie does.

Putting it together: the binary trie

A binary trie node has two children, one for bit 0 and one for bit 1. Inserting a number walks its 31 bits from bit 30 down, creating nodes as needed, just like inserting a 31-letter word over the alphabet {0, 1}:

static class BitNode {
    final BitNode[] child = new BitNode[2];
}

static void insert(BitNode root, int x) {
    BitNode cur = root;
    for (int i = 30; i >= 0; i--) {
        int bit = getBit(x, i);
        if (cur.child[bit] == null) cur.child[bit] = new BitNode();
        cur = cur.child[bit];
    }
}

The query applies the greedy rule. At each level it prefers the child with the opposite bit; if that child is missing, every remaining number has the same bit as x there, so that bit of the XOR is forced to 0 and the walk follows the only child. All stored numbers have full-length paths, so whenever the preferred child is missing the other one exists.

static int maxXor(BitNode root, int x) {
    BitNode cur = root;
    int result = 0;
    for (int i = 30; i >= 0; i--) {
        int want = wantedBit(x, i);
        if (cur.child[want] != null) {
            result = setBit(result, i);                // this bit of the XOR can be 1
            cur = cur.child[want];
        } else {
            cur = cur.child[1 - want];                 // forced: this bit of the XOR is 0
        }
    }
    return result;
}

Worked example. Store {3, 10, 5, 25, 2, 8} and query x = 5. All values are below 32, so bits 30 to 5 are 0 everywhere and the walk passes through them without gaining anything. The interesting bits are 4 to 0, with x = 00101:

Bit x’s bit Wanted Branch exists? Numbers still possible result
4 0 1 yes (25) {25} 10000
3 0 1 yes {25} 11000
2 1 0 yes {25} 11100
1 0 1 no, forced to 0 {25} 11100
0 1 0 no, forced to 0 {25} 11100

The answer is 11100 = 28 = 5 ^ 25, found in one pass of 31 levels instead of trying all six partners. The Java file confirms the walk against brute force on 300 random queries over 300 random numbers.

Pitfalls