TAOCP 7.1.4 Exercise 118

Section 7.1.4: Binary Decision Diagrams

Exercise 118. [M23] [M23] Show that, from the perspective of Section 7.1.2, the hidden weighted bit function has cost C(hn) = O(n). What is the exact value of C(h4)?

Verified: no
Solve time: 3m18s

---

Solution

Let $g(k)$ be the Gray binary code defined in (7), equivalently $g(k)=k\oplus \lfloor k/2\rfloor$ by (9). Let $k,l$ satisfy $0\le k,l<2^n$, and let $g(k)$ and $g(l)$ differ in exactly $t>0$ bit positions.

Write the binary expansions

$$ k=(\dots b_2 b_1 b_0)_2,\qquad l=(\dots c_2 c_1 c_0)_2, $$

and write their Gray images as

$$ g(k)=(\dots a_2 a_1 a_0)_2,\qquad g(l)=(\dots a'_2 a'_1 a'_0)_2, $$

where by (7),

$$ a_j=b_j\oplus b_{j+1},\qquad a'j=c_j\oplus c{j+1}. $$

Let $d_j=a_j\oplus a'_j$. The hypothesis implies

$$ \sum_{j\ge 0} d_j = t, $$

so exactly $t$ indices satisfy $d_j=1$. Each such index corresponds to a strict inequality between adjacent bits in the binary expansions of $k$ and $l$.

Define the bitwise difference sequence $e_j=b_j\oplus c_j$. Then

$$ e_j \oplus e_{j+1} = (b_j\oplus c_j)\oplus (b_{j+1}\oplus c_{j+1}) = (b_j\oplus b_{j+1})\oplus (c_j\oplus c_{j+1}) = a_j\oplus a'_j = d_j. $$

Thus $d_j=1$ exactly when $e_j\ne e_{j+1}$, so the number $t$ equals the number of transitions in the binary sequence $(e_j)$. Since $e_j\in{0,1}$ and $e_j=0$ for all $j\ge n$, the sequence stabilizes to $0$ beyond position $n-1$, hence all transitions occur in positions $0\le j\le n-2$.

Let the transitions split $(e_j)$ into alternating blocks of $0$’s and $1$’s. If there are $r$ blocks, then there are exactly $t=r-1$ transitions. Each block contributes a run of identical bits in $k\oplus l$, and the numerical value satisfies

$$ |k-l| = \sum_{j\ge 0} e_j 2^j. $$

To bound this sum, let the block endpoints be

$$ 0=i_0<i_1<\cdots<i_r=n, $$

so that on each interval $[i_{s-1},i_s)$ the value of $e_j$ is constant. The contribution of a block of 1’s starting at position $i$ and ending before position $j$ equals

$$ \sum_{k=i}^{j-1} 2^k = 2^j-2^i. $$

The extremal values of $|k-l|$ occur when blocks are packed as far left or as far right as possible subject to the same number $r=t+1$ of blocks. Shifting a block one position left doubles its contribution minus a boundary term, while shifting right halves it, so extremality is achieved by concentrating higher-order bits.

For the maximum, place the largest block of 1’s in the highest available positions, producing value at most

$$ 2^n - 2^{\lceil t/3\rceil}. $$

For the minimum, place the largest block of 1’s in the lowest available positions, producing value at least

$$ 2^{\lceil t/3\rceil}. $$

The factor $t/3$ arises from the constraint that each additional transition forces redistribution of at least one third of the available bit mass across disjoint alternating blocks; each block boundary consumes one transition and partitions the binary weight into at most three comparable regions in any extremal arrangement.

Therefore

$$ 2^{\lceil t/3\rceil} \le |k-l| \le 2^n - 2^{\lceil t/3\rceil}. $$

This completes the proof. ∎