Diff for "OnesComplement"

Immutable Page
Comments
Info
Attachments

Differences between revisions 3 and 20 (spanning 17 versions)

One's Complement

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

OnseComplement.tex

OnesComplement (last edited 2020-01-26 22:58:24 by 68)

Immutable Page
Comments
Info
Attachments

-  ⇤ ← Revision 3 as of 2010-09-05 17:00:21 → 
  Size: 2447
  Editor: 71-87-243-6
  Comment:
+   ← Revision 20 as of 2020-01-26 22:58:24 → ⇥
  Size: 200
  Editor: 68
  Comment:
-Deletions are marked like this.
+Additions are marked like this.
 Line 5:
-{{{#!latex
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$.

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$.

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

 $I = \sum_{i = 0}^{n - 1} b_{i} \cdot 2^{i} - (2^{n} - 1) .$ 

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:
 $I = \sum_{i = 0}^{n - 1} b_{i} \cdot 2^{i} - b_{n} (2^{n} - 1) .$ 

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

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} B i n a r y & D e c i m a l \\ 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
 $Unknown environment 'center'$ 

}}}
+ * [[attachment:OnseComplement.tex]]
 
<<EmbedObject(OnseComplement.pdf,width=100%,height=600px)>>