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}