1s complement

[jeevsmyd]

what is the ones complement representation of 0 ?

[kings_mitra]

Good question...and tricky answer !!!
Actually this is where the problem with the mechanism of one's complement appears in programming. And this is where the approach changes to two's complement.
If u actually take one's complement of zero it comes out to be (-ve)zero. Confused ???
One's complement of zero (00000000) i.e +0 becomes (11111111) i.e -0.
This becomes really problematic as the hardware required for adding and subtracting becomes much more complicated. Also it gets difficult for testing for zero, as every time we want to test for zero, we have to see if it's +0 or −0.

So, for avoiding this, and to also make integer addition simpler, the two's complement representation comes into picture. In a two's complement, there is one and only one zero (00000000), and (11111111) denotes −1, so there is no problem testing for zero.

[jeevsmyd]

so, 1s complement is actually the negetive of that number? then what about 2s complement? I am taught how to perform binary sutraction using 1s as well as 2s complement methods, but never really understood what they really are!! so here is one more example..
101 is the binary equivalent of decimal 5,right? and 1s complement of that number is 010,right? but is 010 = -5 ? or cant 1st complement operation be performed without adding the sign bit? the number is "101" so what exactly is 010 taking 1st digit NOT as a sign bit?

[kings_mitra]

In one’s complement, the processor takes the bitwise complement of each “0” and “1” to produce the original number’s opposite/negative.
So, the number 5, represented as a byte is 00000101, -5, using one’s complement would be 11111010.
So, the range of signed numbers obtained by using ones' complement can be represented by −(2^(N−1)−1) to (2^(N−1)−1) and +/− 0. Thus a conventional byte is −127 to +127 with zero being either 00000000 (+0) or 11111111 (−0).
Here, if we want to add two numbers, we will have to do the conventional binary addition, and then it is necessary to add any resulting carry back into the obtained sum.

To overcome these problems for multiple representations of 0 and the end-around carry, the two's complement approach was taken. In two's complement, negative numbers are represented by the bit pattern which is one greater than the ones' complement of the positive value.
So, 1's complement of 5 = (11111010)
After adding 1 to it the 2's complement comes out to be : (11111011)
So, the number -5 in 2's complement form is (11111011)
Again, 1's complement of -5 (11111011) = (00000100)
Adding 1 gives (00000101) , i.e 5 again.
Note that the two's complement of zero is zero: inverting gives all ones, and adding one changes the ones back to zeros (the overflow is ignored).

[jeevsmyd]

ok , thanks.. what about the sign bit?

[jeevsmyd]

I have be taught that, the sign bit should added before performing operations.. so positive 5 is 0,101,right? so, when you are asked to find the 1s complement of 5 , shouldnt it be 1,010? I am really confused about this sign bit.. can you please help me understand the basics?

[jeevsmyd]

is this sign bit part of the digit? when do we use it?
when one is asked to find the 1s or 2s complement of +ve 5 , should the sign bit be considered?

[kings_mitra]

A two's-complement number system encodes positive and negative numbers in a binary number representation. The bits are weighted according to the position of the bit within the array itself.
So, two's complement numbers are a way to encode negative numbers into ordinary binary, such that addition still works. Adding -1 + 1 should equal 0, but ordinary addition gives the result of 2 or -2. But 2's complement operation takes special notice of the sign bit and performs a subtraction instead.
Two's complement results in the correct sum without this extra step.

Example:
In case of 1's complement :
Adding -1 (11111110) and 2 (00000010)

11111110 + 00000010 = 00000000 (carry 1) [incorrect answer]
Adding the carry 1 we get 00000001 = +1 [correct answer]

In case of 2's complement :

Adding -1 (11111111) and 2 (00000010)

11111111 + 00000010 = 00000001 [correct answer]
So, the carry is automatically taken care of. ;)

(Note: Mark the thread as solved if u r clear)

[kings_mitra]

Just checked ur earlier posts...
See a number's sign (i.e, positive or negative) can be represented by allocating one sign bit to represent the sign:
Set that bit (often the most significant bit) to 0 for a positive number
Set to 1 for a negative number.
The remaining bits in the number indicate the magnitude (or absolute value).

Hence in a byte with only 7 bits (apart from the sign bit), the magnitude can range from 0000000 (0) to 1111111 (127). Thus you can represent numbers from −127 to +127 once you add the sign bit (the eighth bit).

