\chapter{Bit operations}
\label{chap:Bit operations}

libzahl provides a number of functions that operate on
bits. These can sometimes be used instead of arithmetic
functions for increased performance. You should read
the sections in order.

\vspace{1cm}
\minitoc


\newpage
\section{Boundary}
\label{sec:Boundary}

To retrieve the index of the lowest set bit, use

\begin{alltt}
   size_t zlsb(z_t a);
\end{alltt}

\noindent
It will return a zero-based index, that is, if the
least significant bit is indeed set, it will return 0.

If {\tt a} is a power of 2, it will return the power
of which 2 is raised, effectively calculating the
binary logarithm of {\tt a}. Note, this is only if
{\tt a} is a power of two. More generally, it returns
the number of trailing binary zeroes, if equivalently
the number of times {\tt a} can evenly be divided by
2. However, in the special case where $a = 0$,
{\tt SIZE\_MAX} is returned.

A similar function is

\begin{alltt}
   size_t zbit(z_t a);
\end{alltt}

\noindent
It returns the minimal number of bits require to
represent an integer. That is, $\lceil \log_2 a \rceil - 1$,
or equivalently, the number of times {\tt a} can be
divided by 2 before it gets the value 0. However, in
the special case where $a = 0$, 1 is returned. 0 is
never returned. If you want the value 0 to be returned
if $a = 0$, write

\begin{alltt}
   zzero(a) ? 0 : zbits(a)
\end{alltt}

The definition ``it returns the minimal number
of bits required to represent an integer,''
holds true if $a = 0$, the other divisions
do not hold true if $a = 0$.


\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}


The function

\begin{alltt}
   void zbset(z_t r, z_t a, size_t bit, int mode);
\end{alltt}

\noindent
is used to manipulate single bits in {\tt a}. It will
copy {\tt a} into {\tt r} and then, in {\tt r}, either
set, clear, or flip, the bit with the index {\tt bit}
— the least significant bit has the index 0. The
action depend on the value of {\tt mode}:

\begin{itemize}
\item
$mode > 0$ ($+1$): set
\item
$mode = 0$ ($0$): clear
\item
$mode < 0$ ($-1$): flip
\end{itemize}


\newpage
\section{Bit test}
\label{sec:Bit test}

libzahl provides a function for testing whether a bit
in a big integer is set:

\begin{alltt}
   int zbtest(z_t a, size_t bit);
\end{alltt}

\noindent
it will return 1 if the bit with the index {\tt bit}
is set in {\tt a}, counting from the least significant
bit, starting at zero. 0 is returned otherwise. The
sign of {\tt a} is ignored.

We can think of this like so: consider

$$ \lvert a \rvert = \sum_{i = 0}^\infty k_i 2^i,~ k_i \in \{0, 1\}, $$

\noindent
{\tt zbtest(a, b)} returns $k_b$. Equivalently, we can think
that {\tt zbtest(a, b)} return whether $b \in B$ where $B$
is defined by

$$ \lvert a \rvert = \sum_{b \in B} 2^b,~ B \subset \textbf{Z}_+, $$

\noindent
or as right-shifting $a$ by $b$ bits and returning whether the
least significant bit is set.

{\tt zbtest} always returns 1 or 0, but for good code quality, you
should avoid testing against 1, rather you should test whether the
value is a truth-value or a falsehood-value. However, there is
nothing wrong with depending on the value being restricted to being
either 1 or 0 if you want to sum up returned values or otherwise
use them in new values.


\newpage
\section{Logic}
\label{sec:Logic}

TODO % zand zor zxor znot