Section 7.1.3: Bitwise Tricks and Techniques

Exercise 196. [21] [21] (K. Thompson, 1992.) Integers in the range 0 ≤x < 231 can be encoded as a string of up to six bytes α(x) = α1 . . . αl in the following way: If x < 27, set l ←1 and α1 ←x. Otherwise let x = (x5 . . . x1x0)64; set l ←⌈(λx)/5⌉, α1 ←28−28−l+xl−1, and αj ←27 +xl−j for 2 ≤j ≤l. Notice that α(x) contains a zero byte if and only if x = 0. a) What are the encodings of #a, #3a3, #7b97, and #1d141? b) If x ≤x′, prove that α(x) ≤α(x′) in lexicographic order. c) Suppose a sequence of values x(1)x(2). . . x(n) has been encoded as a byte string α(x(1))α(x(2)) . . . α(x(n)), and let αk be the kth byte in that string. Show that it’s easy to determine the value x(i) from which αk came, by looking at a few of the neighboring bytes if necessary.

7.1.3 BITWISE TRICKS AND TECHNIQUES 201

Verified: no
Solve time: 4m31s

---

The solution must be rebuilt from the actual definitions, not from byte-range heuristics.

Encoding (correct interpretation)

Integers $0 \le x < 2^{31}$ are encoded as follows.

If $x < 2^7$, then $l = 1$ and $\alpha_1 = x$.

Otherwise write $x$ in base $32$:

$$ x = (x_{l-1},x_{l-2},\dots,x_0)_{32}, \qquad 0 \le x_i \le 31, $$

where

$$ l = \left\lceil \frac{\lambda x}{5} \right\rceil, $$

so each digit carries 5 bits.

Then:

$$ \alpha_1 = 2^8 - 2^{8-l} + x_{l-1}, \qquad \alpha_j = 2^7 + x_{l-j} \quad (2 \le j \le l). $$

Thus:

• continuation bytes are always $128 \le \alpha_j \le 159$,
• leading byte depends on $l$, in interval $[256-2^{8-l},,256-2^{8-l}+31]$.

(a) Explicit encodings

We convert each number to base $32$.

1. $x = #a = 0xA = 10$

Since $10 < 128$, $l = 1$:

$$ \alpha(x) = (10). $$

2. $x = #3a3 = 0x3a3 = 931$

Base 32:

$$ 931 = 29 \cdot 32 + 3 \Rightarrow (29,3), \quad l=2. $$

Now compute:

$$ \alpha_2 = 128 + 3 = 131, $$

$$ \alpha_1 = 256 - 2^{6} + 29 = 256 - 64 + 29 = 221. $$

So:

$$ \alpha(x) = (221,131). $$

3. $x = #7b97 = 0x7b97 = 31639$

Base 32:

$$ 31639 = 30 \cdot 32^2 + 28 \cdot 32 + 23, $$

so

$$ (x_2,x_1,x_0) = (30,28,23), \quad l=3. $$

Compute:

$$ \alpha_3 = 128 + 23 = 151, $$

$$ \alpha_2 = 128 + 28 = 156, $$

$$ \alpha_1 = 256 - 32 + 30 = 254. $$

So:

$$ \alpha(x) = (254,156,151). $$

4. $x = #1d141 = 0x1d141 = 119105$

Base 32:

$$ 119105 = 3 \cdot 32^3 + 20 \cdot 32^2 + 10 \cdot 32 + 1, $$

so

$$ (x_3,x_2,x_1,x_0) = (3,20,10,1), \quad l=4. $$

Compute continuation bytes:

$$ \alpha_4 = 128 + 1 = 129, $$

$$ \alpha_3 = 128 + 10 = 138, $$

$$ \alpha_2 = 128 + 20 = 148. $$

Leading byte:

$$ \alpha_1 = 256 - 2^{4} + 3 = 256 - 16 + 3 = 243. $$

So:

$$ \alpha(x) = (243,148,138,129). $$

(b) Lexicographic monotonicity

Assume $x \le x'$. We compare $\alpha(x)$ and $\alpha(x')$.

Step 1: different lengths

If $l < l'$, then:

$$ x < 2^{5l} \le x' \text{ (by definition of digit length)}. $$

More importantly, leading bytes satisfy:

$$ \alpha_1(x) \in [256 - 2^{8-l},,256 - 2^{8-l} + 31], $$

$$ \alpha_1(x') \ge 256 - 2^{8-l'}. $$

Since $l < l'$, we have:

$$ 2^{8-l} \ge 2^{8-l'} \cdot 2, $$

so every leading-byte interval for smaller $l$ lies strictly below that for larger $l$.

Thus:

$$ l < l' ;\Rightarrow; \alpha(x) < \alpha(x') \text{ lexicographically.} $$

Step 2: equal lengths

Assume $l = l'$. Then:

$$ \alpha_j = 128 + x_{l-j} \quad (j \ge 2), $$

and

$$ \alpha_1 = 256 - 2^{8-l} + x_{l-1}. $$

All components are strictly increasing functions of the corresponding base-32 digits.

Therefore the first position where $x$ and $x'$ differ is exactly the first position where $\alpha(x)$ and $\alpha(x')$ differ, with the same ordering.

Hence:

$$ x \le x' \Rightarrow \alpha(x) \le \alpha(x') \text{ lexicographically.} $$

(c) Recovering $x(i)$ from a byte $\alpha_k$

We show that the originating codeword can be identified using only a bounded number of neighboring bytes.

Key structural facts

1. Continuation bytes satisfy:

$$ 128 \le \alpha_j \le 159, $$

and are exactly the bytes of the form $128 + x_i$.

1. Leading bytes are in disjoint intervals depending on $l$:

$$ \alpha_1 \in [256 - 2^{8-l},,256 - 2^{8-l} + 31]. $$

1. Each codeword has length at most 6.

Step 1: locating the codeword boundary

Given $\alpha_k$:

• If $\alpha_k < 128$, it is a 1-byte codeword.
• If $\alpha_k \ge 128$, it is part of a multi-byte block.

To find the start:

Scan left until encountering a byte that is not a continuation byte.

Since codewords have length $\le 6$, this scan requires at most 5 steps.

Step 2: identifying the start byte

The first non-continuation byte to the left is the unique leading byte because:

• continuation bytes never appear outside a codeword,
• leading bytes are the only bytes that break the $128$-range pattern,
• and no continuation byte can equal a leading byte.

Thus the codeword boundary is unambiguous.

Step 3: reconstructing $x(i)$

Once the block $\alpha_1 \dots \alpha_l$ is known:

• If $l=1$: $x = \alpha_1$.
• If $l \ge 2$:

$$ x_{l-j} = \alpha_j - 128 \quad (j \ge 2), $$

$$ x_{l-1} = \alpha_1 - (256 - 2^{8-l}). $$

Finally:

$$ x = \sum_{i=0}^{l-1} x_i \cdot 32^i. $$

Conclusion

• The encodings follow a base-32 digit decomposition with 5-bit groups.
• Lexicographic order is preserved because both continuation and leading bytes are strictly increasing functions of digits and length produces disjoint leading intervals.
• Any byte belongs to a uniquely identifiable codeword, recoverable by scanning at most 5 neighboring bytes due to bounded block length.