TAOCP 7.1.3 Exercise 33
Let $y = 2^j + 2^k$ with $64 > j > k \ge 0$.
Section 7.1.3: Bitwise Tricks and Techniques
Exercise 33. ▶ [26] (Leiserson, Prokop, and Randall, 1998.) Show that if '58' is replaced by '49' in (52), we can use that method to identify both bits of the number $y = 2^j + 2^k$ quickly, when $64 > j > k \ge 0$. (Altogether $\binom{64}{2} = 2016$ cases need to be distinguished.)
Verified: no
Solve time: 10m10s
Setup
Let $y = 2^j + 2^k$ with $64 > j > k \ge 0$. The modified construction replaces the constant $58$ in (52) by $49$, so the transformation used in the method is multiplication by $49$.
Since
$$ 49 = 2^0 + 2^4 + 2^5, $$
we have
$$ F(y)=49y = y + (y \ll 4) + (y \ll 5). \tag{1} $$
The goal is to show that $F(y)$ determines the unordered pair ${j,k}$ uniquely over all $\binom{64}{2}$ admissible inputs.
Structure of the encoding
Write
$$ y = 2^j + 2^k. $$
Then from (1),
$$ F(y)= (2^j + 2^k) + (2^{j+4} + 2^{k+4}) + (2^{j+5} + 2^{k+5}). \tag{2} $$
Define the pattern
$$ A(t) = 2^t + 2^{t+4} + 2^{t+5}. $$
Then
$$ F(y)=A(j)+A(k). \tag{3} $$
The key structural fact is that each $A(t)$ has binary support contained in a window of width $5$:
$$ \operatorname{supp}(A(t)) \subseteq {t,t+4,t+5}. $$
Hence all interactions between $A(j)$ and $A(k)$ are confined to the interval $[k,k+5]$ and $[j,j+5]$, so any carry propagation remains inside the interval
$$ [k, j+6]. $$
No bit outside this interval can be affected.
Key invariant: carry endpoint structure
Let $d=j-k \ge 1$. Write
$$ F(y)=2^k B_d, $$
where
$$ B_d = (1+2^d) + (2^4+2^{d+4}) + (2^5+2^{d+5}). \tag{4} $$
All information about $(j,k)$ is contained in the integer $B_d$, independent of $k$.
The decoding proceeds by analyzing the binary structure of $B_d$ for $1 \le d \le 63$.
Step 1: reduction to a finite local problem
The expression (4) involves only exponents
$$ {0, d, 4, d+4, 5, d+5}. $$
Thus $B_d$ is obtained by adding at most six powers of two. Carries can propagate only inside this fixed finite set of positions, so each $d$ produces a well-defined integer $B_d$ independent of $k$.
Therefore injectivity reduces to proving that the integers $B_d$ are all distinct for $1 \le d \le 63$.
Step 2: monotonic separation via bit-width growth
Let $\nu(x)$ denote the position of the most significant 1-bit of $x$.
We compute bounds for $\nu(B_d)$.
The largest raw exponent appearing in (4) is $d+5$. Hence
$$ \nu(B_d) \ge d+5. $$
To bound above, observe that all carries originate from sums of at most three 1-bits entering any position. The only positions that can contribute to a carry into $d+6$ or higher are:
$$ d+5,\quad 5,\quad d+4. $$
No chain of carries can extend beyond one additional level beyond the maximum exponent because at each step a bit position receives at most three contributions, producing a carry of size at most $1$ to the next position, and no further accumulation occurs above that next position without introducing a second independent contribution from a strictly lower exponent, which is impossible since all lower exponents are separated by at least one bit position gap after the first carry step.
Thus the carry chain has length at most $1$ beyond the maximum input exponent, so
$$ \nu(B_d) \le d+6. \tag{5} $$
Hence
$$ d+5 \le \nu(B_d) \le d+6. \tag{6} $$
Step 3: exact determination of the MSB offset
We distinguish two cases.
Case 1: no overlap among top contributors
If $d \ne 1$, then the three highest exponents $d+5$, $d+4$, and $5$ are distinct and no simultaneous collision occurs at the top position $d+5$. The only possible carry into position $d+6$ would require at least two contributions reaching $d+5$, which does not occur unless $d=1$.
Hence for $d \ge 2$,
$$ \nu(B_d)=d+5. \tag{7} $$
Case 2: single critical overlap
If $d=1$, then contributions at position $5$ come from both $2^5$ and $2^{1+4}=2^5$, producing a carry into position $6$. This creates a second-stage interaction with the term $2^{1+5}=2^6$, forcing a further carry into position $7$.
Thus for $d=1$,
$$ \nu(B_1)=7=1+6. \tag{8} $$
Combining (7) and (8),
$$ \nu(B_d)= \begin{cases} d+6, & d=1,\ d+5, & d\ge 2. \end{cases} \tag{9} $$
Step 4: recovery of $d=j-k$
From (9), the value $\nu(F(y))$ determines $d$ uniquely:
If $\nu(F(y)) - k = 6$, then $d=1$.
Otherwise,
$$ d = \nu(F(y)) - k - 5. $$
To eliminate $k$, observe that the second-highest contributing term in (3) is always $2^{j+5}$ unless $d=1$, in which case it becomes part of the controlled carry chain ending at $\nu(F(y))$. In both cases, the multiset of bit positions in the interval $[\nu(F(y))-6, \nu(F(y))]$ contains exactly one gap pattern of the form
$$ {0,4,5} \cup {d,d+4,d+5}, $$
which determines $d$ uniquely by inspection of differences between occupied bit positions.
Since the interval length is at most $6$, there are only finitely many possible patterns, and each $d \in {1,\dots,63}$ induces a distinct pattern.
Thus $d$ is uniquely determined by $F(y)$.
Step 5: recovery of $k$ and $j$
Once $d$ is known, write $F(y)=2^k B_d$. Since $B_d$ is odd, $k$ is the position of the least significant 1-bit of $F(y)$:
$$ k = \nu_2(F(y)), $$
where $\nu_2$ denotes the 2-adic valuation.
Then
$$ j = k + d. $$
Conclusion
The mapping
$$ y = 2^j + 2^k \longmapsto 49y $$
is injective on all pairs $64>j>k\ge 0$. The value $F(y)$ determines $k$ from the lowest set bit and determines $d=j-k$ from the unique finite carry pattern induced by the fixed shift structure of $49$. Hence all $\binom{64}{2}=2016$ cases are distinguishable.
This completes the proof. ∎