Using ~ (Unary bitwise complement) for Zero

Pranav Raulkar
Ranch Hand
Posts: 73
I wrote a program to find 0's complement and found out that its -1.

So I get it that ~ is giving me 2's complement. But what I dont understand how is 0's 2's complement is -1.

00000000 is 0
11111111 is 1's complement
1 00000000 is 2's complement of above where carry 1 is ignored.

So why the result is -1 (11111111)

If 1's complement was used then it would give me -0 which is wrong.

Campbell Ritchie
Sheriff
Posts: 50671
83
The ~ operator does not give you a two’s complement. It simply inverts every bit. It is similar to one’s complement. So 0000_0000 turns into 1111_1111, which is exactly what you have shown.

Pranav Raulkar
Ranch Hand
Posts: 73
And 11111111 represents -1 in binary?

Stephan van Hulst
Bartender
Posts: 6479
83
In Java's representation (which uses two's complement), yes.

Pranav Raulkar
Ranch Hand
Posts: 73
So in java 2's complement for 0 is 11111111 which is -1. Agreed.
But if you calculate 2's complement it comes out to be 00000000. Correct me if I'm wrong from my first post.

fred rosenberger
lowercase baba
Bartender
Posts: 12228
36
Pranav Raulkar wrote:So in java 2's complement for 0 is 11111111 which is -1. Agreed.

WRONG.

~0 is NOT two's compliment, it simply flips every '0' bit to '1', and every '1' bit to '0'.

In Java, 2's compliment for 0 is 0. In fact, in ANY language, 2's compliment of 0 is 0, as 2's compliment is an algorithm, not a language specific feature.

Campbell Ritchie
Sheriff
Posts: 50671
83
Pranav Raulkar wrote:So in java 2's complement for 0 is 11111111 which is -1. Agreed.
No. Not at all. I think you have misunderstood two’s complement arithmetic. The two’s complement representation of 0 is 0000_0000 (in 8 bits). The two’s complement of 0 is not 1111_1111. Never.

This is how two’s complement numbers are worked out:
• You work out the range of numbers available: for 8 bits that is 256
• You allow exactly half that range for negative numbers: -1 to -128 inclusive.
• You allow exactly the other half of the range for non-negative numbers: 0 to 127 inclusive.
• For non-negative numbers, use exactly the same format as for unsigned numbers, 0000_0000 to 0111_1111 inclusive.
• For negative numbers, subtract the absolute value from the size of the range.
• You can work out the two’s complement value of a negative number by subtracting its absolute value from the size of the whole range.
• For example: the two’s complement representation of -97 is the same as the unsigned representation of 256 - 97, or 1_0000_0000 - 0110_0001

• That is how complementary numbers are really defined.
If you try that calculation, you get this for -97:
1_0000_0000
0110_0001-
1001_1111

There are at least two other ways you can think of a two’s complement number (still in 8 bits):
One way: The leftmost bit (no 7) represents -2^7 (-128)or 0, the next bit represents (+)64 or 0, then (+)32 or 0, etc until the rightmost bit (the 0-th bit) represents (+)1 or 0. So 1001_1111 means -128 + 0 + 0 + 16 + 8 + 4 + 2 + 1 = -97.

The other way is to remember that 256 - 97 = 256 - 1 - 97 + 1. The -1 and +1 cancel out, but look good in binary.
256 - 1 looks like this:
1_0000_0000
0000_0001-
1111_1111
. . . 255 in unsigned numbers.

Now you can subtract 97 from 255
1111_1111
0110_0001-
1001_1110

Now you add 1 again
1001_1110
0000_0001+
1001_1111
. . . and lo and behold, we have -97

Did you notice that subtracting from 111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111 is the same as swapping all the bits? So, you can get something identical to two’s complement by swapping all the bits and adding 1. If you try complementing 0 to -1 and adding 1, you get 0. Try it

