One's Complement

-- adapted from http://www.cs.uaf.edu/~cs301/notes/Chapter4/node4.html

Given an $n-$bit binary string, $I$, the leftmost bit indicates the sign of an integer in $1$s complement representation. In this left most position a $1$ indicates a negative value while a $0$ indicates a positive value. The representation for positive integers corresponds to unsigned representation where the leftmost bit must contain a $0$.

Negative integers are formed by reversing all bits to form the bitwise complement of the corresponding positive integer. If we represent $I$ by the $n-$bit binary sequence, $b_{n} n_{n-1} \ldots b_1 b_0$ then $-I$ in one's complement is given by $\overline{b_n n_{n-1}} \ldots \overline{b_1 b_0}$ where $\overline{b_i}=1-b_i$ for all $i$.\bigskip

\noindent\textbf{Let's see what that looks like in Math speak}\bigskip

Let $I$ be a negative one's complement integer. The value of $I$ is obtained by forming its one's complement:
\begin{equation}
     -I = \sum_{i=0}^{n}(1-b_i)\cdot2^i = \sum_{i=0}^{n-1}2^i - \sum_{i=0}^{n-1} b_i \cdot 2^i
\end{equation}
since $b_n=1$. Thus,

\begin{equation}
    I = \sum_{i=0}^{n-1}b_i \cdot 2^i - (2^n - 1).
\end{equation}

Negative one's complement integers are formed by subtracting a bias of $2^n - 1$ from the positive integers. Taking into account the sign bit $bn$, the value for a positive or negative (n+1) bit one's complement integer is:
\begin{equation}
    I = \sum_{i=0}^{n-1}b_i \cdot 2^i - b_n (2^n - 1).
\end{equation}

The range of values for an $(n+1)$ bit one's complement integer is $-(2^n-1)$ to $2^n-1$.\bigskip

\noindent\textbf{Examples:}\bigskip

Since the complement of $0$ is $2^{n+1}-1$, there are different representations for $+0$ and $-0$ in one's complement. Examples of $8$-bit one's complement numbers:
\[
 \begin{array}{cr}
    Binary & Decimal \\
    00000000 & 0 \\
    11111111 & -0 \\
    00000011 & 3 \\
    11111100 & -3 \\
  \end{array}
\]
The range of $8$-bit one's complement integers is $-127$ to $+127$.

Addition of signed numbers in one's complement is performed using binary addition with end-around carry. If there is a carry out of the most significant bit of the sum, this bit must be added to the least significant bit of the sum.

To add decimal 17 to decimal -8 in 8-bit one's complement:\bigskip
\begin{center}
\begin{tabular}{rrrrrr}
&  & $0001$ & $0001$ &  & $(17)$ \\
$+$ &  & $1111$ & $0111$ &  & $(-8)$ \\ \cline{1-4}\cline{6-6}
& $1$ & $0000$ & $1000$ &  &  \\
&  & \multicolumn{1}{l}{$\hookrightarrow $} & $+1$ &  &  \\ \cline{3-4}
&  & $0000$ & $1001$ & $=$ & $(9)$%
\end{tabular}
\end{center}