|
Size: 2445
Comment:
|
Size: 2740
Comment:
|
| Deletions are marked like this. | Additions are marked like this. |
| Line 6: | Line 6: |
| The leftmost bit indicates the sign of an integer in $1$s complement representation where $1$ means that the number is negative. The representation for positive integers is the same as unsigned with the leftmost bit represented with a $0$. | 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$. |
| Line 8: | Line 8: |
| Negative integers are formed by reversing all bits to form the bitwise complement of a positive integer. If $I$ is the $n+1$ 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$. | 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} \ldots b_1 $ then $-I$ in one's complement is given by $\overline{b_n } \ldots \overline{b_1}$ where $\overline{b_i}=1-b_i$ for all $i$.\bigskip \noindent\textbf{Let's see what that looks like in Math speak}\bigskip |
| Line 12: | Line 14: |
| -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 | -I = \sum_{i=0}^{n-1}(1-b_i)\cdot2^i = \sum_{i=0}^{n-1}2^i - \sum_{i=0}^{n-1} b_i \cdot 2^i. |
| Line 14: | Line 16: |
| since $b_n=1$. Thus, | Thus, |
| Line 25: | Line 27: |
| The range of values for an $(n+1)$ bit one's complement integer is $-(2^n-1)$ to $2^n-1$ . | Recalling that the left most bit only represents the sign, the range of values for an $n-$bit one's complement integer is $-(2^{n-1}-1)$ to $2^{n-1}-1$.\bigskip \noindent\textbf{Examples:}\bigskip |
| Line 28: | Line 32: |
| \begin{equation} | \[ |
| Line 36: | Line 40: |
| \end{equation} The range of $8$-bit one's complement integers is $-127$ to $+127$. |
\] The range of $8-$bit one's complement integers is $-127$ to $+127$. |
| Line 42: | Line 47: |
| \begin{center} | |
| Line 50: | Line 55: |
| \end{center} |
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} \ldots b_1 $ then $-I$ in one's complement is given by $\overline{b_n } \ldots \overline{b_1}$ 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}(1-b_i)\cdot2^i = \sum_{i=0}^{n-1}2^i - \sum_{i=0}^{n-1} b_i \cdot 2^i.
\end{equation}
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}
Recalling that the left most bit only represents the sign, the range of values for an $n-$bit one's complement integer is $-(2^{n-1}-1)$ to $2^{n-1}-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}