But if you calculate 2's complement it comes out to be 00000000. Correct me if I'm wrong from my first post.
No, you are not calculating a two’s complement at all. What you are doing is taking the bit pattern, eg 0110_0001 for 97 and 0000_0000 for 0 (in 8 bits) and getting the complement of that bit pattern. That is equal to -(i + 1). As you saw above, 97 turns into -98 and 0 turns into -1.

Pranav Raulkar
Ranch Hand
Posts: 73
OK I got this from wiki

In two's-complement, there is only one zero (00000000). Negating a number (whether negative or positive) is done by inverting all the bits and then adding 1 to that result.

Can you put up a claculation just like you did for -97 for complement of zero?

fred rosenberger
lowercase baba
Bartender
Posts: 12228
36
Note: There is a difference between the "complement" and the "two's compliment". I assume you want the latter.

0 is

0000 0000 0000 0000 (i'm only going to use 16 bits, but it works the same for 32, or 64 or however many bits you want)

invert all the bits, you get

1111 1111 1111 1111

add 1:

but that left-most 1 doesn't fit. We run out of bits, so it falls off the end, leaving us with

0000 0000 0000 0000

Campbell Ritchie
Sheriff
Posts: 50671
83
Pranav Raulkar wrote: . . . Can you put up a claculation just like you did for -97 for complement of zero?
Fred has already done that, only for 16 bits. It is exactly the same, but occupies more space on the screen.
The wikipedia article about two’s complement is slightly imprecise. Two’s complement is made by subtracting from 2^i where i is the number of available bits. Inverting each bit and adding one is not how it is defined, but always gives the same result, provided the numbers are within the range -2^(i - 1)...2^(i - 1) - 1.

Pranav Raulkar
Ranch Hand
Posts: 73
Agreed! Complement and 2's complement are different.
If we do complement of 0 its 11111111 which is 255.
since ~ is complement operator ~0 should give me 255. Why -1? If its giving me -1 it means ~ is 2's complement.
But we all know 2's complement for 0 is 00000000 (Carry over 1 is discarded)

I'm so LOST!

fred rosenberger
lowercase baba
Bartender
Posts: 12228
36
Again, you're making a few faulty assumptions here.

the complement of 0 will slightly depend on whether you have an int or a long. an int is 32 bits, and a long is 64 bits. so, 0 will be either

0000 0000 0000 0000 0000 0000 0000 0000

or

0000 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000

the complement will be (for the int)

1111 1111 1111 1111 1111 1111 1111 1111

To determine the value, you have to do the following:

look at the left most bit. If it is a zero (it our case it isn't), you simply add up the powers of 2 that correspond to the 1's, and the value is positive.

if the left-most bit IS a 1, your result will be negative. next, take the 2's complement of the number. So, we flip all the bits, and add 1. so it becomes

0000 0000 0000 0000 0000 0000 0000 0000
+ 1
=============================
0000 0000 0000 0000 0000 0000 0000 0001

So "1111 1111 1111 1111 1111 1111 1111 1111" represents "-1".

Campbell Ritchie
Sheriff
Posts: 50671
83
1111_1111 is only 255 in unsigned binary numbers. It is meaningless to say something like “1010_1010 means xyz”, without saying what format you are using, and what memory size. There are at least four formats for binary integers, possibly five if you include one’s complement. In two’s complement in eight bits, 1111_1111 means -1decimal.

Campbell Ritchie
Sheriff
Posts: 50671
83
I have already told you, and I think Fred has too, that the ~ operator does not produce the two’s complement. It returns the bit pattern inverted, which is more akin to one’s complement. So you get the one’s complement of 0 which in two’s complement returns -1decimal. Remember you had to add 1 to ~97 to get -97.

Campbell Ritchie
Sheriff
Posts: 50671
83
0000_0000   Flip the bits. What the ~ operator does, giving the result on the next line.
1111_1111   That returns -1decimal, but to get that into two’s complement, add 1, and the 8th bit vanishes into cyber-limbo never to be seen again.

1_0000_0000   Now we get back to 0. But that isn’t what the ~ operator does. It only does what you saw one line up.