TAOCP 7.1.3 Exercise 5
**(a)** By definition (19), for every integer $x$ and integer $k \ge 0$, $x \ll k = \lfloor 2^k x \rfloor.$ Since $x$ is an integer, $2^j x$ is an integer, hence $\lfloor 2^j x \rfloor = 2^j x.$ There...
Section 7.1.3: Bitwise Tricks and Techniques
Exercise 5. [M21] Prove or disprove the following conjectured laws concerning binary shifts: a) $(x \ll j) \ll k = x \ll (j + k)$; b) $(x \gg j) \mathbin{&} (y \ll k) = ((x \gg (j + k)) \mathbin{&} y) \ll k = (x \mathbin{&} (y \ll (j + k))) \gg j$.
Verified: yes
Solve time: 1m39s
Solution
(a)
By definition (19), for every integer $x$ and integer $k \ge 0$,
$x \ll k = \lfloor 2^k x \rfloor.$
Since $x$ is an integer, $2^j x$ is an integer, hence
$\lfloor 2^j x \rfloor = 2^j x.$
Therefore,
$x \ll j = 2^j x.$
Applying the same rule again,
$(x \ll j) \ll k = \lfloor 2^k (2^j x) \rfloor = \lfloor 2^{j+k} x \rfloor = x \ll (j+k),$
where the last equality uses definition (19) again.
This completes the proof of (a). ∎
(b)
Let $x = (\ldots x_2 x_1 x_0)_2$ and $y = (\ldots y_2 y_1 y_0)_2$.
For right shift (20),
$(x \gg j)t = x{t+j}, \quad t \ge 0,$
and for left shift (19),
\begin{cases} y_{t-k}, & t \ge k, \ 0, & t < k. \end{cases} $$
First expression Let
$$A = (x \gg j) ,&, (y \ll k).$$ The $t$-th bit of $A$ equals $$A_t = (x \gg j)t \wedge (y \ll k)t = x{t+j} \wedge y{t-k},$$ for $t \ge k$, and $A_t = 0$ for $t < k$. ### Middle expression Let $$B = ((x \gg (j+k)) ,&, y) \ll k.$$ First, $$(x \gg (j+k))u = x{u+j+k},$$ so the AND with $y$ gives $$((x \gg (j+k)) ,&, y)u = x{u+j+k} \wedge y_u.$$ After shifting left by $k$, the $t$-th bit of $B$ satisfies, for $t \ge k$, $$B_t = x_{t-k+j+k} \wedge y_{t-k} = x_{t+j} \wedge y_{t-k},$$ and $B_t = 0$ for $t < k$. Thus $A_t = B_t$ for all $t$. ### Third expression Let $$C = (x ,&, (y \ll (j+k))) \gg j.$$ First, $$(y \ll (j+k))v = \begin{cases} y{v-(j+k)}, & v \ge j+k, \ 0, & v < j+k. \end{cases}$$ Hence $$(x ,&, (y \ll (j+k)))v = x_v \wedge y{v-(j+k)}.$$ After shifting right by $j$, the $t$-th bit is $$C_t = x_{t+j} \wedge y_{t+j-(j+k)} = x_{t+j} \wedge y_{t-k},$$ and this is $0$ when $t < k$ because then $t+j < j+k$ forces the corresponding bit of $y \ll (j+k)$ to be $0$. Thus $C_t = A_t$ for all $t$. Since all three expressions agree bitwise, they are equal: $$ (x \gg j) ,&, (y \ll k) = ((x \gg (j+k)) ,&, y) \ll k = (x ,&, (y \ll (j+k))) \gg j. $$ This completes the proof. ∎