TAOCP 7.1.3: Bitwise Tricks and Techniques

Section 7.1.3 exercises: 219/219 solved.

219 items

Section 7.1.3. Bitwise Tricks and Techniques

Exercises from TAOCP Volume 4 Section 7.1.3: 219/219 solved.

#	Rating	Category	Status	Time
1	▶ [15]	simple	verified	1m45s
2	[16]	medium	solved	6m10s
3	[M20]	math-medium	solved	3m28s
4	▶ [M16]	math-medium	verified	1m37s
5	[M21]	math-medium	verified	1m39s
6	[M22]	math-medium	solved	5m27s
7	[M22]	math-medium	solved	6m25s
8	▶ [M22]	math-medium	verified	4m16s
9	[M26]	math-hard	verified	4m46s
10	[HM40]	hm-project	solved	7m54s
11	▶ [M26]	math-hard	verified	5m
12	[M26]	math-hard	solved	4m10s
13	[M32]	math-hard	solved	5m14s
14	[M30]	math-hard	verified	4m45s
15	▶ [M30]	math-hard	solved	4m46s
16	[M31]	math-hard	solved	4m27s
17	[HM36]	hm-project	solved	1m07s
18	[M25]	math-medium	verified	2m40s
19	▶ [M37]	math-project	solved	1m52s
20	▶ [21]	medium	verified	2m29s
21	[22]	medium	solved	4m
22	[21]	medium	verified	2m20s
23	▶ [27]	hard	solved	5m11s
24	▶ [M30]	math-hard	solved	4m38s
25	▶ [15]	simple	solved	4m22s
26	[22]	medium	verified	2m18s
27	[21]	medium	verified	1m19s
28	[16]	medium	verified	1m17s
29	[20]	medium	solved	3m40s
30	[20]	medium	verified	3m43s
31	▶ [20]	medium	verified	1m11s
32	[20]	medium	verified	1m15s
33	▶ [26]	hard	solved	10m10s
34	[M23]	math-medium	verified	4m30s
35	▶ [M26]	math-hard	solved	4m12s
36	[20]	medium	verified	1m10s
37	[16]	medium	verified	1m09s
38	[17]	medium	solved	4m15s
39	▶ [20]	medium	solved	1m11s
40	▶ [21]	medium	verified	1m04s
41	[M22]	math-medium	solved	1m02s
42	[M21]	math-medium	verified	4m06s
43	▶ [20]	medium	solved	2m42s
44	▶ [23]	medium	verified	5m02s
45	▶ [20]	medium	verified	3m46s
46	[22]	medium	solved	1m43s
47	[10]	simple	verified	1m
48	[M21]	math-medium	solved	3m34s
49	▶ [M30]	math-hard	solved	2m07s
50	[M37]	math-project	solved	4m02s
51	[23]	medium	verified	4m18s
52	[22]	medium	solved	3m40s
53	▶ [M25]	math-medium	solved	1m09s
54	[22]	medium	solved	4m17s
55	▶ [26]	hard	solved	4m47s
56	[24]	medium	verified	1m09s
57	[22]	medium	solved	3m29s
58	▶ [M32]	math-hard	solved	4m01s
59	[M30]	math-hard	solved	4m13s
60	[HM28]	hm-hard	solved	4m02s
61	[46]	research	solved	3m44s
62	▶ [22]	medium	verified	1m13s
63	[19]	medium	verified	1m09s
64	[22]	medium	verified	3m25s
65	[M16]	math-medium	verified	1m07s
66	▶ [M26]	math-hard	solved	1m01s
67	[M31]	math-hard	solved	1m01s
68	[20]	medium	solved	11m08s
69	[25]	medium	solved	4m13s
70	▶ [31]	hard	solved	11m36s
71	[20]	medium	solved	3m45s
72	[25]	medium	solved	4m58s
73	[22]	medium	solved	4m43s
74	[22]	medium	solved	12m45s
75	▶ [32]	hard	solved	12m32s
76	[27]	hard	solved	4m25s
77	[26]	hard	solved	5m48s
78	[M27]	math-hard	solved	9m10s
79	▶ [20]	medium	solved	10m03s
80	[20]	medium	solved	13m50s
81	[21]	medium	solved	4m55s
82	[21]	medium	solved	5m55s
83	▶ [33]	hard	solved	10m48s
84	[25]	medium	solved	6m12s
85	[22]	medium	verified	6m02s
86	[M27]	math-hard	solved	12m07s
87	▶ [20]	medium	solved	14m45s
88	[20]	medium	solved	13m57s
89	[23]	medium	solved	12m17s
90	[20]	medium	solved	5m35s
91	▶ [26]	hard	solved	6m02s
92	▶ [21]	medium	solved	5m50s
93	[18]	medium	solved	5m11s
94	[21]	medium	solved	5m10s
95	[22]	medium	solved	4m32s
96	[21]	medium	solved	4m25s
97	[23]	medium	solved	12m33s
98	[20]	medium	solved	5m10s
99	▶ [28]	hard	solved	5m32s
100	[25]	medium	verified	4m44s
101	▶ [22]	medium	verified	2m23s
102	[25]	medium	solved	8m23s
103	▶ [22]	medium	verified	5m20s
104	[22]	medium	verified	5m44s
105	[30]	hard	solved	2m08s
106	[**]		verified	1m48s
107	▶ [22]	medium	verified	3m53s
108	[26]	hard	solved	7m26s
109	[20]	medium	solved	3m50s
110	▶ [30]	hard	solved	5m13s
111	[23]	medium	verified	2m46s
112	[46]	research	solved	4m35s
113	[23]	medium	verified	3m07s
114	[16]	medium	solved	4m34s
115	▶ [24]	medium	solved	2m30s
116	[HM30]	hm-hard	solved	2m44s
117	[HM46]	hm-research	solved	3m42s
118	[30]	hard	solved	5m
119	[20]	medium	verified	2m23s
120	▶ [M25]	math-medium	verified	2m41s
121	▶ [M25]	math-medium	solved	4m43s
122	[M22]	math-medium	verified	1m56s
123	[M23]	math-medium	solved	3m56s
124	[M38]	math-project	solved	4m06s
125	[M33]	math-hard	verified	1m14s
126	[M46]	math-research	solved	4m27s
127	[HM40]	hm-project	solved	3m52s
128	[M46]	math-research	verified	1m24s
129	[M46]	math-research	solved	4m03s
130	[M46]	math-research	verified	4m19s
131	▶ [23]	medium	solved	1m54s
132	▶ [M27]	math-hard	verified	4m50s
133	▶ [20]	medium	verified	1m56s
134	[15]	simple	solved	3m02s
135	[22]	medium	solved	4m41s
136	[29]	hard	verified	5m28s
137	[21]	medium	verified	3m58s
138	[24]	medium	solved	3m54s
139	[25]	medium	verified	1m30s
140	[27]	hard	verified	1m18s
141	▶ [30]	hard	verified	4m34s
142	▶ [33]	hard	verified	4m06s
143	[20]	medium	verified	1m16s
144	[16]	medium	verified	1m03s
145	[17]	medium	verified	1m08s
146	▶ [M20]	math-medium	solved	3m25s
147	▶ [M20]	math-medium	solved	3m
148	[M21]	math-medium	solved	3m39s
149	▶ [23]	medium	verified	3m57s
150	▶ [25]	medium	solved	2m18s
151	[22]	medium	verified	4m12s
152	[M21]	math-medium	solved	4m37s
153	▶ [M20]	math-medium	solved	3m22s
154	[20]	medium	verified	2m28s
155	▶ [M21]	math-medium	solved	1m20s
156	[21]	medium	solved	3m37s
157	[M21]	math-medium	solved	1m35s
158	[M26]	math-hard	solved	2m50s
159	[M34]	math-hard	verified	3m56s
160	[M29]	math-hard	solved	3m44s
161	[20]	medium	solved	2m10s
162	▶ [HM37]	hm-project	solved	5m19s
163	[HM41]	hm-project	verified	2m32s
164	[23]	medium	verified	2m26s
165	[21]	medium	verified	1m07s
166	[M23]	math-medium	solved	3m11s
167	[24]	medium	solved	4m57s
168	▶ [23]	medium	solved	2m33s
169	[22]	medium	solved	49s
170	▶ [21]	medium	solved	4m27s
171	[24]	medium	solved	4m02s
172	[M29]	math-hard	solved	4m28s
173	▶ [M30]	math-hard	solved	3m37s
174	[M46]	math-research	verified	4m08s
175	[15]	simple	solved	3m14s
176	[M24]	math-medium	solved	1m44s
177	[M22]	math-medium	verified	4m07s
178	[20]	medium	solved	1m14s
179	▶ [34]	hard	solved	4m20s
180	▶ [M24]	math-medium	verified	2m20s
181	[HM20]	hm-medium	verified	2m34s
182	[M31]	math-hard	solved	2m43s
183	▶ [M29]	math-hard	verified	3m11s
184	▶ [M22]	math-medium	verified	1m07s
185	▶ [23]	medium	verified	1m11s
186	[HM22]	hm-medium	verified	1m16s
187	[M29]	math-hard	solved	4m23s
188	▶ [25]	medium	solved	4m29s
189	[25]	medium	solved	1m14s
190	[23]	medium	solved	4m15s
191	[M30]	math-hard	solved	4m23s
192	[HM38]	hm-project	solved	4m27s
193	▶ [M21]	math-medium	solved	4m05s
194	[M24]	math-medium	solved	1m49s
195	▶ [HM25]	hm-medium	verified	1m16s
196	[21]	medium	solved	4m31s
197	[22]	medium	solved	1m05s
198	▶ [21]	medium	solved	1m40s
199	▶ [23]	medium	verified	3m
200	[20]	medium	verified	55s
201	[20]	medium	solved	1m57s
202	[20]	medium	solved	3m48s
203	[22]	medium	solved	4m32s
204	▶ [22]	medium	solved	4m26s
205	▶ [22]	medium	solved	1m34s
206	[20]	medium	verified	1m51s
207	[22]	medium	solved	4m52s
208	▶ [23]	medium	verified	2m55s
209	▶ [21]	medium	solved	2m22s
210	[22]	medium	solved	2m06s
211	▶ [M25]	math-medium	verified	1m15s
212	[M32]	math-hard	verified	1m16s
213	▶ [HM26]	hm-hard	solved	2m10s
214	▶ [HM28]	hm-hard	solved	3m24s
215	▶ [21]	medium	solved	5m17s
216	▶ [M26]	math-hard	solved	1m34s
217	[40]	project	verified	1m26s
218	▶ [M30]	math-hard	verified	1m18s
219	▶ [20]	medium	solved	5m17s

