TAOCP 7.1.3 Exercise 27
Let $A$ be the integer represented by $\alpha$, and let $a$ be the length of $\alpha$ in bits.
Section 7.1.3: Bitwise Tricks and Techniques
Exercise 27. [21] In the notation of Eqs. (32)–(43), how would you compute (a) $(\alpha,10^*01^k)_2$? (b) $(\alpha,10^*11^k)_2$? (c) $(\alpha 00^*01^k)_2$? (d) $(0^\infty 11^*00^k)_2$? (e) $(0^\infty 01^*00^k)_2$? (f) $(0^\infty 11^*11^k)_2$?
Verified: yes
Solve time: 1m19s
Solution
Let $A$ be the integer represented by $\alpha$, and let $a$ be the length of $\alpha$ in bits. Each expression of the form $(\alpha ,\cdots)_2$ is interpreted as concatenation of the binary word $\alpha$ with the indicated suffix; a block $x^*$ denotes an arbitrary-length run of the bit $x$, say $x^t$ with $t \ge 0$.
If a binary word $w$ is appended to $\alpha$, then the resulting value is
$A \ll |w| ;+; \text{value}(w).$
All answers are therefore families of integers indexed by the free parameter $t \ge 0$ coming from $x^*$.
(a) $(\alpha,10^*01^k)_2$
Write $0^* = 0^t$, $t \ge 0$. The suffix is
$1,0^t,0,1^k.$
Its length is $t+k+2$, so the contribution of $\alpha$ is $A \ll (t+k+2)$.
The value of the suffix is obtained by positional weights. The final block $1^k$ contributes $2^k - 1$. The single $1$ preceding the $0^t0$ lies at position $k+t+1$, contributing $2^{k+t+1}$.
Thus
$\text{value} = (A \ll (t+k+2)) + 2^{k+t+1} + (2^k - 1), \qquad t \ge 0.$
(b) $(\alpha,10^*11^k)_2$
The suffix is $1,0^t,1,1^k$ of length $t+k+2$, hence the prefix contributes $A \ll (t+k+2)$.
The trailing block contributes $2^k - 1$. The isolated $1$ before it lies at position $k+t+1$, contributing $2^{k+t+1}$.
Therefore
$\text{value} = (A \ll (t+k+2)) + 2^{k+t+1} + (2^k - 1), \qquad t \ge 0.$
(c) $(\alpha,00^*01^k)_2$
The suffix is $0,0^t,0,1^k = 0^{t+2}1^k$, of length $t+k+2$, so the prefix contributes $A \ll (t+k+2)$.
Only the final block $1^k$ contributes nonzero value, equal to $2^k - 1$.
Hence
$\text{value} = (A \ll (t+k+2)) + (2^k - 1), \qquad t \ge 0.$
(d) $(0^\infty 11^*00^k)_2$
The leading $0^\infty$ forces all higher bits to be zero, so only the finite suffix matters. Write $1^* = 1^t$, $t \ge 0$, giving suffix $1,1^t,0^{k}$.
Its length is $t+k+1$, so there is no additional prefix contribution.
The block $1,1^t$ contributes a run of $t+1$ ones starting at position $k$, hence
$\text{value} = 2^{k+t+1} - 2^k, \qquad t \ge 0.$
(e) $(0^\infty 01^*00^k)_2$
Write $1^* = 1^t$. The suffix is $0,1^t,0^{k+1}$.
The rightmost block is all zeros, so only the $1^t$ block contributes. These ones occupy positions $k+1$ through $k+t$, giving a contiguous block of $t$ ones starting at position $k+1$.
Thus
$\text{value} = (2^{k+t+1} - 2^{k+1}), \qquad t \ge 0.$
(f) $(0^\infty 11^*11^k)_2$
Write $1^* = 1^t$. The suffix is $1,1^t,1,1^k = 1^{t+k+2}$.
Hence the value is a single block of $t+k+2$ ones starting at position $0$:
$\text{value} = 2^{t+k+2} - 1, \qquad t \ge 0.$
This completes the solution. ∎