one's compliment operator

[deepak]

Hi,

when I execute following program which find's one's compliment of 2,
I'm getting -3 where
I was expecting -2. Is there anything fundamentally wrong in my
understanding?


main()
{
int a = 2;

printf("%d\n", ~a);
}

O/P:
-3

Thanks,
Deepak

 

[deepak]

That output is correct, for a two's complement machine.


Take that bit pattern over to a one's complement machine, and it
will print -2 there. The same bit pattern on a two's complement
machine is -3.


The one's complement is one less than the two's complement.
On a two's complement machine (close to all machines are,
especially modern ones), the two's complement of N is
displayed as -N, and the one's complement of N is -N-1.

What machine is going to gain by changing it to 2's complement from
1's complement?

 

[osmium]

What machine is going to gain by changing it to 2's complement from
1's complement?

The first step is to identify what "it" is. Is "it" a computer? The design
of a computer? A number? All of the above? None of the above?

 

[Keith Thompson]

What machine is going to gain by changing it to 2's complement from
1's complement?

[...]

I'm having trouble understanding your question, but I'll try to answer
it anyway.

Representing unsigned integers is straightforward: each bit represents
a power of two. (There are complications, but we'll ignore them for
now). Representing signed integers is a bit more tricky.

There are three major ways to represent signed integers:

sign-and-magnitude simply reserves a bit to indicate the sign; this
bit is set to 0 for positive numbers, 1 for negative numbers. To
negate a number, just flip the sign bit.

In ones' complement, you negate a number by flipping *all* the bits.

In two's complement, you negate a number by flipping all the bits and
then adding 1.

It turns out that two's complement has considerable advantages over
the other representations. For one thing, it doesn't have two
different representations for zero; if you negate 0, you just get 0
again. The other representations both have distinct representations
for +0 and -0, which means you have to decide how to deal with them.
(Are +0 and -0 equal? If so, you can't compare two numbers just by
comparing all the bits.) Also, if you ignore overflow/wraparound,
many signed and unsigned operations are identical.

For this and other reasons, almost all machines these days use two's
complement for signed integers; the other representations aren't quite
dead, but they're rare.

 

[Richard Tobin]

It turns out that two's complement has considerable advantages over
the other representations. For one thing, it doesn't have two
different representations for zero; if you negate 0, you just get 0
again. The other representations both have distinct representations
for +0 and -0, which means you have to decide how to deal with them.
(Are +0 and -0 equal? If so, you can't compare two numbers just by
comparing all the bits.) Also, if you ignore overflow/wraparound,
many signed and unsigned operations are identical.

The most compelling reason is that it's just what you get if you apply
the usual algorithms for positive numbers even when the result might
be negative. You don't need to do anything special about negative
numbers at all.

Try it in base ten: subtract one from zero. 0 - 1 you can't do, so borrow
10. 10 - 1 is 9. Continue for however many digits you're using, and you'll
find 0 - 1 is 999...999. You're using ten's complement.

So to turn Keith's last sentence around, it's not that you find that
signed and unsigned operations are identical, it's that when you apply
operations without considering sign you find that you have invented a
consistent way of representing negative numbers.

-- Richard

 

[jameskuyper]

Hi,

when I execute following program which find's one's compliment of 2,
I'm getting -3 where
I was expecting -2. Is there anything fundamentally wrong in my
understanding?


main()
{
int a = 2;

printf("%d\n", ~a);
}

O/P:
-3

What's fundamentally wrong with your understanding is your expectation
that the '~' operator would give you the ones' complEment of it's
operand. That's not how it's defined. The correct definition is in
6.5.3.3p4:

"The result of the ~ operator is the bitwise complement of its
(promoted) operand (that is,
each bit in the result is set if and only if the corresponding bit in
the converted operand is
not set)."

That is the same as the ones' complement only when the promoted type
of the operand is represented on that machine using one's complement
notation. Since machines using one's complement notation are extremely
rare nowadays, you're far more likely to generate the twos' complement
when you apply the '~' operator.

 

[Keith Thompson]

What's fundamentally wrong with your understanding is your expectation
that the '~' operator would give you the ones' complEment of it's
operand. That's not how it's defined. The correct definition is in
6.5.3.3p4:

"The result of the ~ operator is the bitwise complement of its
(promoted) operand (that is,
each bit in the result is set if and only if the corresponding bit in
the converted operand is
not set)."

That is the same as the ones' complement only when the promoted type
of the operand is represented on that machine using one's complement
notation. Since machines using one's complement notation are extremely
rare nowadays, you're far more likely to generate the twos' complement
when you apply the '~' operator.

My understanding of what "the ones' complement" of a number means
differs from yours.

Here's how I'd say it:

The ~ operator does yield the ones' complement of its operand. This
won't be the *negated* value of the operand unless the system happens
to use a ones' complement representation for signed integers.

On a two's complement machine, the ~ operator still yields the ones'
complement of its operand. If it yielded the two's complement, as you
said above, it would be a negation operator; it isn't.

Though I probably wouldn't refer to ones' complement as an operation.
The operation in question is the bitwise complement. "Ones'
complement" usually refers to the particular representation that uses
the bitwise complement operator for arithmetic negation.

If you want the negated value of something just use the unary "-"
operator.

 

[jameskuyper]

My understanding of what "the ones' complement" of a number means
differs from yours.

To be honest, I have no such understanding of my own; I was making a
guess as to what the term meant to deepak. I'm familiar with the term
only as the name for a method of representing numbers, not as the name
for an operation that could be performed on them.

The one thing that I was clear about is that what he called the ones'
complement of a number differs from what the standard requires for the
result of applying the '~' operator on a value whose promoted type has
a twos' complement representation.

....

Though I probably wouldn't refer to ones' complement as an operation.
The operation in question is the bitwise complement. "Ones'
complement" usually refers to the particular representation that uses
the bitwise complement operator for arithmetic negation.

So we're pretty much in agreement.