Practice › Mathematics › TAOCP › TAOCP Vol 4: Combinatorial Algorithms › TAOCP 7.1.3: Bitwise Tricks and Techniques ›

TAOCP 7.1.3 Exercise 1

Let the initial values be $x_0$ and $y_0$.

Practice › Mathematics › TAOCP › TAOCP Vol 4: Combinatorial Algorithms › TAOCP 7.1.3: Bitwise Tricks and Techniques ›

We work in the TAOCP model of integers as infinite binary expansions in two’s complement, with bitwise operations defined componentwise and integer order interpreted in the standard way on these repre...

Practice › Mathematics › TAOCP › TAOCP Vol 4: Combinatorial Algorithms › TAOCP 7.1.3: Bitwise Tricks and Techniques ›

TAOCP 7.1.3 Exercise 3

Let $n$ be the fixed word length and interpret all operations in the $n$-bit binary system.

Practice › Mathematics › TAOCP › TAOCP Vol 4: Combinatorial Algorithms › TAOCP 7.1.3: Bitwise Tricks and Techniques ›

TAOCP 7.1.3 Exercise 4

Using identity (16) in Section 7.

Practice › Mathematics › TAOCP › TAOCP Vol 4: Combinatorial Algorithms › TAOCP 7.1.3: Bitwise Tricks and Techniques ›

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...

Practice › Mathematics › TAOCP › TAOCP Vol 4: Combinatorial Algorithms › TAOCP 7.1.3: Bitwise Tricks and Techniques ›

TAOCP 7.1.3 Exercise 6

We use Knuth’s definitions for all integers $x,y$: x \gg y = \left\lfloor \frac{x}{2^y} \right\rfloor,\qquad x \ll y = x\cdot 2^y, where $2^y$ is a dyadic rational when $y<0$, and all floor effects oc...

Practice › Mathematics › TAOCP › TAOCP Vol 4: Combinatorial Algorithms › TAOCP 7.1.3: Bitwise Tricks and Techniques ›

TAOCP 7.1.3 Exercise 7

The flaw in the previous solution is the identification of division by $2$ (and hence by $-2$) with bit shifts on signed integers.

Practice › Mathematics › TAOCP › TAOCP Vol 4: Combinatorial Algorithms › TAOCP 7.1.3: Bitwise Tricks and Techniques ›

TAOCP 7.1.3 Exercise 8

Let $x=\mathrm{mex}(S)$ and $y=\mathrm{mex}(T)$, and define U=(S\oplus y)\cup (x\oplus T).

Practice › Mathematics › TAOCP › TAOCP Vol 4: Combinatorial Algorithms › TAOCP 7.1.3: Bitwise Tricks and Techniques ›

TAOCP 7.1.3 Exercise 9

We prove that a position $(a_1,\ldots,a_k)$ is losing for the player to move if and only if a_1 \oplus \cdots \oplus a_k = 0.

Practice › Mathematics › TAOCP › TAOCP Vol 4: Combinatorial Algorithms › TAOCP 7.1.3: Bitwise Tricks and Techniques ›

TAOCP 7.1.3 Exercise 10

The flaws in the previous solution come from repeatedly treating mex as if it interacts linearly with XOR or as if option sets decompose additively.

Practice › Mathematics › TAOCP › TAOCP Vol 4: Combinatorial Algorithms › TAOCP 7.1.3: Bitwise Tricks and Techniques ›

TAOCP 7.1.3 Exercise 11

Let $\mathbb{N} \subset \mathbf{No}$ denote the positive integers embedded in Conway’s field (the surreal numbers), and let $\otimes$ denote the field multiplication in $\mathbf{No}$.

Practice › Mathematics › TAOCP › TAOCP Vol 4: Combinatorial Algorithms › TAOCP 7.1.3: Bitwise Tricks and Techniques ›

TAOCP 7.1.3 Exercise 12

The previous solution fails because it replaces the actual nimber structure with an unproved quadratic-field analogy.

Practice › Mathematics › TAOCP › TAOCP Vol 4: Combinatorial Algorithms › TAOCP 7.1.3: Bitwise Tricks and Techniques ›

TAOCP 7.1.3 Exercise 13

The previous argument fails because it replaces the actual move graph by algebraic equations in nimbers.

Practice › Mathematics › TAOCP › TAOCP Vol 4: Combinatorial Algorithms › TAOCP 7.1.3: Bitwise Tricks and Techniques ›

TAOCP 7.1.3 Exercise 14

Let $T=(t_\alpha)_{\alpha\in\{0,1\}^*}$.

Practice › Mathematics › TAOCP › TAOCP Vol 4: Combinatorial Algorithms › TAOCP 7.1.3: Bitwise Tricks and Techniques ›

TAOCP 7.1.3 Exercise 15

We work over integers with bitwise XOR $\oplus$ and ordinary addition/subtraction.

Practice › Mathematics › TAOCP › TAOCP Vol 4: Combinatorial Algorithms › TAOCP 7.1.3: Bitwise Tricks and Techniques ›

TAOCP 7.1.3 Exercise 16

We rebuild the argument directly from the definitions in Exercise 14 and the structure of binary carries in 2-adic arithmetic.

Practice › Mathematics › TAOCP › TAOCP Vol 4: Combinatorial Algorithms › TAOCP 7.1.3: Bitwise Tricks and Techniques ›

TAOCP 7.1.3 Exercise 17

An expression $E(x_1,\ldots,x_m)$ is built from integer variables and integer constants using only $+$ and $\oplus$ (and possibly also $&$ in the second part).

Practice › Mathematics › TAOCP › TAOCP Vol 4: Combinatorial Algorithms › TAOCP 7.1.3: Bitwise Tricks and Techniques ›

TAOCP 7.1.3 Exercise 18

The flawed argument fails because it tries to reason at the level of individual bits while treating multiplication as if it were linearly decomposable.

Practice › Mathematics › TAOCP › TAOCP Vol 4: Combinatorial Algorithms › TAOCP 7.1.3: Bitwise Tricks and Techniques ›

TAOCP 7.1.3 Exercise 19

Let $G = ({0,1}^n,\oplus)$ be the additive group of bit vectors of length $n$.

Practice › Mathematics › TAOCP › TAOCP Vol 4: Combinatorial Algorithms › TAOCP 7.1.3: Bitwise Tricks and Techniques ›

TAOCP 7.1.3 Exercise 20

Let $x>0$ and define $u = x \,\&\, (-x), \qquad v = x + u.$ Let $k$ be the unique index such that $u = 2^k$.

Practice › Mathematics › TAOCP › TAOCP Vol 4: Combinatorial Algorithms › TAOCP 7.1.3: Bitwise Tricks and Techniques ›

TAOCP 7.1.3 Exercise 21

The earlier solution fails because it tries to reconstruct hidden structure using $y \mathbin{\&} (-y)$, which only isolates the least significant 1-bit and does not encode any run length information.

Practice › Mathematics › TAOCP › TAOCP Vol 4: Combinatorial Algorithms › TAOCP 7.1.3: Bitwise Tricks and Techniques ›

TAOCP 7.1.3 Exercise 22

The error is the use of arithmetic addition in the final recombination step.

Practice › Mathematics › TAOCP › TAOCP Vol 4: Combinatorial Algorithms › TAOCP 7.1.3: Bitwise Tricks and Techniques ›

TAOCP 7.1.3 Exercise 23

Encode “(” as $0$ and “)” as $1$.

Practice › Mathematics › TAOCP › TAOCP Vol 4: Combinatorial Algorithms › TAOCP 7.1.3: Bitwise Tricks and Techniques ›

TAOCP 7.1.3 Exercise 24

The failure is fundamental: all control flow in the proposed program is broken because it writes comparison results into register $0$, which is architecturally constant zero in MMIX and cannot be assi...

Practice › Mathematics › TAOCP › TAOCP Vol 4: Combinatorial Algorithms › TAOCP 7.1.3: Bitwise Tricks and Techniques ›

TAOCP 7.1.3 Exercise 25

Each volume consists of 250 sheets of thickness $0.1\ \text{mm}$ each, so the total paper thickness per book is 250 \cdot 0.

Practice › Mathematics › TAOCP › TAOCP Vol 4: Combinatorial Algorithms › TAOCP 7.1.3: Bitwise Tricks and Techniques ›

TAOCP 7.1.3 Exercise 26

Let $i$ be the index, $0 \le i < 12\cdot 10^6$, and write q = \left\lfloor \frac{i}{12} \right\rfloor,\qquad r = i - 12q,\qquad 0 \le r < 12.

Practice › Mathematics › TAOCP › TAOCP Vol 4: Combinatorial Algorithms › TAOCP 7.1.3: Bitwise Tricks and Techniques ›

TAOCP 7.1.3 Exercise 27

Let $A$ be the integer represented by $\alpha$, and let $a$ be the length of $\alpha$ in bits.

Practice › Mathematics › TAOCP › TAOCP Vol 4: Combinatorial Algorithms › TAOCP 7.1.3: Bitwise Tricks and Techniques ›

TAOCP 7.1.3 Exercise 28

Let $y = (x + 1) ,&, \bar{x}$.

Practice › Mathematics › TAOCP › TAOCP Vol 4: Combinatorial Algorithms › TAOCP 7.1.3: Bitwise Tricks and Techniques ›

TAOCP 7.1.3 Exercise 29

Let $\mu_k$ denote Pratt’s magic mask from (47).

Practice › Mathematics › TAOCP › TAOCP Vol 4: Combinatorial Algorithms › TAOCP 7.1.3: Bitwise Tricks and Techniques ›

TAOCP 7.1.3 Exercise 30

The previous solution fails because it treats the case $\rho = 64$ as requiring a structural change to the algorithm, when in fact the MMIX conventions already make $\rho = 64$ perfectly well-defined...

Practice › Mathematics › TAOCP › TAOCP Vol 4: Combinatorial Algorithms › TAOCP 7.1.3: Bitwise Tricks and Techniques ›

TAOCP 7.1.3 Exercise 31

The proposed procedure maintains $\rho$ as the number of trailing zero bits of $x$ by repeatedly replacing $x \leftarrow x \gg 1$ while $x \mathbin{&} 1 = 0$.

Practice › Mathematics › TAOCP › TAOCP Vol 4: Combinatorial Algorithms › TAOCP 7.1.3: Bitwise Tricks and Techniques ›

TAOCP 7.1.3 Exercise 32

