bit-operations.tex - libzahl - big integer library
HTML git clone git://git.suckless.org/libzahl
DIR Log
DIR Files
DIR Refs
DIR README
DIR LICENSE
---
bit-operations.tex (8816B)
---
1 \chapter{Bit operations}
2 \label{chap:Bit operations}
3
4 libzahl provides a number of functions that operate on
5 bits. These can sometimes be used instead of arithmetic
6 functions for increased performance. You should read
7 the sections in order.
8
9 \vspace{1cm}
10 \minitoc
11
12
13 \newpage
14 \section{Boundary}
15 \label{sec:Boundary}
16
17 To retrieve the index of the lowest set bit, use
18
19 \begin{alltt}
20 size_t zlsb(z_t a);
21 \end{alltt}
22
23 \noindent
24 It will return a zero-based index, that is, if the
25 least significant bit is indeed set, it will return 0.
26
27 If {\tt a} is a power of 2, it will return the power
28 of which 2 is raised, effectively calculating the
29 binary logarithm of {\tt a}. Note, this is only if
30 {\tt a} is a power of two. More generally, it returns
31 the number of trailing binary zeroes, if equivalently
32 the number of times {\tt a} can evenly be divided by
33 2. However, in the special case where $a = 0$,
34 {\tt SIZE\_MAX} is returned.
35
36 A similar function is
37
38 \begin{alltt}
39 size_t zbit(z_t a);
40 \end{alltt}
41
42 \noindent
43 It returns the minimal number of bits require to
44 represent an integer. That is, $\lceil \log_2 a \rceil - 1$,
45 or equivalently, the number of times {\tt a} can be
46 divided by 2 before it gets the value 0. However, in
47 the special case where $a = 0$, 1 is returned. 0 is
48 never returned. If you want the value 0 to be returned
49 if $a = 0$, write
50
51 \begin{alltt}
52 zzero(a) ? 0 : zbits(a)
53 \end{alltt}
54
55 The definition ``it returns the minimal number
56 of bits required to represent an integer,''
57 holds true if $a = 0$, the other divisions
58 do not hold true if $a = 0$.
59
60
61 \newpage
62 \section{Shift}
63 \label{sec:Shift}
64
65 There are two functions for shifting bits
66 in integers:
67
68 \begin{alltt}
69 void zlsh(z_t r, z_t a, size_t b);
70 void zrsh(z_t r, z_t a, size_t b);
71 \end{alltt}
72
73 \noindent
74 {\tt zlsh} performs a left-shift, and {\tt zrsh}
75 performs a right-shift. That is, {\tt zlsh} adds
76 {\tt b} trailing binary zeroes, and {\tt zrsh}
77 removes the lowest {\tt b} binary digits. So if
78
79 $a = \phantom{00}10000101_2$ then
80
81 $r = 1000010100_2$ after calling {\tt zlsh(r, a, 2)}, and
82
83 $r = \phantom{0100}100001_2$ after calling {\tt zrsh(r, a, 2)}.
84 \vspace{1em}
85
86 {\tt zlsh(r, a, b)} is equivalent to $r \gets a \cdot 2^b$,
87 and {\tt zrsh(r, a, b)} is equivalent to $r \gets a \div 2^b$,
88 with truncated division, {\tt zlsh} and {\tt zrsh} are
89 significantly faster than {\tt zpowu} and should be used
90 whenever possible. {\tt zpowu} does not check if it is
91 possible for it to use {\tt zlsh} instead, even if it
92 would, {\tt zlsh} and {\tt zrsh} would still be preferable
93 in most cases because it removes the need for {\tt zmul}
94 and {\tt zdiv}, respectively.
95
96 {\tt zlsh} and {\tt zrsh} are implemented in two steps:
97 (1) shift whole characters, that is, groups of aligned
98 64 bits, and (2) shift on a bit-level between characters.
99
100 If you are implementing a calculator, you may want to
101 create a wrapper for {\tt zpow} that uses {\tt zlsh}
102 whenever possible. One such wrapper could be
103
104 \begin{alltt}
105 void
106 pow(z_t r, z_t a, z_t b)
107 \{
108 size_t s1, s2;
109 if ((s1 = zlsb(a)) + 1 == zbits(a) &&
110 zbits(b) <= 8 * sizeof(SIZE_MAX)) \{
111 s2 = zzero(b) ? 0 : b->chars[0];
112 if (s1 <= SIZE_MAX / s2) \{
113 zsetu(r, 1);
114 zlsh(r, r, s1 * s2);
115 return;
116 \}
117 \}
118 zpow(r, a, b);
119 \}
120 \end{alltt}
121
122
123 \newpage
124 \section{Truncation}
125 \label{sec:Truncation}
126
127 In \secref{sec:Shift} we have seen how bit-shift
128 operations can be used to multiply or divide by a
129 power of two. There is also a bit-truncation
130 operation: {\tt ztrunc}, which is used to keep
131 only the lowest bits, or equivalently, calculate
132 the remainder of a division by a power of two.
133
134 \begin{alltt}
135 void ztrunc(z_t r, z_t a, size_t b);
136 \end{alltt}
137
138 \noindent
139 is consistent with {\tt zmod}; like {\tt zlsh} and
140 {\tt zrsh}, {\tt a}'s sign is preserved into {\tt r}
141 assuming the result is non-zero.
142
143 {\tt ztrunc(r, a, b)} stores only the lowest {\tt b}
144 bits in {\tt a} into {\tt r}, or equivalently,
145 calculates $r \gets a \mod 2^b$. For example, if
146
147 $a = 100011000_2$ then
148
149 $r = \phantom{10001}1000_2$ after calling
150 {\tt ztrunc(r, a, 4)}.
151
152
153 \newpage
154 \section{Split}
155 \label{sec:Split}
156
157 In \secref{sec:Shift} and \secref{sec:Truncation}
158 we have seen how bit operations can be used to
159 calculate division by a power of two and
160 modulus a power of two efficiently using
161 bit-shift and bit-truncation operations. libzahl
162 also has a bit-split operation that can be used
163 to efficiently calculate both division and
164 modulus a power of two efficiently in the same
165 operation, or equivalently, storing low bits
166 in one integer and high bits in another integer.
167 This function is
168
169 \begin{alltt}
170 void zsplit(z_t high, z_t low, z_t a, size_t b);
171 \end{alltt}
172
173 \noindent
174 Unlike {\tt zdivmod}, it is not more efficient
175 than calling {\tt zrsh} and {\tt ztrunc}, but
176 it is more convenient. {\tt zsplit} requires
177 that {\tt high} and {\tt low} are from each
178 other distinct references.
179
180 Calling {\tt zsplit(high, low, a, b)} is
181 equivalent to
182
183 \begin{alltt}
184 ztrunc(low, a, delim);
185 zrsh(high, a, delim);
186 \end{alltt}
187
188 \noindent
189 assuming {\tt a} and {\tt low} are not the
190 same reference (reverse the order of the
191 functions if they are the same reference.)
192
193 {\tt zsplit} copies the lowest {\tt b} bits
194 of {\tt a} to {\tt low}, and the rest of the
195 bits to {\tt high}, with the lowest {\tt b}
196 removesd. For example, if $a = 1010101111_2$,
197 then $high = 101010_2$ and $low = 1111_2$
198 after calling {\tt zsplit(high, low, a, 4)}.
199
200 {\tt zsplit} is especially useful in
201 divide-and-conquer algorithms.
202
203
204 \newpage
205 \section{Bit manipulation}
206 \label{sec:Bit manipulation}
207
208
209 The function
210
211 \begin{alltt}
212 void zbset(z_t r, z_t a, size_t bit, int mode);
213 \end{alltt}
214
215 \noindent
216 is used to manipulate single bits in {\tt a}. It will
217 copy {\tt a} into {\tt r} and then, in {\tt r}, either
218 set, clear, or flip, the bit with the index {\tt bit}
219 — the least significant bit has the index 0. The
220 action depend on the value of {\tt mode}:
221
222 \begin{itemize}
223 \item
224 $mode > 0$ ($+1$): set
225 \item
226 $mode = 0$ ($0$): clear
227 \item
228 $mode < 0$ ($-1$): flip
229 \end{itemize}
230
231
232 \newpage
233 \section{Bit test}
234 \label{sec:Bit test}
235
236 libzahl provides a function for testing whether a bit
237 in a big integer is set:
238
239 \begin{alltt}
240 int zbtest(z_t a, size_t bit);
241 \end{alltt}
242
243 \noindent
244 it will return 1 if the bit with the index {\tt bit}
245 is set in {\tt a}, counting from the least significant
246 bit, starting at zero. 0 is returned otherwise. The
247 sign of {\tt a} is ignored.
248
249 We can think of this like so: consider
250
251 $$ \lvert a \rvert = \sum_{i = 0}^\infty k_i 2^i,~ k_i \in \{0, 1\}, $$
252
253 \noindent
254 {\tt zbtest(a, b)} returns $k_b$. Equivalently, we can
255 think that {\tt zbtest(a, b)} return whether $b \in B$
256 where $B$ is defined by
257
258 $$ \lvert a \rvert = \sum_{b \in B} 2^b,~ B \subset \textbf{Z}_+, $$
259
260 \noindent
261 or as right-shifting $a$ by $b$ bits and returning
262 whether the least significant bit is set.
263
264 {\tt zbtest} always returns 1 or 0, but for good
265 code quality, you should avoid testing against 1,
266 rather you should test whether the value is a
267 truth-value or a falsehood-value. However, there
268 is nothing wrong with depending on the value being
269 restricted to being either 1 or 0 if you want to
270 sum up returned values or otherwise use them in
271 new values.
272
273
274 \newpage
275 \section{Connectives}
276 \label{sec:Connectives}
277
278 libzahl implements the four basic logical
279 connectives: and, or, exclusive or, and not.
280 The functions for these are named {\tt zand},
281 {\tt zor}, {\tt zxor}, and {\tt znot},
282 respectively.
283
284 The connectives apply to each bit in the
285 integers, as well as the sign. The sign is
286 treated as a bit that is set if the integer
287 is negative, and as cleared otherwise. For
288 example (integers are in binary):
289
290 \begin{alltt}
291 zand(r, a, b) zor(r, a, b)
292 a = +1010 (input) a = +1010 (input)
293 b = -1100 (input) b = -1100 (input)
294 r = +1000 (output) r = -1110 (output)
295
296 zxor(r, a, b) znot(r, a)
297 a = +1010 (input) a = +1010 (input)
298 b = -1100 (input) r = -0101 (output)
299 r = -0110 (output)
300 \end{alltt}
301
302 Remember, in libzahl, integers are represented
303 with sign and magnitude, not two's complement,
304 even when using these connectives. Therefore,
305 more work than just changing the name of the
306 called function may be required when moving
307 between big integer libraries. Consequently,
308 {\tt znot} does not flip bits that are higher
309 than the highest set bit, which means that
310 {\tt znot} is nilpotent rather than self dual.
311
312 Below is a list of the value of {\tt a} when
313 {\tt znot(a, a)} is called repeatedly.
314
315 \begin{alltt}
316 10101010
317 -1010101
318 101010
319 -10101
320 1010
321 -101
322 10
323 -1
324 0
325 0
326 0
327 \end{alltt}