1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
|
\chapter{Bit operations}
\label{chap:Bit operations}
TODO
\vspace{1cm}
\minitoc
\newpage
\section{Boundary}
\label{sec:Boundary}
TODO % zbits zlsb
\newpage
\section{Shift}
\label{sec:Shift}
There are two functions for shifting bits
in integers:
\begin{alltt}
void zlsh(z_t r, z_t a, size_t b);
void zrsh(z_t r, z_t a, size_t b);
\end{alltt}
\noindent
{\tt zlsh} performs a left-shift, and {\tt zrsh}
performs a right-shift. That is, {\tt zlsh} adds
{\tt b} trailing binary zeroes, and {\tt zrsh}
removes the lowest {\tt b} binary digits. So if
$a = \phantom{00}10000101_2$ then
$r = 1000010100_2$ after calling {\tt zlsh(r, a, 2)}, and
$r = \phantom{0100}100001_2$ after calling {\tt zrsh(r, a, 2)}.
\vspace{1em}
{\tt zlsh(r, a, b)} is equivalent to $r \gets a \cdot 2^b$,
and {\tt zrsh(r, a, b)} is equivalent to $r \gets a \div 2^b$,
with truncated division, {\tt zlsh} and {\tt zrsh} are
significantly faster than {\tt zpowu} and should be used
whenever possible. {\tt zpowu} does not check if it is
possible for it to use {\tt zlsh} instead, even if it
would, {\tt zlsh} and {\tt zrsh} would still be preferable
in most cases because it removes the need for {\tt zmul}
and {\tt zdiv}, respectively.
{\tt zlsh} and {\tt zrsh} are implemented in two steps:
(1) shift whole characters, that is, groups of aligned
64 bits, and (2) shift on a bit-level between characters.
If you are implementing a calculator, you may want to
create a wrapper for {\tt zpow} that uses {\tt zlsh}
whenever possible. One such wrapper could be
\begin{alltt}
void
pow(z_t r, z_t a, z_t b)
\{
size_t s1, s2;
if ((s1 = zlsb(a)) + 1 == zbits(a) &&
zbits(b) <= 8 * sizeof(SIZE_MAX)) \{
s2 = zzero(b) ? 0 : b->chars[0];
if (s1 <= SIZE_MAX / s2) \{
zsetu(r, 1);
zlsh(r, r, s1 * s2);
return;
\}
\}
zpow(r, a, b);
\}
\end{alltt}
\newpage
\section{Truncation}
\label{sec:Truncation}
In \secref{sec:Shift} we have seen how bit-shift
operations can be used to multiply or divide by a
power of two. There is also a bit-truncation
operation: {\tt ztrunc}, which is used to keep
only the lowest bits, or equivalently, calculate
the remainder of a division by a power of two.
\begin{alltt}
void ztrunc(z_t r, z_t a, size_t b);
\end{alltt}
\noindent
is consistent with {\tt zmod}; like {\tt zlsh} and
{\tt zrsh}, {\tt a}'s sign is preserved into {\tt r}
assuming the result is non-zero.
{\tt ztrunc(r, a, b)} stores only the lowest {\tt b}
bits in {\tt a} into {\tt r}, or equivalently,
calculates $r \gets a \mod 2^b$. For example, if
$a = 100011000_2$ then
$r = \phantom{10001}1000_2$ after calling
{\tt ztrunc(r, a, 4)}.
\newpage
\section{Split}
\label{sec:Split}
In \secref{sec:Shift} and \secref{sec:Truncation}
we have seen how bit operations can be used to
calculate division by a power of two and
modulus a power of two efficiently using
bit-shift and bit-truncation operations. libzahl
also has a bit-split operation that can be used
to efficently calculate both division and
modulus a power of two efficiently in the same
operation, or equivalently, storing low bits
in one integer and high bits in another integer.
This function is
\begin{alltt}
void zsplit(z_t high, z_t low, z_t a, size_t b);
\end{alltt}
\noindent
Unlike {\tt zdivmod}, it is not more efficient
than calling {\tt zrsh} and {\tt ztrunc}, but
it is more convenient. {\tt zsplit} requires
that {\tt high} and {\tt low} are from each
other distinct references.
Calling {\tt zsplit(high, low, a, b)} is
equivalent to
\begin{alltt}
ztrunc(low, a, delim);
zrsh(high, a, delim);
\end{alltt}
\noindent
assuming {\tt a} and {\tt low} are not the
same reference (reverse the order of the
functions if they are the same reference.)
{\tt zsplit} copies the lowest {\tt b} bits
of {\tt a} to {\tt low}, and the rest of the
bits to {\tt high}, with the lowest {\tt b}
removesd. For example, if $a = 1010101111_2$,
then $high = 101010_2$ and $low = 1111_2$
after calling {\tt zsplit(high, low, a, 4)}.
{\tt zsplit} is especially useful in
divide-and-conquer algorithms.
\newpage
\section{Bit manipulation}
\label{sec:Bit manipulation}
TODO % zbset
\newpage
\section{Bit test}
\label{sec:Bit test}
TODO % zbtest
\newpage
\section{Logic}
\label{sec:Logic}
TODO % zand zor zxor znot
|