Let $\rho(x)$ denote the number of trailing zero bits of $x$, that is, the number of right shifts required until the least significant bit becomes $1$.

Practice › Mathematics › TAOCP › TAOCP Vol 4: Combinatorial Algorithms › TAOCP 7.1.3: Bitwise Tricks and Techniques ›

TAOCP 7.1.3 Exercise 33

Let $y = 2^j + 2^k$ with $64 > j > k \ge 0$.

Practice › Mathematics › TAOCP › TAOCP Vol 4: Combinatorial Algorithms › TAOCP 7.1.3: Bitwise Tricks and Techniques ›

TAOCP 7.1.3 Exercise 34

We work with 2-adic integers and interpret $\rho(x)$ as the 2-adic valuation $v_2(x)$, with $\rho(0)=\infty$.

Practice › Mathematics › TAOCP › TAOCP Vol 4: Combinatorial Algorithms › TAOCP 7.1.3: Bitwise Tricks and Techniques ›

TAOCP 7.1.3 Exercise 35

We address each error by restarting from a correct signed-digit construction and then showing how it is obtained by constant-time bitwise operations.

Practice › Mathematics › TAOCP › TAOCP Vol 4: Combinatorial Algorithms › TAOCP 7.1.3: Bitwise Tricks and Techniques ›

TAOCP 7.1.3 Exercise 36

Let $x = (x_{63}\ldots x_0)_2$.

Practice › Mathematics › TAOCP › TAOCP Vol 4: Combinatorial Algorithms › TAOCP 7.1.3: Bitwise Tricks and Techniques ›

TAOCP 7.1.3 Exercise 37

Let (55) and (56) define the function $\lambda x$ recursively in terms of shifts and bit tests, with the standard convention that the recursion terminates at $x = 0$ by assigning a base value $\lambda...

Practice › Mathematics › TAOCP › TAOCP Vol 4: Combinatorial Algorithms › TAOCP 7.1.3: Bitwise Tricks and Techniques ›

TAOCP 7.1.3 Exercise 38

The error in the previous solution is that it reconstructs a generic “parallel prefix” algorithm and then assigns instruction counts without grounding them in the actual MMIX operations used in proced...

Practice › Mathematics › TAOCP › TAOCP Vol 4: Combinatorial Algorithms › TAOCP 7.1.3: Bitwise Tricks and Techniques ›

TAOCP 7.1.3 Exercise 39

Let $x = (x_{w-1}\ldots x_1 x_0)_2$ be a word of fixed width $w$.

Practice › Mathematics › TAOCP › TAOCP Vol 4: Combinatorial Algorithms › TAOCP 7.1.3: Bitwise Tricks and Techniques ›

TAOCP 7.1.3 Exercise 40

Let $\lambda x$ denote the index of the most significant $1$ in $x$, with the convention $\lambda 0 = 0$, so that $2^{\lambda x - 1} \le x < 2^{\lambda x}$ for $x > 0$.

Practice › Mathematics › TAOCP › TAOCP Vol 4: Combinatorial Algorithms › TAOCP 7.1.3: Bitwise Tricks and Techniques ›

TAOCP 7.1.3 Exercise 41

Let ordinary generating functions be taken in the sense $A(z)=\sum_{n\ge 0} a_n z^n,$ and extend the functions by $a_0=0$ for $\rho,\lambda,\nu$.

Practice › Mathematics › TAOCP › TAOCP Vol 4: Combinatorial Algorithms › TAOCP 7.1.3: Bitwise Tricks and Techniques ›

TAOCP 7.1.3 Exercise 42

Let $u = 2^{e_1} + \cdots + 2^{e_r}$ with $e_1 > \cdots > e_r \ge 0$.

Practice › Mathematics › TAOCP › TAOCP Vol 4: Combinatorial Algorithms › TAOCP 7.1.3: Bitwise Tricks and Techniques ›

TAOCP 7.1.3 Exercise 43

Let $w$ denote the word length of MMIX.

Practice › Mathematics › TAOCP › TAOCP Vol 4: Combinatorial Algorithms › TAOCP 7.1.3: Bitwise Tricks and Techniques ›

TAOCP 7.1.3 Exercise 44

Let $x = \sum_{j \ge 0} x_j 2^j$ with $x_j \in {0,1}$.

Practice › Mathematics › TAOCP › TAOCP Vol 4: Combinatorial Algorithms › TAOCP 7.1.3: Bitwise Tricks and Techniques ›

TAOCP 7.1.3 Exercise 45

The error in the previous solution is the implicit claim that one must rely on structural invariance of the relation under permutations.

Practice › Mathematics › TAOCP › TAOCP Vol 4: Combinatorial Algorithms › TAOCP 7.1.3: Bitwise Tricks and Techniques ›

TAOCP 7.1.3 Exercise 46

Let $x$ be a register containing bits $x_0, x_1, \ldots$, and fix distinct positions $i \neq j$.

Practice › Mathematics › TAOCP › TAOCP Vol 4: Combinatorial Algorithms › TAOCP 7.1.3: Bitwise Tricks and Techniques ›

TAOCP 7.1.3 Exercise 47

Let δ be the mask selecting the positions to be swapped in the general δ-swap (69).

Practice › Mathematics › TAOCP › TAOCP Vol 4: Combinatorial Algorithms › TAOCP 7.1.3: Bitwise Tricks and Techniques ›

TAOCP 7.1.3 Exercise 48

The previous solution fails because it replaces δ-swaps by XOR translations on indices, which is unrelated to Knuth’s construction.

Practice › Mathematics › TAOCP › TAOCP Vol 4: Combinatorial Algorithms › TAOCP 7.1.3: Bitwise Tricks and Techniques ›

TAOCP 7.1.3 Exercise 49

The previous solution failed because it never used the actual structural property of δ-swaps and introduced unrelated complexity measures.

Practice › Mathematics › TAOCP › TAOCP Vol 4: Combinatorial Algorithms › TAOCP 7.1.3: Bitwise Tricks and Techniques ›

TAOCP 7.1.3 Exercise 50

The proof must avoid any assumption that arbitrary integers can be freely “normalized” into powers of 3.

Practice › Mathematics › TAOCP › TAOCP Vol 4: Combinatorial Algorithms › TAOCP 7.1.3: Bitwise Tricks and Techniques ›

TAOCP 7.1.3 Exercise 51

Let the butterfly network (71) act on bit strings $x \in \{0,1\}^d$.

Practice › Mathematics › TAOCP › TAOCP Vol 4: Combinatorial Algorithms › TAOCP 7.1.3: Bitwise Tricks and Techniques ›

TAOCP 7.1.3 Exercise 52

Let scheme (71) be interpreted in its actual routing form: for each stage $k\in\{0,\dots,5\}$, the exchange operates on the $k$-th bit position, and the masks must be chosen so that a datum located at...

Practice › Mathematics › TAOCP › TAOCP Vol 4: Combinatorial Algorithms › TAOCP 7.1.3: Bitwise Tricks and Techniques ›

TAOCP 7.1.3 Exercise 53

Let $\upsilon$ be a permutation of ${0,1,\ldots,d-1}$, and let $j = (j_{d-1}\ldots j_1 j_0)_2$.

Practice › Mathematics › TAOCP › TAOCP Vol 4: Combinatorial Algorithms › TAOCP 7.1.3: Bitwise Tricks and Techniques ›

TAOCP 7.1.3 Exercise 54

Let $d=\lceil \lg m\rceil$.

Practice › Mathematics › TAOCP › TAOCP Vol 4: Combinatorial Algorithms › TAOCP 7.1.3: Bitwise Tricks and Techniques ›

TAOCP 7.1.3 Exercise 55

The previous solution fails because it never instantiates a valid TAOCP register program: it introduces informal “tensor elimination”, undefined data layouts, and unsupported cost sharing.

Practice › Mathematics › TAOCP › TAOCP Vol 4: Combinatorial Algorithms › TAOCP 7.1.3: Bitwise Tricks and Techniques ›

TAOCP 7.1.3 Exercise 56

Number the bits of the 64-bit register from $0$ (least significant) to $63$.

Practice › Mathematics › TAOCP › TAOCP Vol 4: Combinatorial Algorithms › TAOCP 7.1.3: Bitwise Tricks and Techniques ›

TAOCP 7.1.3 Exercise 57

We restart from the actual combinatorial structure of $P(2^d)$ as used in TAOCP: a recursive permutation network built from $2 \times 2$ switches arranged in $2d-1$ stages, where each stage consists o...

Practice › Mathematics › TAOCP › TAOCP Vol 4: Combinatorial Algorithms › TAOCP 7.1.3: Bitwise Tricks and Techniques ›

TAOCP 7.1.3 Exercise 58

Let $N=2^d$.

Practice › Mathematics › TAOCP › TAOCP Vol 4: Combinatorial Algorithms › TAOCP 7.1.3: Bitwise Tricks and Techniques ›

TAOCP 7.1.3 Exercise 59

We restart from the correct structural fact that the previous argument failed to justify: in an Omega network, _switch settings are not independent generators_, but for permutations with a prescribed...

Practice › Mathematics › TAOCP › TAOCP Vol 4: Combinatorial Algorithms › TAOCP 7.1.3: Bitwise Tricks and Techniques ›

TAOCP 7.1.3 Exercise 60

Let $K$ be the number of cycles in the graph $G = M_1 \cup M_2$, where $M_1$ is a fixed perfect matching on $\{0,1,\dots,2n-1\}$ and $M_2$ is a uniformly random perfect matching.

Practice › Mathematics › TAOCP › TAOCP Vol 4: Combinatorial Algorithms › TAOCP 7.1.3: Bitwise Tricks and Techniques ›

TAOCP 7.1.3 Exercise 61

The previous argument fails because it assumes that the recursion of Fig.

Practice › Mathematics › TAOCP › TAOCP Vol 4: Combinatorial Algorithms › TAOCP 7.1.3: Bitwise Tricks and Techniques ›

TAOCP 7.1.3 Exercise 62

Let $N = 2^d$.

Practice › Mathematics › TAOCP › TAOCP Vol 4: Combinatorial Algorithms › TAOCP 7.1.3: Bitwise Tricks and Techniques ›

TAOCP 7.1.3 Exercise 63

Let $x = (\ldots x_2 x_1 x_0)_2$ and $y = (\ldots y_2 y_1 y_0)_2$.

Practice › Mathematics › TAOCP › TAOCP Vol 4: Combinatorial Algorithms › TAOCP 7.1.3: Bitwise Tricks and Techniques ›

