chapterBitManipulation.tex

\chapter{Bit Manipulation}
\section{Concepts}
\subsection{Basics}
\begin{enumerate}
\item Bit value: bit0, bit1. 
\item BitSet/Bits
\item Bit position (bit interchangeably)
\item 32-bit signed range: $[-2^{31}, 2^{31}-1]$. $0$ is like positive number without complement. 
\end{enumerate}
\begin{python}
MAX = 0x7FFFFFFF
MIN = 0x80000000
MSK = 0xFFFFFFFF
\end{python}
\subsection{Operations}
\runinhead{Basics} 
\begin{enumerate}
\item Masking to 1: to mask a single bit position, $bit\OR 1$
\item Masking to 0: to mask a single bit position, $bit\AND 0$
\item Querying a bit position value: to query a single bit position, $bit\AND 0010$
\item Toggling bit values: to toggle a single bit position, $bit\XOR 1$
\end{enumerate}
This can be extended to do masking operations on multiple bits. 

\runinhead{2's complement}
$$
-i = \NOT i+1
$$

Negative numbers: \pyinline{0b10000000} to \pyinline{0b11111111} (-128 to -1 in decimal). This process essentially "wraps around" the positive binary sequence to start from the most negative number. 

\begin{python}
{
  # 4 overflow
  3: 0b011,
  2: 0b010,
  1: 0b001,
  0: 0b000,
  #########
 -1: 0b111, 
 -2: 0b110,
 -3: 0b101,
 -4: 0b100,
}
\end{python}
Since 0 takes a position in the binary representation:
\begin{itemize}
\item $\NOT0$ is $-1$
\item $\NOT1$ is $-2$
\item $\NOT3$ is $-4$.
\end{itemize}


\runinhead{Check 2's power}
2's power is in the form of \pyinline{0b01000}.
$$x\AND(x-1)$$

\runinhead{Rightmost bit set. LSB} To get the rightmost bit, with the help of 2's complement as followed:
\begin{align*}
x &= 0bijk1000 \\
\NOT x &= 0bIJK0111 \\
-x &= 0bIJK1000
\end{align*}
where $IJK$ represent bits that are the negation of $ijk$.

$$LSB = x \AND -x$$

This above is left extended with 0's. To left extended with 1's. 

$$
LSB_{1extended} = \NOT (lsb - 1)
$$

\runinhead{Rightmost bit set. MSB.} Find the most significant bit. 
\begin{python}
msb = 0
while num >> msb:
  msb += 1
return msb  # index
\end{python}
If zero-indexed, the MSB is \pyinline{msb - 1}. 

Alternatively,
\begin{python}
msb = 1
while msb <= x:
  msb <<= 1
return msb >> 1
\end{python}

\runinhead{Negation and index} We can use tilde notation for the index accessing a string or an array
\begin{lstlisting}
i  ~i
#####
0  -1
1  -2
2  -3
3  -4 
4  -5 
5  -6
\end{lstlisting}
$$
\NOT i = -i-1
$$
To determine whether a string is palindrome:
\begin{python}
def is_palindrome(s):
  return all(s[i] == s[~i] for i in range(len(s)/2)) 
\end{python}

\runinhead{Divide by 2.} To divide a number by 2, it should be \pyinline{x >> 1} rather than \pyinline{x >> 2}. 

\subsection{Python}
Python int is larger than 32 bit. 
If 32bit signed int, in python, we may need to mask the int:
\begin{enumerate}
\item Mask to 32bit: \pyinline{x & MSK}, 
\item Left extended with 1's: \pyinline{\~(x ^ MSK)}
\end{enumerate}

, where \pyinline{MSK = 0xFFFFFFFF}, 8 F's for 32 bits. 

\section{Radix}
\runinhead{Convert to hexadecimal, but with 2's complement.} Easy to convert positive number of hex, but need to pay more attention to negative number when thinking in the decimal representation. 

Everything easy to convert the number even under 2's complement if thinking in the binary representation. 

Core proccess:
\begin{enumerate}
\item current digit we need: \pyinline{num & 0xF}
\item next significant number: \pyinline{num >>= 4}
\end{enumerate}
\section{Circuit}
It is under 32-bit assumption, for Python, we need additional masking in the previous section. 
\subsection{Full-adder}
\rih{Plus.} Handle carry: only 1 + 1 needs carry, thus \pyinline{a & b} determines carry. 
\begin{python}
def plus(a, b):
  carry = (a & b) << 1
  out = a ^ b 
  if carry != 0:
    return plus(out, carry)
  else:
    return out
\end{python}
\rih{Half Adder}. One bit \pyinline{a, b}:
\begin{python}
def half_add(a, b): 
  carry = a & b
  out   = a ^ b 
  return out, carry 
\end{python}
\rih{Full Adder}. One bit \pyinline{a, b, cin}. \pyinline{out = a ^ b ^ cin}. and \pyinline{cout = a & b | cin & a ^ b}
\begin{python}
def full_add(a, b, cin): 
  out, c1 = half_add(a, b)
  out, c2 = half_add(out, cin)
  cout    = c1 | c2  # ^ possible
  return out, cout 
\end{python}

\subsection{Full-substractor}
\rih{Substract.} Handle borrow: only 0 - 1 needs borrow, thus \pyinline{\~a & b} determines borrow. 
\begin{python}
def sub(a, b):
  borrow = (~a & b) << 1
  out = a ^ b 
  if borrow != 0:
    return sub(out, borrow)
  else:
    return out
\end{python}
\rih{Half Substractor.} One bit \pyinline{a, b}:
\begin{python}
def half_sub(a, b):
  borrow = (~a & b)
  out = a ^ b
  return out, borrow
\end{python}
Notice negation can be done in xor. 
\begin{python}
~a == 1 ^ a 
\end{python}
\rih{Full Substractor}. One bit \pyinline{a, b, bin}. \pyinline{out = a ^ b ^ bin}. 
\begin{python}
def full_sub(a, b, bin):
  out, b1 = half_sub(a, b)
  out, b2 = half_sub(out, bin)
  bout = b1 | b2 
  return out, bout 
\end{python}

\subsection{Multipler}


\section{Single Number}
\subsection{Three-time appearance} 
Given an array of integers, every element appears three times except for one. Find that single one.

\rih{Using list.} Consider 4-bit numbers:
\begin{eqnarray*}
&& 0000 \\
&& 0001 \\
&& 0010 \\
&& ... \\
&& 1111
\end{eqnarray*}

Add (not $\&$) the bit values \textbf{vertically}, then result would be $abcd$ where $a, b, c, d$ can be any number, not just binary. $a, b, c, d$ can be divided by 3 if the all element appears three times. Until here, you can use a list to hold $a, b, c, d$. By mod 3, the single one that does not appear 3 times is found. 

To generalize to 32-bit \pythoninline{int}, use a list of length 32.

\rih{Using bits.}
To further optimize the space, use bits (bit set) instead of list. 
\begin{itemize}
\item Since all except one appears 3 times, we are only interested in $0, 1, 2$ (mod 3) count of bit1 appearances in a bit position.
\item We create 3 bit sets to represent $0, 1, 2$ appearances of all positions of bits.
\item For a bit, there is one and only one bit set containing bit1 in that bit position.
\item Transition among the 3 bit sets for every number:
$$
bitSet^{(i)} = (bitSet^{(i-1)}\AND num)\OR(bitSet^{(i)}\AND \NOT num)
$$
\end{itemize}

For $i$ appearances, the first part is the bit set \textbf{transited from} $(i-1)$ appearances, and the second part is the bit set \textbf{transited out} from itself.

Consider each single bit separately. For the $j$-th bit in $num$, if $num_j=1$, the first part indicates $bitSet^{(i-1)}$ will transit in (since transition); the 2nd part is always 0 (since transition out or initially 0). If $num_j=0$, the 1st part is always 0 (since no transition); the 2nd part indicates $bitSet^{(i)}$ will remain the same (since no transition). 



\subsection{Two Numbers} 
Given an array of numbers nums, in which exactly \textbf{two} elements appear only once and all the other elements appear exactly twice. Find the two elements that appear only once.

\begin{itemize}
\item Easily get: $x = a \XOR b$.
\item $a \neq b$; thus there are at least one 1-bit in $x$ is different.  
\item Take an arbitrary 1 bit set in $x$, and such bit set can classify the elements in the array into two separate groups.
\item Then do $a_i \XOR a_j$ in two groups respectively to find out $a$ and $b$ from each group.
\end{itemize}

\section{Bitwise operators}
\runinhead{Comparison.} Write a method which finds the maximum of two numbers $a, b$. You should not use if- else or any other comparison operator
\\
Clues:
\begin{enumerate}
\item check the sign bit $s$ of $a-b$.
\item return $a-s*(a-b)$
\end{enumerate}
Codes:
\begin{java}
int getMax(int a, int b) { 
    int c = a - b;
    int k = (c >> 31) & 0x1; 
    int max = a - k * c; 
    return max;
}

\end{java}
If consider overflow, it raises another level of difficulty. 

\runinhead{ Maximum XOR} Maximum XOR of Two Numbers in an Array. To achieve $O(N)$, check bit by bit rather than number by number.