[RESOLVED] bitwise operator ~ NOT

3_grosz

What cause that output is -3? I'm trying to understand binary NOT (~), but I'm stuck on this simple code.

<?php
$bitek = 2;
echo ~$bitek; //~2= -3 
?>

Thanks in advance

laserlight

I suggest that you read up on two's complement representation as it is most likely the representation that is in use here.

bradgrafelman

Eh, it's actually just a one's complement

Decimal 2 is '00000010' as a signed binary number.
Flip each bit to get '11111101' which is -3 as a signed binary number.

If it were a two's complement, you'd have to add 1 after flipping the bits.

laserlight

bradgrafelman wrote:
Eh, it's actually just a one's complement

Decimal 2 is '00000010' as a signed binary number.
Flip each bit to get '11111101' which is -3 as a signed binary number.

If it were a two's complement, you'd have to add 1 after flipping the bits.

No, it is two's complement. You are thinking of a way to obtain the binary representation of a negative number given the binary representation of its absolute value. For an 8 bit signed integer in one's complement, 11111101 represents -2, not -3.

bradgrafelman

laserlight wrote:
For an 8 bit signed integer in one's complement, 11111101 represents -2, not -3.

Check out this page. The table on the right shows -2 as "1 1 1 1 1 1 0", which is obtained by taking 2, flipping every bit, and adding 1 (a.k.a. 2's complement).

laserlight

bradgrafelman wrote:
Check out this page. The table on the right shows -2 as "1 1 1 1 1 1 0", which is obtained by taking 2, flipping every bit, and adding 1 (a.k.a. 2's complement).

Yes, in two's complement. You seem confused as to whether you are talking about one's complement or two's complement 😉

bradgrafelman

laserlight;10938145 wrote:
Yes, in two's complement. You seem confused as to whether you are talking about one's complement or two's complement 😉

Not at all; two's complement is flipping all the bits of a number and then adding 1.

laserlight

Look at your post #3:

bradgrafelman wrote:
Eh, it's actually just a one's complement

Decimal 2 is '00000010' as a signed binary number.
Flip each bit to get '11111101' which is -3 as a signed binary number.

If 11111101 represents -3, then you are using two's complement, not one's complement. Therefore, you must be wrong to say that one's complement is used.

But when I point this out to you, you turn around and talk about two's complement. Not very fair, is it? 🙂

EDIT:
To return to the pedantic accuracy of my post #2: actually, that 11111101 represents -3 does not imply that two's complement is used, but it is highly probable since standard C only allows for signed integers to be represented by using two's complement, one's complement, or sign and magnitude.

So, back to 3.grosz's question. Notice that 3.grosz observed that ~2 == -3. This corresponds very nicely to two's complement. Indeed, if we apply the method that you described, then from the 8 bit signed integer representation of 3, i.e., 00000011, we flip the bits to get 11111100, then we add 1 to get 11111101, which is the two's complement representation of -3. Now, from the 8 bit signed integer representation of 2, i.e., 00000010, we obtain ~2 by flipping the bits and get 11111101. So, we end up with the same representation, thus confirming that it is possible that two's complement is used, hence affirming that my suggestion is valid.

Try this using one's complement: we begin with 00000011, and flip the bits to get 11111100, which is the one's complement representation of -3. The earlier representation of ~2 has not changed, i.e., it is still 11111101, which is different from 11111100. This implies that your statement that "it's actually just a one's complement" is incorrect.

Weedpacket

Well, if we're being pedantic, I thought I'd toss out this little gem from the famous [url=ftp://publications.ai.mit.edu/ai-publications/0-499/AIM-239.tiff.tar.gz]HAKMEM[/url] memo.

Bill Gosper wrote:
ITEM 154:
The myth that any given programming language is machine independent is easily exploded by computing the sum of powers of 2.

If the result loops with period = 1 with sign +, you are on a sign-magnitude machine.

If the result loops with period = 1 at -1, you are on a twos-complement machine.

If the result loops with period > 1, including the beginning, you are on a ones-complement machine.

If the result loops with period > 1, not including the beginning, your machine isn't binary -- the pattern should tell you the base.

If you run out of memory, you are on a string or Bignum system.

If arithmetic overflow is a fatal error, some fascist pig with a read-only mind is trying to enforce machine independence. But the very ability to trap overflow is machine dependent.

By this strategy, consider the universe, or, more precisely, algebra:

let X = the sum of many powers of two = ...111111
now add X to itself; X + X = ...111110
thus, 2X = X - 1 so X = -1
therefore algebra is run on a machine (the universe) which is twos-complement.

Which to me at least suggests that two's complement arithmetic (which is what all the CPUs in PCs today use) is the Right Thing. The alternative I guess would be negabinary.

bradgrafelman

All I was saying is that '~' operator translates to doing a one's complementary on the number.

Basic flow of my thought process:

~2 == -3 == 11111101

1's complement of 2 == 11111101
2's complement of 2 == 11111110

11111101 == 11111101, therefore
~2 == 1's complement of 2

Weedpacket

Ah, it's just a misunderstanding about what "It" referred to.

bradgrafelman

Weedpacket;10938178 wrote:
Ah, it's just a misunderstanding about what "It" referred to.

I think I see it now.

I was explaining why -3 is correct, assuming that the OP was just wondering why -3 was being shown, whereas laserlight was assuming that the OP wanted -2 and was wondering why ~2 wasn't working.

laserlight

bradgrafelman wrote:
All I was saying is that '~' operator translates to doing a one's complementary on the number.

Yes, that is what I mean by:

laserlight wrote:
You are thinking of a way to obtain the binary representation of a negative number given the binary representation of its absolute value.

3_grosz

bradgrafelman;10938179 wrote:
I was explaining why -3 is correct, assuming that the OP was just wondering why -3 was being shown.

Yes, I want to know why -3 is correct.

I read some book and articles and I had a headache.

I came up with an answer. The answer is below.

<?php
$two = 2;
echo ~$two; //output: -3
#0|010 (2)
#1|101

#identical output:
$two_gmp = gmp_com(2); //gmp_com — Calculates one's complement
echo gmp_strval($two_gmp); //output: -3
?>

the reason for this is because -3 is opposed to 2:
-4 -3 -2 -1 | 0 1 2 3 4

Am I right? Or I am totaly silly man?

PS. I found this example in Zend php5 certifications study guide

laserlight

3.grosz wrote:
the reason for this is because -3 is opposed to 2:
-4 -3 -2 -1 | 0 1 2 3 4

Am I right? Or I am totaly silly man?

I suppose that you could look it in that way, but then you have to draw the number line according to the signed integer representation. For example, suppose that the signed integer representation was sign and magnitude. Given an 8-bit integer $x where $x = 2, ~$x would be equal to -125. You can still explain this as "-125 is opposed to 2" by drawing the number line:
-124 -125 -126 -127 | 0 1 2 3 4

But how do I know that the number line should be drawn in this way? The answer is that I know how sign and magnitude representation works. So ultimately, you need to know what is the signed integer representation on your system (two's complement in your case), then reason about the effect of bitwise not (i.e., flip each bit to get the result), and finally interpret the result according to the rules of the signed integer representation.

Weedpacket

3.grosz wrote:
Am I right? Or I am totaly silly man?

You're certainly close. The difference between negative numbers and nonnegative numbers is that the leftmost bit is 1 for negative and 0 for nonnegative (there has to be some way of distinguishing them, after all). It's that way around because you want zero itself to be represented as 00000000, one to be represented as 00000001, two as 00000010 and so on (I'm only writing one byte because I'm too lazy to write the full thirty-two bit register).

The reason why a simple one's complement ~ isn't used is because ~0=11111111 would then mean "negative zero". Which isn't very helpful, because among other things it would mean that one minus one would not equal one plus negative one. Zero ends up appearing twice in the number line, in other words.

But waitaminute - that means that "negative zero" is actually negative one, and "negative one" is actually negative two! If you add 1 to 11111111 you get 100000000, that leading 1 drops off the end of the register leaving you with 00000000 which is what we should have got for "negative zero". If you do that to all the negative numbers you cause them to all shift up by one place (squeezing that bogus "negative zero" out in the process) without them getting out of order and addition works again.