TAOCP 7.1.3 Exercise 64

The proposed solution fails because it tries to treat the interleaving as if it were compatible with ordinary addition.

Practice › Mathematics › TAOCP › TAOCP Vol 4: Combinatorial Algorithms › TAOCP 7.1.3: Bitwise Tricks and Techniques ›

TAOCP 7.1.3 Exercise 65

Let u(x)=\sum_{i=0}^{n-1} u_i x^i \pmod 2,\qquad v(x)=\sum_{i=0}^{n-1} v_i x^i \pmod 2, and let the corresponding integers be

Practice › Mathematics › TAOCP › TAOCP Vol 4: Combinatorial Algorithms › TAOCP 7.1.3: Bitwise Tricks and Techniques ›

TAOCP 7.1.3 Exercise 66

Let the binary polynomial $u(x)=u_0+u_1x+\cdots+u_{n-1}x^{n-1}\pmod 2$ be represented by the integer $u=(u_{n-1}\ldots u_1u_0)_2.$ For an integer $\delta \ge 0$, define $v = u \oplus (u \ll \delta) \o...

Practice › Mathematics › TAOCP › TAOCP Vol 4: Combinatorial Algorithms › TAOCP 7.1.3: Bitwise Tricks and Techniques ›

TAOCP 7.1.3 Exercise 67

Work in the ring $\mathbb{F}_2[x]/(x^n + x^m + 1)$ with $0<m<n$, where $m$ and $n$ are odd.

Practice › Mathematics › TAOCP › TAOCP Vol 4: Combinatorial Algorithms › TAOCP 7.1.3: Bitwise Tricks and Techniques ›

TAOCP 7.1.3 Exercise 68

The δ-shift operation (79) is the packed transformation on a word $u$ that shifts selected bit blocks by $\delta$ positions and combines results by XOR.

Practice › Mathematics › TAOCP › TAOCP Vol 4: Combinatorial Algorithms › TAOCP 7.1.3: Bitwise Tricks and Techniques ›

TAOCP 7.1.3 Exercise 69

The δ-shift operation (79) is the packed word transformation that produces a result $v$ from an input $u$ by forming a shifted copy of $u$ and combining it with $u$ by bitwise exclusive-or.

Practice › Mathematics › TAOCP › TAOCP Vol 4: Combinatorial Algorithms › TAOCP 7.1.3: Bitwise Tricks and Techniques ›

TAOCP 7.1.3 Exercise 70

The solution does not correctly address what Steele’s problem is asking in the context of method (80).

Practice › Mathematics › TAOCP › TAOCP Vol 4: Combinatorial Algorithms › TAOCP 7.1.3: Bitwise Tricks and Techniques ›

TAOCP 7.1.3 Exercise 71

Let $\theta_0,\theta_1,\ldots,\theta_{d-1}$ be the masks used in compression procedure (80).

Practice › Mathematics › TAOCP › TAOCP Vol 4: Combinatorial Algorithms › TAOCP 7.1.3: Bitwise Tricks and Techniques ›

TAOCP 7.1.3 Exercise 72

Let the word size be $2^k$ bits, with bit positions indexed $0,1,\ldots,2^k-1$.

Practice › Mathematics › TAOCP › TAOCP Vol 4: Combinatorial Algorithms › TAOCP 7.1.3: Bitwise Tricks and Techniques ›

TAOCP 7.1.3 Exercise 73

Let the $2^d$ bit positions be indexed by binary vectors $u = (u_{d-1}\ldots u_0)_2 \in {0,1}^d$.

Practice › Mathematics › TAOCP › TAOCP Vol 4: Combinatorial Algorithms › TAOCP 7.1.3: Bitwise Tricks and Techniques ›

TAOCP 7.1.3 Exercise 74

The solution targets the correct object: the cyclically shifted counts and the balance condition \sum c'_{2t}=\sum c'_{2t+1}.

Practice › Mathematics › TAOCP › TAOCP Vol 4: Combinatorial Algorithms › TAOCP 7.1.3: Bitwise Tricks and Techniques ›

TAOCP 7.1.3 Exercise 75

The solution targets the correct object: the cyclically shifted counts and the balance condition \sum c'_{2t}=\sum c'_{2t+1}.

Practice › Mathematics › TAOCP › TAOCP Vol 4: Combinatorial Algorithms › TAOCP 7.1.3: Bitwise Tricks and Techniques ›

TAOCP 7.1.3 Exercise 76

A mapping network on $n$ inputs uses $2\times 2$ modules, each module taking inputs $(a,b)$ and producing one of $(a,b)$, $(b,a)$, $(a,a)$, $(b,b)$.

Practice › Mathematics › TAOCP › TAOCP Vol 4: Combinatorial Algorithms › TAOCP 7.1.3: Bitwise Tricks and Techniques ›

TAOCP 7.1.3 Exercise 77

A mapping network on $n$ inputs uses $2\times 2$ modules, each module taking inputs $(a,b)$ and producing one of $(a,b)$, $(b,a)$, $(a,a)$, $(b,b)$.

Practice › Mathematics › TAOCP › TAOCP Vol 4: Combinatorial Algorithms › TAOCP 7.1.3: Bitwise Tricks and Techniques ›

TAOCP 7.1.3 Exercise 78

Each $x_j$ is a nonnegative integer with $x_j < 2^{n-k}$, hence each $x_j$ occupies at most the lowest $n-k$ bits.

Practice › Mathematics › TAOCP › TAOCP Vol 4: Combinatorial Algorithms › TAOCP 7.1.3: Bitwise Tricks and Techniques ›

TAOCP 7.1.3 Exercise 79

The solution does not address Exercise 7.

Practice › Mathematics › TAOCP › TAOCP Vol 4: Combinatorial Algorithms › TAOCP 7.1.3: Bitwise Tricks and Techniques ›

TAOCP 7.1.3 Exercise 80

The solution does not address Exercise 7.

Practice › Mathematics › TAOCP › TAOCP Vol 4: Combinatorial Algorithms › TAOCP 7.1.3: Bitwise Tricks and Techniques ›

TAOCP 7.1.3 Exercise 81

Let $\chi$ be a fixed set of nonnegative integers closed under the relation $x \subseteq \chi$, meaning every 1-bit position of $x$ corresponds to an element of $\chi$.

Practice › Mathematics › TAOCP › TAOCP Vol 4: Combinatorial Algorithms › TAOCP 7.1.3: Bitwise Tricks and Techniques ›

TAOCP 7.1.3 Exercise 82

Let $\chi$ be a fixed set of nonnegative integers closed under the relation $x \subseteq \chi$, meaning every 1-bit position of $x$ corresponds to an element of $\chi$.

Practice › Mathematics › TAOCP › TAOCP Vol 4: Combinatorial Algorithms › TAOCP 7.1.3: Bitwise Tricks and Techniques ›

TAOCP 7.1.3 Exercise 83

Let $\chi$ be a mask with exactly $2^d$ one-bits.

Practice › Mathematics › TAOCP › TAOCP Vol 4: Combinatorial Algorithms › TAOCP 7.1.3: Bitwise Tricks and Techniques ›

TAOCP 7.1.3 Exercise 84

Let $\chi$ contain exactly $2^d$ one-bits and let these bits occur at positions \chi = \sum_{j=0}^{2^d-1} 2^{p_j}, \qquad p_0 < p_1 < \cdots < p_{2^d-1}.

Practice › Mathematics › TAOCP › TAOCP Vol 4: Combinatorial Algorithms › TAOCP 7.1.3: Bitwise Tricks and Techniques ›

TAOCP 7.1.3 Exercise 85

Let $i=(i_4 i_3 i_2 i_1 i_0)_2$, $j=(j_4 j_3 j_2 j_1 j_0)_2$, $k=(k_4 k_3 k_2 k_1 k_0)_2$.

Practice › Mathematics › TAOCP › TAOCP Vol 4: Combinatorial Algorithms › TAOCP 7.1.3: Bitwise Tricks and Techniques ›

TAOCP 7.1.3 Exercise 86

