From d1771305d6b1a548544119ce953c9bb758c6b77a Mon Sep 17 00:00:00 2001
From: Mattias Andrée <maandree@kth.se>
Date: Thu, 2 Jun 2016 12:42:12 +0200
Subject: On bit test
MIME-Version: 1.0
Content-Type: text/plain; charset=UTF-8
Content-Transfer-Encoding: 8bit

Signed-off-by: Mattias Andrée <maandree@kth.se>
---
 doc/bit-operations.tex | 37 +++++++++++++++++++++++++++++++++++--
 1 file changed, 35 insertions(+), 2 deletions(-)

(limited to 'doc/bit-operations.tex')

diff --git a/doc/bit-operations.tex b/doc/bit-operations.tex
index c3fbe4a..8bf3d36 100644
--- a/doc/bit-operations.tex
+++ b/doc/bit-operations.tex
@@ -209,7 +209,7 @@ divide-and-conquer algorithms.
 The function
 
 \begin{alltt}
-   zbset(z_t r, z_t a, size_t bit, int mode);
+   void zbset(z_t r, z_t a, size_t bit, int mode);
 \end{alltt}
 
 \noindent
@@ -233,7 +233,40 @@ $mode < 0$ ($-1$): flip
 \section{Bit test}
 \label{sec:Bit test}
 
-TODO % zbtest
+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
-- 
cgit v1.2.3-70-g09d2

