\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