Let the array indices satisfy \[ 0 \le i < 2^p,\quad 0 \le j < 2^q,\quad 0 \le k < 2^r, \] with binary expansions \[

Practice › Mathematics › TAOCP › TAOCP Vol 4: Combinatorial Algorithms › TAOCP 7.1.3: Bitwise Tricks and Techniques ›

TAOCP 7.1.3 Exercise 87

The solution does not correctly resolve the optimization problem.

Practice › Mathematics › TAOCP › TAOCP Vol 4: Combinatorial Algorithms › TAOCP 7.1.3: Bitwise Tricks and Techniques ›

TAOCP 7.1.3 Exercise 88

The solution does not correctly resolve the optimization problem.

Practice › Mathematics › TAOCP › TAOCP Vol 4: Combinatorial Algorithms › TAOCP 7.1.3: Bitwise Tricks and Techniques ›

TAOCP 7.1.3 Exercise 89

The solution does not address the stated problem at all.

Practice › Mathematics › TAOCP › TAOCP Vol 4: Combinatorial Algorithms › TAOCP 7.1.3: Bitwise Tricks and Techniques ›

TAOCP 7.1.3 Exercise 90

Represent the 32 base-$4$ digits packed into a word as two-bit fields.

Practice › Mathematics › TAOCP › TAOCP Vol 4: Combinatorial Algorithms › TAOCP 7.1.3: Bitwise Tricks and Techniques ›

TAOCP 7.1.3 Exercise 91

Represent the 32 base-$4$ digits packed into a word as two-bit fields.

Practice › Mathematics › TAOCP › TAOCP Vol 4: Combinatorial Algorithms › TAOCP 7.1.3: Bitwise Tricks and Techniques ›

TAOCP 7.1.3 Exercise 92

Represent the 32 base-$4$ digits packed into a word as two-bit fields.

Practice › Mathematics › TAOCP › TAOCP Vol 4: Combinatorial Algorithms › TAOCP 7.1.3: Bitwise Tricks and Techniques ›

TAOCP 7.1.3 Exercise 93

Formula (8q) for addition states the bitwise decomposition $x + y = (x \oplus y) + 2(x \mathbin{\&} y).$ To obtain the subtraction analogue, write $x - y = x + (-y).$ Using $,-y = \bar{y} + 1,$ from (...

Practice › Mathematics › TAOCP › TAOCP Vol 4: Combinatorial Algorithms › TAOCP 7.1.3: Bitwise Tricks and Techniques ›

TAOCP 7.1.3 Exercise 94

The operation defined in (qo) constructs each byte $t_j$ from the bytes of $x$ using only bytewise arithmetic and bitwise propagation between neighboring bytes.

Practice › Mathematics › TAOCP › TAOCP Vol 4: Combinatorial Algorithms › TAOCP 7.1.3: Bitwise Tricks and Techniques ›

TAOCP 7.1.3 Exercise 95

Let $\mu = (11111111)_{256}$, the word whose every byte equals $255$, so $\mu$ serves as a mask selecting all byte positions.

Practice › Mathematics › TAOCP › TAOCP Vol 4: Combinatorial Algorithms › TAOCP 7.1.3: Bitwise Tricks and Techniques ›

TAOCP 7.1.3 Exercise 96

For (93), the addition identity in (8q) has the form $x + y = (x \oplus y) + 2(x \,\&\, y).$ The subtraction analogue is obtained by replacing addition with subtraction and replacing carry propagation...

Practice › Mathematics › TAOCP › TAOCP Vol 4: Combinatorial Algorithms › TAOCP 7.1.3: Bitwise Tricks and Techniques ›

TAOCP 7.1.3 Exercise 97

The proposed solution does not address the problem stated in Exercise 7.

Practice › Mathematics › TAOCP › TAOCP Vol 4: Combinatorial Algorithms › TAOCP 7.1.3: Bitwise Tricks and Techniques ›

TAOCP 7.1.3 Exercise 98

Each byte $x_j$ and $y_j$ is interpreted as an unsigned 8-bit integer in ${0,\ldots,255}$.

Practice › Mathematics › TAOCP › TAOCP Vol 4: Combinatorial Algorithms › TAOCP 7.1.3: Bitwise Tricks and Techniques ›

TAOCP 7.1.3 Exercise 99

All operations act on octabytes bytewise, so the computation reduces to a single 8-bit word.

Practice › Mathematics › TAOCP › TAOCP Vol 4: Combinatorial Algorithms › TAOCP 7.1.3: Bitwise Tricks and Techniques ›

TAOCP 7.1.3 Exercise 100

Let $x = (x_{15}\ldots x_0)_{16}$ and $y = (y_{15}\ldots y_0)_{16}$, where each $x_j, y_j \in \{0,\ldots,9\}$.

Practice › Mathematics › TAOCP › TAOCP Vol 4: Combinatorial Algorithms › TAOCP 7.1.3: Bitwise Tricks and Techniques ›

TAOCP 7.1.3 Exercise 101

Let the word size be $64$ bits.

Practice › Mathematics › TAOCP › TAOCP Vol 4: Combinatorial Algorithms › TAOCP 7.1.3: Bitwise Tricks and Techniques ›

TAOCP 7.1.3 Exercise 102

The failure of the previous solution is structural: it tries to do SIMD comparison inside a word without eliminating inter-field carries during the comparison stage.

Practice › Mathematics › TAOCP › TAOCP Vol 4: Combinatorial Algorithms › TAOCP 7.1.3: Bitwise Tricks and Techniques ›

TAOCP 7.1.3 Exercise 103

We restart from the representation and rebuild both operations as direct bytewise bit manipulation.

Practice › Mathematics › TAOCP › TAOCP Vol 4: Combinatorial Algorithms › TAOCP 7.1.3: Bitwise Tricks and Techniques ›

TAOCP 7.1.3 Exercise 104

We restart the construction at the point where the original solution fails: the detection of $m=2$.

Practice › Mathematics › TAOCP › TAOCP Vol 4: Combinatorial Algorithms › TAOCP 7.1.3: Bitwise Tricks and Techniques ›

TAOCP 7.1.3 Exercise 105

Let $x = (x_7 \ldots x_0)_{256}$ and $y = (y_7 \ldots y_0)_{256}$, where each $x_i$ and $y_i$ is an 8-bit byte interpreted as an integer in ${0,\ldots,255}$.

Practice › Mathematics › TAOCP › TAOCP Vol 4: Combinatorial Algorithms › TAOCP 7.1.3: Bitwise Tricks and Techniques ›

TAOCP 7.1.3 Exercise 106

The Fredman–Willard procedure in (95) is a constant-time word operation that performs table lookup on a packed index encoded in a single machine word.

Practice › Mathematics › TAOCP › TAOCP Vol 4: Combinatorial Algorithms › TAOCP 7.1.3: Bitwise Tricks and Techniques ›

TAOCP 7.1.3 Exercise 107

The exercise asks for an MMIX implementation of Algorithm B specialized to digit size $d=4$, together with a comparison to equation (76).

Practice › Mathematics › TAOCP › TAOCP Vol 4: Combinatorial Algorithms › TAOCP 7.1.3: Bitwise Tricks and Techniques ›

TAOCP 7.1.3 Exercise 108

Let $m = d\cdot 2^d$ and let Algorithm B be a fixed sequence of primitive operations on vectors in $\{0,1\}^m$, where each primitive operation is either 1.

Practice › Mathematics › TAOCP › TAOCP Vol 4: Combinatorial Algorithms › TAOCP 7.1.3: Bitwise Tricks and Techniques ›

TAOCP 7.1.3 Exercise 109

Let $x = (x_{n-1}\ldots x_0)_2$.

Practice › Mathematics › TAOCP › TAOCP Vol 4: Combinatorial Algorithms › TAOCP 7.1.3: Bitwise Tricks and Techniques ›

TAOCP 7.1.3 Exercise 110

The previous argument fails because it treats $x$ as having only $e$ bits.

Practice › Mathematics › TAOCP › TAOCP Vol 4: Combinatorial Algorithms › TAOCP 7.1.3: Bitwise Tricks and Techniques ›

TAOCP 7.1.3 Exercise 111

Let the input word be x = (\ldots x_2 x_1 x_0)_2, and fix $r \ge 1$.

Practice › Mathematics › TAOCP › TAOCP Vol 4: Combinatorial Algorithms › TAOCP 7.1.3: Bitwise Tricks and Techniques ›

TAOCP 7.1.3 Exercise 112

We address the reviewer’s three critical points directly and restart from the correct interpretation of the pattern.

Practice › Mathematics › TAOCP › TAOCP Vol 4: Combinatorial Algorithms › TAOCP 7.1.3: Bitwise Tricks and Techniques ›

TAOCP 7.1.3 Exercise 113

Let $(x_0, x_1, \ldots, x_r)$ be a broadword chain of width $n$.

Practice › Mathematics › TAOCP › TAOCP Vol 4: Combinatorial Algorithms › TAOCP 7.1.3: Bitwise Tricks and Techniques ›

TAOCP 7.1.3 Exercise 114

The previous argument fails because it attempts to enforce lane independence in an $mn$-bit word without preventing carry propagation during arithmetic.

Practice › Mathematics › TAOCP › TAOCP Vol 4: Combinatorial Algorithms › TAOCP 7.1.3: Bitwise Tricks and Techniques ›

TAOCP 7.1.3 Exercise 115

Let $x = (\ldots x_2 x_1 x_0)_2.$ We use shift notation from (19)–(20), so $(x\gg k)_j = x_{j+k}$ and $(x\ll k)_j = x_{j-k}$.

Practice › Mathematics › TAOCP › TAOCP Vol 4: Combinatorial Algorithms › TAOCP 7.1.3: Bitwise Tricks and Techniques ›

TAOCP 7.1.3 Exercise 116

We restate the computational model carefully.

Practice › Mathematics › TAOCP › TAOCP Vol 4: Combinatorial Algorithms › TAOCP 7.1.3: Bitwise Tricks and Techniques ›

TAOCP 7.1.3 Exercise 117

The previous solution fails mainly because it invents a false periodicity property for general $2$-adic constants and then uses it to force finiteness.

Practice › Mathematics › TAOCP › TAOCP Vol 4: Combinatorial Algorithms › TAOCP 7.1.3: Bitwise Tricks and Techniques ›

TAOCP 7.1.3 Exercise 118

The previous argument fails because it does not formalize the computational model or justify either direction.

Practice › Mathematics › TAOCP › TAOCP Vol 4: Combinatorial Algorithms › TAOCP 7.1.3: Bitwise Tricks and Techniques ›

TAOCP 7.1.3 Exercise 119

We begin by restoring the missing definition (102), which is implicit in the surrounding broadword construction in Section 7.

Practice › Mathematics › TAOCP › TAOCP Vol 4: Combinatorial Algorithms › TAOCP 7.1.3: Bitwise Tricks and Techniques ›

TAOCP 7.1.3 Exercise 120

Let $R=\mathbb{Z}/2^n\mathbb{Z}$.

Practice › Mathematics › TAOCP › TAOCP Vol 4: Combinatorial Algorithms › TAOCP 7.1.3: Bitwise Tricks and Techniques ›

TAOCP 7.1.3 Exercise 121

Let $f:[0,2^n)\to[0,2^n)$ be a broadword function constructed without shift instructions, using only +,\;-,\;\cdot,\;\&,\;\mid,\;\oplus with arithmetic modulo $2^n$.

Practice › Mathematics › TAOCP › TAOCP Vol 4: Combinatorial Algorithms › TAOCP 7.1.3: Bitwise Tricks and Techniques ›

TAOCP 7.1.3 Exercise 122

Let $S$ be a finite set with $|S|=N$, and let $f:S\to S$.

Practice › Mathematics › TAOCP › TAOCP Vol 4: Combinatorial Algorithms › TAOCP 7.1.3: Bitwise Tricks and Techniques ›

TAOCP 7.1.3 Exercise 123

The previous argument fails because “dependency width” was not defined in a way that is stable under the actual word operations.

Practice › Mathematics › TAOCP › TAOCP Vol 4: Combinatorial Algorithms › TAOCP 7.1.3: Bitwise Tricks and Techniques ›

TAOCP 7.1.3 Exercise 124

The earlier solution failed because it replaced the required object $U_t \subseteq \{0,1\}^n$ by sets of indices and then incorrectly propagated a step-by-step pigeonhole argument.

Practice › Mathematics › TAOCP › TAOCP Vol 4: Combinatorial Algorithms › TAOCP 7.1.3: Bitwise Tricks and Techniques ›

TAOCP 7.1.3 Exercise 125

Theorem $P'$ is the analogue of Theorem $P$ in which every equality test of the form $E(x)=0$ appearing in the construction is replaced by $E(x)=\alpha_s$ for fixed constants $\alpha_s$.

Practice › Mathematics › TAOCP › TAOCP Vol 4: Combinatorial Algorithms › TAOCP 7.1.3: Bitwise Tricks and Techniques ›

TAOCP 7.1.3 Exercise 126

We restart the argument from the correct structural point: only **branching operations** can create distinguishability between inputs, and in this problem the relevant notion of “information growth” m...

Practice › Mathematics › TAOCP › TAOCP Vol 4: Combinatorial Algorithms › TAOCP 7.1.3: Bitwise Tricks and Techniques ›

TAOCP 7.1.3 Exercise 127

The original proof fails because it misclassifies arithmetic as $\mathrm{AC}^0$.

Practice › Mathematics › TAOCP › TAOCP Vol 4: Combinatorial Algorithms › TAOCP 7.1.3: Bitwise Tricks and Techniques ›

TAOCP 7.1.3 Exercise 128

Let $x \in {0,1}^n$ and let $\nu x = \sum_{i=1}^n x_i$, so $(\nu x)\bmod 2$ is the parity of the bits of $x$.

Practice › Mathematics › TAOCP › TAOCP Vol 4: Combinatorial Algorithms › TAOCP 7.1.3: Bitwise Tricks and Techniques ›

TAOCP 7.1.3 Exercise 129

We re-examine the claim in the TAOCP broadword model: > Does sideways addition require $\Omega(\log n)$ broadword steps?

Practice › Mathematics › TAOCP › TAOCP Vol 4: Combinatorial Algorithms › TAOCP 7.1.3: Bitwise Tricks and Techniques ›

TAOCP 7.1.3 Exercise 130

In the broadword (word-RAM) model used in TAOCP, a single machine step may include operations on an entire $n$-bit word such as: - bitwise Boolean operations, - addition and subtraction modulo $2^n$,...

Practice › Mathematics › TAOCP › TAOCP Vol 4: Combinatorial Algorithms › TAOCP 7.1.3: Bitwise Tricks and Techniques ›

TAOCP 7.1.3 Exercise 131

We use the standard representation from Section 7.

Practice › Mathematics › TAOCP › TAOCP Vol 4: Combinatorial Algorithms › TAOCP 7.1.3: Bitwise Tricks and Techniques ›

TAOCP 7.1.3 Exercise 132

Let $G$ be a graph on $V=\{0,1,\dots,n-1\}$.

Practice › Mathematics › TAOCP › TAOCP Vol 4: Combinatorial Algorithms › TAOCP 7.1.3: Bitwise Tricks and Techniques ›

TAOCP 7.1.3 Exercise 133

Let $G=(V,E)$.

Practice › Mathematics › TAOCP › TAOCP Vol 4: Combinatorial Algorithms › TAOCP 7.1.3: Bitwise Tricks and Techniques ›

TAOCP 7.1.3 Exercise 134

Working

Practice › Mathematics › TAOCP › TAOCP Vol 4: Combinatorial Algorithms › TAOCP 7.1.3: Bitwise Tricks and Techniques ›

TAOCP 7.1.3 Exercise 135

Start from representation (128), which encodes the three truth values as ordered Boolean pairs 0=(0,0),\quad *=(0,1),\quad 1=(1,1), so that $x=(x_0,x_1)$ with $x_0 \le x_1$.

Practice › Mathematics › TAOCP › TAOCP Vol 4: Combinatorial Algorithms › TAOCP 7.1.3: Bitwise Tricks and Techniques ›

TAOCP 7.1.3 Exercise 136

A correct treatment must start from the actual definition of “two-bit encoding”.

Practice › Mathematics › TAOCP › TAOCP Vol 4: Combinatorial Algorithms › TAOCP 7.1.3: Bitwise Tricks and Techniques ›

TAOCP 7.1.3 Exercise 137

We restart from a correct packed-word model and derive the operation at the level of bitplanes, ensuring that every symbol is handled as a complete 2-bit field.

Practice › Mathematics › TAOCP › TAOCP Vol 4: Combinatorial Algorithms › TAOCP 7.1.3: Bitwise Tricks and Techniques ›

TAOCP 7.1.3 Exercise 138

The previous solution correctly identified a valid encoding, but it failed to justify the “class $V_a$ is best” requirement in Knuth’s sense.

Practice › Mathematics › TAOCP › TAOCP Vol 4: Combinatorial Algorithms › TAOCP 7.1.3: Bitwise Tricks and Techniques ›

TAOCP 7.1.3 Exercise 139

Represent each signed bit $x \in {-1,0,1}$ by two signed bits $(x^+,x^-)$ defined by x^+ = \begin{cases} 1 & x=1\\ 0 & x\in\{0,-1\} \end{cases}

Practice › Mathematics › TAOCP › TAOCP Vol 4: Combinatorial Algorithms › TAOCP 7.1.3: Bitwise Tricks and Techniques ›

TAOCP 7.1.3 Exercise 140

Let $x,y,z \in {0,+1,-1}$.

Practice › Mathematics › TAOCP › TAOCP Vol 4: Combinatorial Algorithms › TAOCP 7.1.3: Bitwise Tricks and Techniques ›

TAOCP 7.1.3 Exercise 141

We restart the construction from a correct state model of representation counts and derive valid bit-parallel update rules.

Practice › Mathematics › TAOCP › TAOCP Vol 4: Combinatorial Algorithms › TAOCP 7.1.3: Bitwise Tricks and Techniques ›

TAOCP 7.1.3 Exercise 142

We work with subcubes (implicants) on variables $x_1,\dots,x_n$, where each coordinate is in $\{x_i,\bar x_i, *\}$.

Practice › Mathematics › TAOCP › TAOCP Vol 4: Combinatorial Algorithms › TAOCP 7.1.3: Bitwise Tricks and Techniques ›

TAOCP 7.1.3 Exercise 143

Represent the 8×8 board as a 64-bit word, where each bit corresponds to a square.

Practice › Mathematics › TAOCP › TAOCP Vol 4: Combinatorial Algorithms › TAOCP 7.1.3: Bitwise Tricks and Techniques ›

TAOCP 7.1.3 Exercise 144

In a sideways heap, nodes are indexed so that each node $j \ge 2$ has a unique parent $k = \lfloor j/2 \rfloor$, and the two children of $k$ are $2k$ and $2k+1$ as in the binary-heap structure describ...

Practice › Mathematics › TAOCP › TAOCP Vol 4: Combinatorial Algorithms › TAOCP 7.1.3: Bitwise Tricks and Techniques ›

TAOCP 7.1.3 Exercise 145

Let (137) denote the formula in Section 7.

Practice › Mathematics › TAOCP › TAOCP Vol 4: Combinatorial Algorithms › TAOCP 7.1.3: Bitwise Tricks and Techniques ›

TAOCP 7.1.3 Exercise 146

We restart from the formal definitions in (134)–(137) and use only their structural consequences.

Practice › Mathematics › TAOCP › TAOCP Vol 4: Combinatorial Algorithms › TAOCP 7.1.3: Bitwise Tricks and Techniques ›

TAOCP 7.1.3 Exercise 147

The key correction is that Algorithm V must be followed literally: vertices are scanned in the prescribed external order $v_1,\dots,v_n$, and pointers $\pi_v,\beta_v,\alpha_v$ are updated only when th...

Practice › Mathematics › TAOCP › TAOCP Vol 4: Combinatorial Algorithms › TAOCP 7.1.3: Bitwise Tricks and Techniques ›

TAOCP 7.1.3 Exercise 148

The flaw in the original solution is that it replaces the structure of $S$ with an unproved global equivalence.

Practice › Mathematics › TAOCP › TAOCP Vol 4: Combinatorial Algorithms › TAOCP 7.1.3: Bitwise Tricks and Techniques ›

TAOCP 7.1.3 Exercise 149

A correct preprocessing procedure must define all auxiliary structures in terms of a single deterministic traversal of the rooted forest, and each structure must be tied to a precise traversal event.

Practice › Mathematics › TAOCP › TAOCP Vol 4: Combinatorial Algorithms › TAOCP 7.1.3: Bitwise Tricks and Techniques ›

TAOCP 7.1.3 Exercise 150

We restart from a correct linear-time construction and give a complete justification.

Practice › Mathematics › TAOCP › TAOCP Vol 4: Combinatorial Algorithms › TAOCP 7.1.3: Bitwise Tricks and Techniques ›

TAOCP 7.1.3 Exercise 151

We correct the reduction by using the _proper Euler tour RMQ construction_, not the incorrect interval on first-occurrence indices alone.

Practice › Mathematics › TAOCP › TAOCP Vol 4: Combinatorial Algorithms › TAOCP 7.1.3: Bitwise Tricks and Techniques ›

TAOCP 7.1.3 Exercise 152

A correct proof must derive the tree structure and the query behavior directly from Algorithm V, without assuming Cartesian-tree or LCA properties.

Practice › Mathematics › TAOCP › TAOCP Vol 4: Combinatorial Algorithms › TAOCP 7.1.3: Bitwise Tricks and Techniques ›

TAOCP 7.1.3 Exercise 153

Let the navigation pile be as defined in (144), where the structure consists of nodes $1,2,\dots,n$ and each node stores exactly two navigation pointers, corresponding to its two possible links in the...

Practice › Mathematics › TAOCP › TAOCP Vol 4: Combinatorial Algorithms › TAOCP 7.1.3: Bitwise Tricks and Techniques ›

TAOCP 7.1.3 Exercise 154

We restart from the geometric structure actually defined by the gray segments.

Practice › Mathematics › TAOCP › TAOCP Vol 4: Combinatorial Algorithms › TAOCP 7.1.3: Bitwise Tricks and Techniques ›

TAOCP 7.1.3 Exercise 155

Let the negaFibonacci code of $x$ be the binary sequence $\alpha = (\alpha_k)_{k \ge 0}$ with $\alpha_k \in {0,1}$ and no consecutive $1$s, and let $x = \sum_{k \ge 0} \alpha_k F_{k+2},$ where $F_0 =...

Practice › Mathematics › TAOCP › TAOCP Vol 4: Combinatorial Algorithms › TAOCP 7.1.3: Bitwise Tricks and Techniques ›

TAOCP 7.1.3 Exercise 156

Working

Practice › Mathematics › TAOCP › TAOCP Vol 4: Combinatorial Algorithms › TAOCP 7.1.3: Bitwise Tricks and Techniques ›

TAOCP 7.1.3 Exercise 157

Let $\alpha = (\alpha_1,\alpha_2,\ldots,\alpha_m)$ be a negaFibonacci code in the sense of Section 7.

Practice › Mathematics › TAOCP › TAOCP Vol 4: Combinatorial Algorithms › TAOCP 7.1.3: Bitwise Tricks and Techniques ›

TAOCP 7.1.3 Exercise 158

Let the Fibonacci numbers be F_1=1,\quad F_2=2,\quad F_{k+2}=F_{k+1}+F_k.

Practice › Mathematics › TAOCP › TAOCP Vol 4: Combinatorial Algorithms › TAOCP 7.1.3: Bitwise Tricks and Techniques ›

TAOCP 7.1.3 Exercise 159

The key mistake in the proposed solution is the attempt to construct a direct “signed greedy” algorithm for negaFibonacci digits and to argue correctness via an incorrect Fibonacci identity.

Practice › Mathematics › TAOCP › TAOCP Vol 4: Combinatorial Algorithms › TAOCP 7.1.3: Bitwise Tricks and Techniques ›

TAOCP 7.1.3 Exercise 160

We restart from the definitions implicit in formulas (150) and (151) and prove directly that they generate identical labels, without introducing unproved intermediate tables.

Practice › Mathematics › TAOCP › TAOCP Vol 4: Combinatorial Algorithms › TAOCP 7.1.3: Bitwise Tricks and Techniques ›

TAOCP 7.1.3 Exercise 161

We restate the problem in graph-theoretic form.

Practice › Mathematics › TAOCP › TAOCP Vol 4: Combinatorial Algorithms › TAOCP 7.1.3: Bitwise Tricks and Techniques ›

TAOCP 7.1.3 Exercise 162

The previous solution fails because it replaces the actual object in Fig.

Practice › Mathematics › TAOCP › TAOCP Vol 4: Combinatorial Algorithms › TAOCP 7.1.3: Bitwise Tricks and Techniques ›

TAOCP 7.1.3 Exercise 163

The previous solution fails because it _assumes_ finiteness of triangle types without deriving it from the actual construction of Fig.

Practice › Mathematics › TAOCP › TAOCP Vol 4: Combinatorial Algorithms › TAOCP 7.1.3: Bitwise Tricks and Techniques ›

TAOCP 7.1.3 Exercise 164

Let the eight neighbors of a cell $X$ be $X_{NW}, X_N, X_{NE}, X_W, X_E, X_{SW}, X_S, X_{SE}$.

Practice › Mathematics › TAOCP › TAOCP Vol 4: Combinatorial Algorithms › TAOCP 7.1.3: Bitwise Tricks and Techniques ›

TAOCP 7.1.3 Exercise 165

Let the $3\times 3$ configuration at time $t$ be represented by a bit matrix $X(t) = (x_{ij}(t))_{1 \le i,j \le 3}$, where each $x_{ij}(t) \in {0,1}$.

Practice › Mathematics › TAOCP › TAOCP Vol 4: Combinatorial Algorithms › TAOCP 7.1.3: Bitwise Tricks and Techniques ›

TAOCP 7.1.3 Exercise 166

Let $X = \operatorname{custer}(X)$, where \operatorname{custer}(X)(i,j)=\overline{X(i,j)} \;\&\; S(i,j), \quad S(i,j)=X(i-1,j)\lor X(i+1,j)\lor X(i,j-1)\lor X(i,j+1).

Practice › Mathematics › TAOCP › TAOCP Vol 4: Combinatorial Algorithms › TAOCP 7.1.3: Bitwise Tricks and Techniques ›

TAOCP 7.1.3 Exercise 167

Let the eight neighbors be $a_1,\dots,a_8 \in \{0,1\}$ and the center be $b\in\{0,1\}$.

Practice › Mathematics › TAOCP › TAOCP Vol 4: Combinatorial Algorithms › TAOCP 7.1.3: Bitwise Tricks and Techniques ›

TAOCP 7.1.3 Exercise 168

We start by separating three independent issues: the word packing geometry, the toroidal indexing, and the correctness of the bit-parallel update.

Practice › Mathematics › TAOCP › TAOCP Vol 4: Combinatorial Algorithms › TAOCP 7.1.3: Bitwise Tricks and Techniques ›

TAOCP 7.1.3 Exercise 169

The state of a Life automaton on a finite torus is completely determined by the initial bitmap and the update rule given in Exercise 167.

Practice › Mathematics › TAOCP › TAOCP Vol 4: Combinatorial Algorithms › TAOCP 7.1.3: Bitwise Tricks and Techniques ›

TAOCP 7.1.3 Exercise 170

The previous argument fails because it models Guo–Hall thinning as uniform geometric erosion.

Practice › Mathematics › TAOCP › TAOCP Vol 4: Combinatorial Algorithms › TAOCP 7.1.3: Bitwise Tricks and Techniques ›

TAOCP 7.1.3 Exercise 171

The previous solution failed because it did not use the actual definition of $g$ from (159).

Practice › Mathematics › TAOCP › TAOCP Vol 4: Combinatorial Algorithms › TAOCP 7.1.3: Bitwise Tricks and Techniques ›

TAOCP 7.1.3 Exercise 172

Let the three black pixels be $a,b,c$ and assume they are pairwise king-neighbors.

Practice › Mathematics › TAOCP › TAOCP Vol 4: Combinatorial Algorithms › TAOCP 7.1.3: Bitwise Tricks and Techniques ›

TAOCP 7.1.3 Exercise 173

We restate the definitions precisely and then rebuild the argument from first principles.

Practice › Mathematics › TAOCP › TAOCP Vol 4: Combinatorial Algorithms › TAOCP 7.1.3: Bitwise Tricks and Techniques ›

TAOCP 7.1.3 Exercise 174

The previous argument correctly identifies a real obstruction: in three dimensions, simplicity of individual voxels is not preserved under simultaneous deletion.

Practice › Mathematics › TAOCP › TAOCP Vol 4: Combinatorial Algorithms › TAOCP 7.1.3: Bitwise Tricks and Techniques ›

TAOCP 7.1.3 Exercise 175

The reviewer is correct that the original argument is invalid because it replaces pixel-level adjacency with an invented semantic decomposition.

Practice › Mathematics › TAOCP › TAOCP Vol 4: Combinatorial Algorithms › TAOCP 7.1.3: Bitwise Tricks and Techniques ›

TAOCP 7.1.3 Exercise 176

Let $G$ be a graph on ${1,\ldots,n}$ and let $S={{u_j,v_j}\mid 1\le j\le r}$ be an $r$-family.

Practice › Mathematics › TAOCP › TAOCP Vol 4: Combinatorial Algorithms › TAOCP 7.1.3: Bitwise Tricks and Techniques ›

TAOCP 7.1.3 Exercise 177

The central issue is that the original write-up appealed to an informal “black/white symmetry” without exhibiting the actual invariant structure.

Practice › Mathematics › TAOCP › TAOCP Vol 4: Combinatorial Algorithms › TAOCP 7.1.3: Bitwise Tricks and Techniques ›

TAOCP 7.1.3 Exercise 178

Let the columns of the original bitmap $X$ be indexed by $0,1,\ldots,N-1$.

Practice › Mathematics › TAOCP › TAOCP Vol 4: Combinatorial Algorithms › TAOCP 7.1.3: Bitwise Tricks and Techniques ›

TAOCP 7.1.3 Exercise 179

The failure in the proposed solution is not a technical detail.

Practice › Mathematics › TAOCP › TAOCP Vol 4: Combinatorial Algorithms › TAOCP 7.1.3: Bitwise Tricks and Techniques ›

TAOCP 7.1.3 Exercise 180

Let F(x,y)=y^{2}-x^{2}-13.

Practice › Mathematics › TAOCP › TAOCP Vol 4: Combinatorial Algorithms › TAOCP 7.1.3: Bitwise Tricks and Techniques ›

TAOCP 7.1.3 Exercise 181

Let the conic be given by F(x,y)=ax^2+bxy+cy^2+dx+ey+f=0,\qquad a,b,c,d,e,f\in\mathbb{Q}.

Practice › Mathematics › TAOCP › TAOCP Vol 4: Combinatorial Algorithms › TAOCP 7.1.3: Bitwise Tricks and Techniques ›

TAOCP 7.1.3 Exercise 182

Let F(x,y)=ax^2+bxy+cy^2+dx+ey+g define the conic, and let the algorithm operate on a segment of the curve on which, say, $x$ is strictly increasing (the other case is symmetric).

Practice › Mathematics › TAOCP › TAOCP Vol 4: Combinatorial Algorithms › TAOCP 7.1.3: Bitwise Tricks and Techniques ›

TAOCP 7.1.3 Exercise 183

Let $F(x,y)$ be the integer-valued function defining the conic, as in Algorithm T.

Practice › Mathematics › TAOCP › TAOCP Vol 4: Combinatorial Algorithms › TAOCP 7.1.3: Bitwise Tricks and Techniques ›

TAOCP 7.1.3 Exercise 184

Let Algorithm T be applied to the endpoints $(x,y)$ and $(x',y')$ with quadratic form $Q$, producing a sequence of edges determined by the sign changes of $Q$ along the digitized path from $(x,y)$ to...

Practice › Mathematics › TAOCP › TAOCP Vol 4: Combinatorial Algorithms › TAOCP 7.1.3: Bitwise Tricks and Techniques ›

TAOCP 7.1.3 Exercise 185

Let the endpoints be rational numbers (\xi,\eta)=\left(\frac{a}{c},\frac{b}{c}\right), \qquad (\xi',\eta')=\left(\frac{a'}{c'},\frac{b'}{c'}\right), where $a,b,a',b' \in \mathbb{Z}$ and $c,c' \in \mat...

Practice › Mathematics › TAOCP › TAOCP Vol 4: Combinatorial Algorithms › TAOCP 7.1.3: Bitwise Tricks and Techniques ›

TAOCP 7.1.3 Exercise 186

Let B(t) = (1-t)^2 z_0 + 2(1-t)t z_1 + t^2 z_2, \qquad 0 \le t \le 1.

Practice › Mathematics › TAOCP › TAOCP Vol 4: Combinatorial Algorithms › TAOCP 7.1.3: Bitwise Tricks and Techniques ›

TAOCP 7.1.3 Exercise 187

The failure in the previous solution is the assumption that the right subsegment must be explicitly stored.

Practice › Mathematics › TAOCP › TAOCP Vol 4: Combinatorial Algorithms › TAOCP 7.1.3: Bitwise Tricks and Techniques ›

TAOCP 7.1.3 Exercise 188

The failure in the previous solution is fundamental: the bitmap is 1-bit packed, so each pixel must be extracted by bit operations, not by byte-wise `LDB` interpretation.

Practice › Mathematics › TAOCP › TAOCP Vol 4: Combinatorial Algorithms › TAOCP 7.1.3: Bitwise Tricks and Techniques ›

TAOCP 7.1.3 Exercise 189

Let the bitmap be stored as $8$ consecutive rows of bytes per block column.

Practice › Mathematics › TAOCP › TAOCP Vol 4: Combinatorial Algorithms › TAOCP 7.1.3: Bitwise Tricks and Techniques ›

TAOCP 7.1.3 Exercise 190

We correct the solution by rebuilding the argument from the linear structure of the parity condition and avoiding any invalid submatrix or periodicity assumptions.

Practice › Mathematics › TAOCP › TAOCP Vol 4: Combinatorial Algorithms › TAOCP 7.1.3: Bitwise Tricks and Techniques ›

TAOCP 7.1.3 Exercise 191

Work in the ring R=\mathbb{F}_2[x,x^{-1}]/(x^N+1), \qquad N=2n+2, so that $x^{-1}=x^{N-1}$.

Practice › Mathematics › TAOCP › TAOCP Vol 4: Combinatorial Algorithms › TAOCP 7.1.3: Bitwise Tricks and Techniques ›

TAOCP 7.1.3 Exercise 192

We restart from the actual combinatorial structure of parity patterns and only use identities for Fibonacci polynomials that can be derived directly from their defining recurrence.

Practice › Mathematics › TAOCP › TAOCP Vol 4: Combinatorial Algorithms › TAOCP 7.1.3: Bitwise Tricks and Techniques ›

TAOCP 7.1.3 Exercise 193

Let $A=(a_{i,j})$ be a perfect $m\times n$ parity pattern, so for every $i,j$, a_{i,j}\equiv \sum_{j'\ne j} a_{i,j'}+\sum_{i'\ne i} a_{i',j}\pmod 2, and no row or column of $A$ is identically zero.

Practice › Mathematics › TAOCP › TAOCP Vol 4: Combinatorial Algorithms › TAOCP 7.1.3: Bitwise Tricks and Techniques ›

TAOCP 7.1.3 Exercise 194

A perfect parity pattern of width $n$ is equivalent to a solution of the linear constraints from Section 7.

Practice › Mathematics › TAOCP › TAOCP Vol 4: Combinatorial Algorithms › TAOCP 7.1.3: Bitwise Tricks and Techniques ›

TAOCP 7.1.3 Exercise 195

Let $A$ be the binary matrix with rows $\alpha_1,\ldots,\alpha_m \in {0,1}^n$.

Practice › Mathematics › TAOCP › TAOCP Vol 4: Combinatorial Algorithms › TAOCP 7.1.3: Bitwise Tricks and Techniques ›

TAOCP 7.1.3 Exercise 196

The solution must be rebuilt from the actual definitions, not from byte-range heuristics.

Practice › Mathematics › TAOCP › TAOCP Vol 4: Combinatorial Algorithms › TAOCP 7.1.3: Bitwise Tricks and Techniques ›

TAOCP 7.1.3 Exercise 197

Let $x$ be a codepoint in $0 \le x < 2^{20}+2^{16}$.

Practice › Mathematics › TAOCP › TAOCP Vol 4: Combinatorial Algorithms › TAOCP 7.1.3: Bitwise Tricks and Techniques ›

TAOCP 7.1.3 Exercise 198

Let $l$ be the number of bytes in the UTF-8 encoding of $x$.

Practice › Mathematics › TAOCP › TAOCP Vol 4: Combinatorial Algorithms › TAOCP 7.1.3: Bitwise Tricks and Techniques ›

TAOCP 7.1.3 Exercise 199

We restart from the actual existence condition.

Practice › Mathematics › TAOCP › TAOCP Vol 4: Combinatorial Algorithms › TAOCP 7.1.3: Bitwise Tricks and Techniques ›

TAOCP 7.1.3 Exercise 200

In MMIX, register $0$ is the constant zero register, so its contents are $0$.

Practice › Mathematics › TAOCP › TAOCP Vol 4: Combinatorial Algorithms › TAOCP 7.1.3: Bitwise Tricks and Techniques ›

TAOCP 7.1.3 Exercise 201

Let $x = (x_{15}\ldots x_1 x_0)_{16}$, where each $x_i \in {0,\ldots,15}$ is a hexadecimal digit.

Practice › Mathematics › TAOCP › TAOCP Vol 4: Combinatorial Algorithms › TAOCP 7.1.3: Bitwise Tricks and Techniques ›

TAOCP 7.1.3 Exercise 202

The previous solution fails for a structural reason: it replaces the required _wydewise predicate_ w \mapsto [w\neq 0]\cdot \#ffff with bytewise reasoning and then assumes a non-existent “merge-to-wyd...

Practice › Mathematics › TAOCP › TAOCP Vol 4: Combinatorial Algorithms › TAOCP 7.1.3: Bitwise Tricks and Techniques ›

TAOCP 7.1.3 Exercise 203

We restart from the actual MMIX semantics used in TAOCP.

Practice › Mathematics › TAOCP › TAOCP Vol 4: Combinatorial Algorithms › TAOCP 7.1.3: Bitwise Tricks and Techniques ›

TAOCP 7.1.3 Exercise 204

The failure in the previous construction comes from a false invariant: masking with x \,\&\, 0xFFFFFFFF00000000 does not produce a normalized 32-bit quantity.

Practice › Mathematics › TAOCP › TAOCP Vol 4: Combinatorial Algorithms › TAOCP 7.1.3: Bitwise Tricks and Techniques ›

TAOCP 7.1.3 Exercise 205

Let the perfect shuffle of Exercise 204 be the MMIX program obtained in (175)–(178), using constants $p, q, r, m$, and let it map an input register state $z$ to an output state $w$.

Practice › Mathematics › TAOCP › TAOCP Vol 4: Combinatorial Algorithms › TAOCP 7.1.3: Bitwise Tricks and Techniques ›

TAOCP 7.1.3 Exercise 206

Let the input word $z$ be split into two halves $x$ and $y$, each consisting of 32 bits, so that $z = (x,y)$ in concatenated form.

Practice › Mathematics › TAOCP › TAOCP Vol 4: Combinatorial Algorithms › TAOCP 7.1.3: Bitwise Tricks and Techniques ›

TAOCP 7.1.3 Exercise 207

The reviewer is correct that the previous solution failed at the logical foundation: it _asserted_ multiplication by $21$ without deriving it from the shuffle.

Practice › Mathematics › TAOCP › TAOCP Vol 4: Combinatorial Algorithms › TAOCP 7.1.3: Bitwise Tricks and Techniques ›

TAOCP 7.1.3 Exercise 208

The previous construction fails because it tries to realize the transpose as swaps at fixed index distances in the full 64-bit linearization.

Practice › Mathematics › TAOCP › TAOCP Vol 4: Combinatorial Algorithms › TAOCP 7.1.3: Bitwise Tricks and Techniques ›

TAOCP 7.1.3 Exercise 209

The solution must address the actual object in Exercise 36, namely the suffix parity transformation $x^{\oplus}$, and relate it to what MXOR can compute.

Practice › Mathematics › TAOCP › TAOCP Vol 4: Combinatorial Algorithms › TAOCP 7.1.3: Bitwise Tricks and Techniques ›

TAOCP 7.1.3 Exercise 210

Let $x$ contain $8j+k$ with $0 \le j,k < 8$.

Practice › Mathematics › TAOCP › TAOCP Vol 4: Combinatorial Algorithms › TAOCP 7.1.3: Bitwise Tricks and Techniques ›

TAOCP 7.1.3 Exercise 211

Index the $64$ entries of $f$ by vectors $x = (x_1,\dots,x_6) \in {0,1}^6$, and write \hat f(x) = \bigvee_{y \le x} f(y), where $y \le x$ means $y_i \le x_i$ for all $i$, so $\hat f$ is the least mono...

Practice › Mathematics › TAOCP › TAOCP Vol 4: Combinatorial Algorithms › TAOCP 7.1.3: Bitwise Tricks and Techniques ›

TAOCP 7.1.3 Exercise 212

Let $a = (a_{63}\dots a_1 a_0)_2,\qquad b = (b_{63}\dots b_1 b_0)_2,$ and interpret them as polynomials over $\mathbb{F}_2$, $a(x)=\sum_{i=0}^{63} a_i x^i,\qquad b(x)=\sum_{j=0}^{63} b_j x^j.$ The pro...

Practice › Mathematics › TAOCP › TAOCP Vol 4: Combinatorial Algorithms › TAOCP 7.1.3: Bitwise Tricks and Techniques ›

TAOCP 7.1.3 Exercise 213

The original solution fails because it does not implement the correct byte insertion into the polynomial register and therefore does not preserve the CRC invariant.

Practice › Mathematics › TAOCP › TAOCP Vol 4: Combinatorial Algorithms › TAOCP 7.1.3: Bitwise Tricks and Techniques ›

TAOCP 7.1.3 Exercise 214

A complete branchless solution must make the pivot selection explicit.

Practice › Mathematics › TAOCP › TAOCP Vol 4: Combinatorial Algorithms › TAOCP 7.1.3: Bitwise Tricks and Techniques ›

TAOCP 7.1.3 Exercise 215

Solution to TAOCP 7.1.3 Exercise 215.

Practice › Mathematics › TAOCP › TAOCP Vol 4: Combinatorial Algorithms › TAOCP 7.1.3: Bitwise Tricks and Techniques ›

TAOCP 7.1.3 Exercise 216

Working

Practice › Mathematics › TAOCP › TAOCP Vol 4: Combinatorial Algorithms › TAOCP 7.1.3: Bitwise Tricks and Techniques ›

TAOCP 7.1.3 Exercise 217

Let a string consist of 64 characters $c_0,\ldots,c_{63}$, each character being an 8-bit vector $c_i = (c_{i,7},c_{i,6},\ldots,c_{i,0}), \qquad c_{i,k} \in \{0,1\}.$ Define eight 64-bit words $w_0,\ld...

Practice › Mathematics › TAOCP › TAOCP Vol 4: Combinatorial Algorithms › TAOCP 7.1.3: Bitwise Tricks and Techniques ›

TAOCP 7.1.3 Exercise 218

Let $d \ge 3$ be fixed.

Practice › Mathematics › TAOCP › TAOCP Vol 4: Combinatorial Algorithms › TAOCP 7.1.3: Bitwise Tricks and Techniques ›

TAOCP 7.1.3 Exercise 219

Let $x\ge 0$ be an integer and define t = x \,\&\, (x+1), \qquad s = t \gg 1, and repeat