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
|
\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}
TODO % zsplit
\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
|