This approach is directly comparable to the common way of showing a sign (placing a "+" or "−" next to the number's magnitude).
Clear hah...??

[jeevsmyd]

one more doubt , 1s complement of zero can either be 1,1111 or 0,1111, right? when you take the complement of a number, you gotta take the complement of the sign bit also, right?

[kings_mitra]

Definitely, that's how it gets converted to from positive to negative and vice-versa.
But consider at least 1 byte i.e 8 bits for the examples.

One simple quote to clear ur doubt:
The largest number that can be represented in 8-bit 1's complement is :
01111111 = 127
The smallest is
10000000 = -127.
Thats what I hv already specified as magnitude, right !!!

[tesuji]

what is the ones complement representation of 0 ?

Short answer (0D encoded in 1 byte): 00000000 and 11111111. There are really two one's complement representations of decimal 0 (=0D).

Longer answer, well, not sure whether this answer is too long:

There are four commonly used methods for encoding [B]positive and negative[/B] binary number:

[I]One's complement,

Two's complement,

Sign-magnitude method,

Bias method.[/I]

All methods use the high order (hob) oder most significant (msb) bit to encode the sign, except for the bias method. Also in programming language COBOL the sign is encoded on the low-order-bit side (4 bits are used in COBOL, the low order half byte).

To show the various methods let me state this Example:
 
[I]What is the negative encoding of decimal 13D when encoded in [B]one byte/8 bits[/B]?[/I] 

We will also see that the length, the number of bits, used to encode negative numbers, is important too. 
 
Positive value of 13D is binary 1101B or hexadecimal DH what is to extend to 00001101B or 0DH to fill 8 bits (B=Binary, D=Decimal, H=Hexadecimal).

1. Negative 13D using one's complement
--------------------------------------
Rule: 0 becomes 1, 1 becomes 0
Result:  11110010B or hex F2H

2. Negative 13D using two's complement
--------------------------------------
Rule: calculate one's complement, then add 1.
Result: 11110010B + 1 = 11110011B or hex F2H+1 = F3H

In both cases the leading 1 (msb) indicates negative number.

[B]Important:[/B] If we hadn't put the 0000 on the left of 1101B, the negative results would have been wrong. For example: one's complement of 1101B would be 0010B. But this has a leading 0 what indicates a positive number, therefore wrong.

Today, all processors and almost every programming language such as assembly, C, C++, Java etc use two's complement to encode negative whole numbers = integers. In former days the one's complement has been most widely used, e.g. on IBM computers.   

3. The sign-magnitude method
----------------------------
Rule: If the number is positive, put a 0 on the msb side of the positive (=absolute) value. If the number is negative, put an 1 on msb side.
Example: On the msb side of the positive value 0001101B we have to put 1 to get -13D
Result: 10001101B or hex 8DH.

This method is used to encode the sign of the mantissa of float and double values in concordance to IEEE 754.

4. The bias method
------------------
Rule: Always add a positive constant (=bias) to every number so that there are only positive numbers.

Here a positive constant is added to a whole number for transforming the negative part of the co-domain into the positive domain. For a co-domain of [-128...+127] this positive constant is just 128 to transform the co-domain into [0...+255]. The constant 128 is called the bias. 

Example (bias 128): Negative 13D is 128-13 = 115D = 01110011B (8 bits, thus leading 0 added) or hex 73H

The bias method is used to encode the exponent of float and double numbers. The IEEE 754 standard defines various biases for float and double numbers. For example the 64Bit c++ double datatype has a bias of 1024 (also 1023 allowed!)

Final question: What are the 8-bit-encodings for some special numbers using all four methods (bias 128)?

Number                   -128     -127     -1       -0       0       +1      + 127  
------------------------------------------------------------------------------------ 
One's complement         ***   10000000 11111110 [B]11111111 00000000[/B] 00000001 01111111 

Two's complement      10000000 10000001 11111111 00000000 00000000 00000001 01111111

Sign-magnitude method   ***    11111111 10000001 10000000 00000000 00000001 01111111

The bias method       00000000 00000001 01111111 10000000 10000000 10000001 11111111
(*** impossible) Please note: The two's encoding of -128D is called the "weired" number :( (why?)          

Sign-encoding methods and IEEE754 are explainted on wikipedia in detail.

-- tesu

[tesuji]

"weired" should be weird, weird number?

[tesuji]

I have to correct a mistake: I wrote that the one's complement would be still commonly used. This is not correct. Today, this complement is never been used. The prime reason is, that it allows two differently encoded zeros (0000, 1111).

To implement the zero test (if (a==0)...) both encodings must be implemented in a processor's hardware. Nowadays, negative whole numbers/integers are only encoded with two's complement because there is a bijective zero. There is a further advantage: If the result of a directly calculated subtraction is negative, this result is in two's complement, e.g. 0011B - 0111B = 1100B, where 1100B is just the two's complement of -4D.

Drawback of two's complement: One cannot calculate the absolute value of the largest negative number. Its result remains negative.

-- tesu

[kings_mitra]

One quick trick to find out the two's complement of a binary number without performing the one's complement.
Start from the least significant bit (LSB), and copy all the zeros (from LSB towards the most significant bit MSB) until the first 1 is reached; then copy that 1, and flip all the remaining bits.
For example:
Two's complement of 01101000 = 10011000, where the underlined part is what is copied and rest of the bits are flipped.

Cheers,:)

[TrustyTony]

And one not about long ago adding error checking to binary GCD algorithm in ARM assembler: one interesting feature of 2's complement is that there is that smallest negative number, whose ABSolute value is not in the INTegers. So it is actually possible to have overflow error of taking ABS or changing sign of number in one case of typically 2**32=4294967296 cases.

[arkoenig]

one more doubt , 1s complement of zero can either be 1,1111 or 0,1111, right? when you take the complement of a number, you gotta take the complement of the sign bit also, right?

No. 1s complement of zero is either 1,1111 or 0,0000.

[TrustyTony]

Yes, but I said two's complement, which was described as only game in town. One's complements problem was two zeroes. I wanted to say that problem is moved to having one number whose absolute value is outside the class of numbers. That number is however very rare.