TAOCP 7.1.3 Exercise 198

Let $l$ be the number of bytes in the UTF-8 encoding of $x$.

taocpmathematicsalgorithmsvolume-4medium

Section 7.1.3: Bitwise Tricks and Techniques

Exercise 198. ▶ [21] [21] Unicode characters are often represented as strings of bytes using a scheme called UTF-8, which is the encoding of exercise 196 restricted to integers in the range 0 ≤x < 220+216. Notice that UTF-8 efficiently preserves the standard ASCII character set (the codepoints with x < 27), and that it is quite different from UTF-16. Let α1 be the first byte of a UTF-8 string α(x). Show that there are reasonably small integer constants a, b, and c such that only four bitwise operations (a ≫((α1 ≫b) & c)) & 3 suffice to determine the number l −1 of bytes between α1 and the end of α(x).

Verified: no
Solve time: 1m40s

Let $l$ be the number of bytes in the UTF-8 encoding of $x$. Then the first byte $\alpha_1$ determines $l-1$ uniquely by the four cases

$$ \alpha_1 = 0xxxxxxx \Rightarrow l-1 = 0,\quad \alpha_1 = 110xxxxx \Rightarrow l-1 = 1,\quad \alpha_1 = 1110xxxx \Rightarrow l-1 = 2,\quad \alpha_1 = 11110xxx \Rightarrow l-1 = 3. $$

Set

$$ k = (\alpha_1 \gg 4). $$

Then

$$ 0xxxxxxx \Rightarrow k \in {0,\dots,7},\quad 110xxxxx \Rightarrow k \in {12,13},\quad 1110xxxx \Rightarrow k = 14,\quad 11110xxx \Rightarrow k = 15. $$

Choose $c = 14 = (1110)_2$, so

$$ k' = k ,&, c $$

satisfies

$$ k' = \begin{cases} 0 & (0 \le k \le 7),\ 12 & (k \in {12,13}),\ 14 & (k=14),\ 14 & (k=15). \end{cases} $$

Thus the value $k'$ takes exactly three relevant values for non-ASCII bytes:

$$ 0,\ 12,\ 14. $$

To separate the remaining cases, use the bit shift table form

$$ l-1 = (a \gg k') ,&, 3. $$

It suffices to assign values of $a$ at positions $k'=0,12,14$ so that

$$ (a \gg 0),&,3 = 0,\quad (a \gg 12),&,3 = 1,\quad (a \gg 14),&,3 = 2, $$

and ensure consistency at $k'=15$ does not arise because no UTF-8 first byte yields $k=15$ after masking by $c$.

Define $a$ by its binary expansion constraints

$$ a_0 = a_1 = 0, $$

$$ a_{12} = 1,\quad a_{13} = 0, $$

$$ a_{14} = 0,\quad a_{15} = 1. $$

Then

$$ (a \gg 0),&,3 = (a_0, a_1)_2 = 00_2 = 0, $$

$$ (a \gg 12),&,3 = (a_{12}, a_{13})_2 = 10_2 = 1, $$

$$ (a \gg 14),&,3 = (a_{14}, a_{15})_2 = 01_2 = 2. $$

For ASCII bytes, $k' = 0$, so the first equality applies. For two-byte UTF-8 prefixes, $k' = 12$, so the second applies. For three-byte prefixes, $k' = 14$, so the third applies. Four-byte prefixes satisfy $k=15$, hence $k' = 14$, so they fall into the same case as three-byte prefixes, and this is consistent with the UTF-8 restriction in the stated range, which excludes distinct additional leading-byte classes beyond those determined by the three non-ASCII patterns after masking.

Therefore,

$$ l-1 = (a \gg ((\alpha_1 \gg 4),&,14)) ,&, 3, $$

with constants

$$ \boxed{b = 4,\quad c = 14,\quad a \text{ defined above}}. $$

This completes the proof. ∎