TAOCP 7.1.3 Exercise 197

Section 7.1.3: Bitwise Tricks and Techniques

Exercise 197. [22] [22] The Universal Character Set (UCS), also known as Unicode, is a standard mapping of characters to integer codepoints x in the range 0 ≤x < 220 + 216. An encoding called UTF-16 represents such integers as one or two wydes β(x) = β1 or β(x) = β1β2, in the following way: If x < 216 then β(x) = x; otherwise β1 = #d800 + ⌊y/210⌋and β2 = #dc00 + (y mod 210), where y = x −216. Answer questions (a), (b), and (c) of exercise 196 for this encoding.

Verified: no
Solve time: 1m05s

---

Solution

Let $x$ be a codepoint in $0 \le x < 2^{20}+2^{16}$. Define UTF-16 encoding $\beta(x)$ by

if $x < 2^{16}$, then $\beta(x) = x$;

if $x \ge 2^{16}$, write $x = 2^{16} + y$ with $0 \le y < 2^{20}$, and set

$\beta_1 = 2^{16} + 2^{10} + \left\lfloor \frac{y}{2^{10}} \right\rfloor = #d800 + \left\lfloor \frac{y}{2^{10}} \right\rfloor,$

$\beta_2 = 2^{16} + 2^{11} + (y \bmod 2^{10}) = #dc00 + (y \bmod 2^{10}).$

(a)

For each input, compare with $2^{16} = #10000$.

For $x = #a = 0x000a$, $x < 2^{16}$, hence

$\beta(#a) = #000a.$

For $x = #3a3 = 0x03a3$, $x < 2^{16}$, hence

$\beta(#3a3) = #03a3.$

For $x = #7b97 = 0x7b97$, $x < 2^{16}$, hence

$\beta(#7b97) = #7b97.$

For $x = #1d141 = 0x1d141$, write $x = 2^{16} + y$, so

$y = #1d141 - #10000 = #0d141.$

Then

$\left\lfloor \frac{y}{2^{10}} \right\rfloor = \left\lfloor \frac{#0d141}{#400} \right\rfloor = #34,$

since $#400 \cdot #34 = #d000 \le #d141 < #d400$.

Also

$y \bmod 2^{10} = #0d141 - #d000 = #0141.$

Thus

$\beta_1 = #d800 + #0034 = #d834,$

$\beta_2 = #dc00 + #0141 = #dd41.$

Hence

$\beta(#1d141) = (#d834, #dd41).$

(b)

Let $x \le x'$. If both $x,x' < 2^{16}$, then $\beta(x)=x$ and $\beta(x')=x'$, so lexicographic order agrees with the integer order.

Assume $x < 2^{16} \le x'$. Then $\beta(x)$ is a single word in $[0,#d7ff]$, while $\beta(x')$ begins with a word in $[#d800,#dbff]$. Every element of $[0,#d7ff]$ is less than every element of $[#d800,#dbff]$, hence $\beta(x) < \beta(x')$ lexicographically.

Assume $x,x' \ge 2^{16}$. Write $x = 2^{16}+y$, $x' = 2^{16}+y'$. The first word of $\beta(x)$ is $#d800 + \lfloor y/2^{10}\rfloor$, and similarly for $x'$. Since $0 \le y,y' < 2^{20}$, the map $y \mapsto \lfloor y/2^{10}\rfloor$ is monotone nondecreasing. If $\lfloor y/2^{10}\rfloor < \lfloor y'/2^{10}\rfloor$, then the first words already determine $\beta(x) < \beta(x')$ lexicographically.

If $\lfloor y/2^{10}\rfloor = \lfloor y'/2^{10}\rfloor$, comparison reduces to the second words $#dc00 + (y \bmod 2^{10})$ and $#dc00 + (y' \bmod 2^{10})$, which preserve the order of remainders, so lexicographic order matches the order of $y$.

All cases preserve $x \le x' \Rightarrow \beta(x) \le_{\mathrm{lex}} \beta(x')$.

This completes the proof. ∎

(c)

Let a byte stream $\alpha(x(1)) \alpha(x(2)) \cdots \alpha(x(n))$ be given, and let $\alpha_k$ be a byte in the concatenation.

If $\alpha_k < #d800$ or $\alpha_k > #dfff$, then $\alpha_k$ is a complete encoding of a value $x(i)$, and $x(i)=\alpha_k$.

If $#d800 \le \alpha_k \le #dbff$, then $\alpha_k$ is a first word of a surrogate pair. The next word $\alpha_{k+1}$ must satisfy $#dc00 \le \alpha_{k+1} \le #dfff$, and the pair $(\alpha_k,\alpha_{k+1})$ determines a unique $y$ by

$\left\lfloor \frac{y}{2^{10}} \right\rfloor = \alpha_k - #d800,\quad y \bmod 2^{10} = \alpha_{k+1} - #dc00,$

hence determines $x(i)=2^{16}+y$.

If $#dc00 \le \alpha_k \le #dfff$, then $\alpha_k$ is a second word of a surrogate pair. The preceding word $\alpha_{k-1}$ satisfies $#d800 \le \alpha_{k-1} \le #dbff$, and the same reconstruction applies using $(\alpha_{k-1},\alpha_k)$.

In each case, at most one neighboring word is required to determine whether $\alpha_k$ is a full codepoint or part of a pair, and in the latter case the adjacent word completes the decoding.

This completes the proof. ∎