• Advertisement
Sign in to follow this  

bitwise NOT

This topic is 2999 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Recommended Posts

hi, well, i'm not really sure if this goes here but... why does ~(260) = -261 in "~" , 0's are changed to 1's and 1's are changed to 0's 260 in 32 bits is: 0000 0000 0000 0000 0000 0001 0000 0100 ~260 would be.... well, a lot of 1's. I read that i should use "two's complement", but all the examples i read are for 8 bits. But in this case, i dont really understand how to solve this. Can somebody explain it to how ~260 = -261 ?? thanks a lot.

Share this post


Link to post
Share on other sites
Advertisement
I may be mistaken, but IMO bitwise operations are only meaningful for unsigned types. (Where all bits are equal and one is not more significant than the others.)

In signed types, the first bit indicates sign. So if that is not set initially, flipping it makes the number negative.

Then it also follows from the two's complement, that when you flip all bits in a positive signed integer, you get basically -(n + 1)

Share this post


Link to post
Share on other sites
260 in 32 bits is as you said:
0000 0000 0000 0000 0000 0001 0000 0100

However, you need to understand how the 2s-complement works. In that notation, the most significant (leftmost) bit is the sign value for signed types. Also, it is designed in a way to aid addition.

I assume you believe the following value to equal 0:
1000 0000 0000 0000 0000 0000 0000 0000

It does not. What that value equals is:
0111 1111 1111 1111 1111 1111 1111 1111 + 1

That is the scenario where you have the largest possible value and it "rolls over" to the negative value.

1000 0000 0000 0000 0000 0000 0000 0000 actually equals the largest negative value: -2,147,483,648.

So, -1 would actually be:
1111 1111 1111 1111 1111 1111 1111 1111

And when you add one, you get all zeroes. I think this explains why -260 is "a lot of 1s."

Quote:
I may be mistaken, but IMO bitwise operations are only meaningful for unsigned types. (Where all bits are equal and one is not more significant than the others.)


I suppose it depends on what you are trying to do. I don't think it is any more or less meaningful.

Share this post


Link to post
Share on other sites
Quote:
Original post by BlackWind
~260 would be.... well, a lot of 1's.

Indeed it is!

Quote:
but all the examples i read are for 8 bits

The examples of two's complement may be for eight bits, but there's nothing special about the extension to 32 bits. Here's -10 as an eight-bit signed integer.

11110110

Now, here's the same number, but as a 16-bit signed integer.

1111111111110110

Here's the same number as a 100-bit signed integer.

1111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111110110

Get the point?

Share this post


Link to post
Share on other sites
Quote:
Original post by visitor
I may be mistaken, but IMO bitwise operations are only meaningful for unsigned types. (Where all bits are equal and one is not more significant than the others.)

The C or C++ standards probably don't specify the results of bitwise operations on signed types, but in assembly there is no difference between signed and unsigned, so the compiler will just do the naive thing.

Also, some bits are more significant than others in unsigned types. I don't know why you would think otherwise...

Share this post


Link to post
Share on other sites
Quote:
Original post by alvaro
The C or C++ standards probably don't specify the results of bitwise operations on signed types, but in assembly there is no difference between signed and unsigned, so the compiler will just do the naive thing.

Also, some bits are more significant than others in unsigned types. I don't know why you would think otherwise...
I'd be surprised if that were the case - there's plenty of reasons you'd want to do bitwise arithmetic on signed numbers (Packing a signed 32-bit fixed point value into 16 bits for instance).

Share this post


Link to post
Share on other sites
Quote:
Original post by visitor
I may be mistaken, but IMO bitwise operations are only meaningful for unsigned types.
It depends on what you mean by "meaningful". The numeric result of a bitwise operation on two unsigned integers is deterministic and platform-independent, whereas the numeric result of a bitwise operation on two signed integers is deterministic but platform-dependent (because the C-standard allows for several signed integer representations). There's no simple, elegant relationship between bitwise boolean operations and conventional arithmetic operators, but several long-standing ASM techniques (which I shall refer to as "stupid bit tricks") rely on bitwise operations to accomplish mathematically meaningful results. These often depend on a particular representation of numbers.

Share this post


Link to post
Share on other sites
Quote:
Original post by Evil Steve
Quote:
Original post by alvaro
The C or C++ standards probably don't specify the results of bitwise operations on signed types, but in assembly there is no difference between signed and unsigned, so the compiler will just do the naive thing.

Also, some bits are more significant than others in unsigned types. I don't know why you would think otherwise...
I'd be surprised if that were the case - there's plenty of reasons you'd want to do bitwise arithmetic on signed numbers (Packing a signed 32-bit fixed point value into 16 bits for instance).


You'd be surprised if what were the case?

Share this post


Link to post
Share on other sites
i might be missing something, but i'm not sure if i get it.

260 in 32 bits is:
0000 0000 0000 0000 0000 0001 0000 0100

so ~260 is:

1111 1111 1111 1111 1111 1110 1111 1011

so then, i use twos complement, right?

if so, i get:

0000 0000 0000 0000 0000 0001 0000 0101

which would be 261. But becasue when i did ~260, the leftmost bit was 1, which represents a negative value, the result would be -261.

is the process ok?

Share this post


Link to post
Share on other sites
Dont forget

~2 != -2

~2 = 0x11111101 0xFD
-2 = 0x11111110 0xFE

so -(~2) != 2

and

~0 != -0

~0 = 0x11111111
-0 = 0x00000000

Can somebody explain it to how ~260 = -261 ??

bitwise ~x = -(x+1)

260 = 0000 0001 0000 0100
~260 = 1111 1110 1111 1011

261 = 0000 0001 0000 0101
-261 = 1111 1110 1111 1011

Share this post


Link to post
Share on other sites
Assuming you fully understand the bitwise NOT operator, and the fact that it NOTs all the bits in the value (32 bits for 32 bit values, 64 for 64, etc), you can read this:

http://en.wikipedia.org/wiki/Two's_complement

You are experiencing the 2's compliment rule. Just read the above article and it'l make sense (hopefully) :p

Share this post


Link to post
Share on other sites
I'd still argue that for demonstration purposes unsigned types would be more suitable. (How negative numbers are represented is an interesting issue, but somewhat a separate topic from bitwise operators.)

While you can do things with signed values, how often do you really think about them in terms of positive and negative values? E.g, if you want all bits set, would you rather use -1 or ~0 (or 0xFFFFFFFF - BTW hex literals seem to be unsigned in C++)? If you want this bitmask 0xFFFF0000, would you consider using -65536 instead?

Share this post


Link to post
Share on other sites
Start with an 8-bit value. An unsigned 8-bit number has the range 0 to 255, or 0x00 to 0xFF. A signed 8-bit number has the range -128 to 127, or 0x80 to 0x7F. Notice how exactly half the values are positive and exactly half the values are negative as long as you consider '0' to be positive.

2's compliment works so well because it naturally falls into how a computer counts. Notice when I wrote the range for a signed 8-bit number has the range -128 to 127, and wrote the hex representation of 0x80 to 0x7F. If you start counting from 0 (0x00) and count up to 127, you get 0x7F. Add one more and you get 0x80. Adding one more to 0x7F and making it 0x80 changes the MSB (Most Significant Bit) which is the sign bit. You just rolled over from 127 (0x7F) to -128 (0x80). This means the largest negative number of any n-bit value will have the sign bit set to '1' and all other values set to '0'. 0x80 is the largest negative 8-bit value, 0x8000 is the largest negative 16-bit value, 0x80000000 is the largest negative 32-bit value, etc.

That also means the smallest negative number of any n-bit value is all '1's. A signed 8-bit value of 0xFF is -1, which makes sense. Add 1 to -1 and you get 0. Add 1 to 0xFF and you roll over and get 0x00, or 0.


Now, in 2's compliment math, in order to invert a value, you need to perform two steps. First, invert all the bits. Second, add 1. Let's look at an example. Take '87', which is 0x57 or 01010111b. Inverting the bits gets you 0xA8 or 10101000b. Now, add 1 to get 0xA9 or 10101001b. 0xA9 == -87.

As a side note: simply inverting the bits is known as 1's compliment. Adding 1 after taking the 1's compliment gives you the 2's compliment. Those works in both directions, making a negative number positive and a positive number negative.


Hope this helps.

Share this post


Link to post
Share on other sites
Quote:
Original post by visitor
I'd still argue that for demonstration purposes unsigned types would be more suitable. (How negative numbers are represented is an interesting issue, but somewhat a separate topic from bitwise operators.)

While you can do things with signed values, how often do you really think about them in terms of positive and negative values? E.g, if you want all bits set, would you rather use -1 or ~0 (or 0xFFFFFFFF - BTW hex literals seem to be unsigned in C++)? If you want this bitmask 0xFFFF0000, would you consider using -65536 instead?

I think you're confusing the reasons for using one or another a bit. If you want the bit pattern for 0xFFFF0000, then of course you use 0xFFFF0000, becuase that is what you wanted. For the same reason, if you want the bit pattern for 200, you use 200 and not 0x000000C8. It's about intent, and 0xFFFF0000 describes your intent better, not that it is unsigned and you prefer to view bit patterns as unsigned values.

Personally, I look at bit patterns as neither signed or unsigned. I look at them as bit patterns. Whether signed or unsigned, bitwise operations rarely makes any sense when looking at the values underlying datatype, and not individual bits alone.

Share this post


Link to post
Share on other sites
Quote:
Original post by Brother Bob
[...] Whether signed or unsigned, bitwise operations rarely makes any sense when looking at the values underlying datatype, and not individual bits alone.


I generally agree. The only honest exception I know occurs in the analysis of impartial games, where Nimber addition is computed as bitwise exclusive-or. In this case, negative values make no sense.

Share this post


Link to post
Share on other sites
There are some interesting bit operations you can do involving operations that don't appear at first glance to make any sense, such as ANDing with a negative number. For example, see if you can figure out what these do:


[1] x & (x - 1)
[2] (x + 8) & (-7)

Share this post


Link to post
Share on other sites
Quote:
Original post by cache_hit
For example, see if you can figure out what these do:


[1] x & (x - 1)
[2] (x + 8) & (-7)


[1] is a well-known trick to erase the last bit set in x.
[2] is a weird operation with no apparent use.

Share this post


Link to post
Share on other sites
Quote:
Original post by alvaro
Quote:
Original post by cache_hit
For example, see if you can figure out what these do:


[1] x & (x - 1)
[2] (x + 8) & (-7)


[1] is a well-known trick to erase the last bit set in x.
[2] is a weird operation with no apparent use.



[1] Which is especially useful if you're trying to test whether a number is a power of 2, since that means x & (x - 1) == 0 if and only if x is a power of 2.
[2] Temporary dyslexia. I meant to write (x + 7) & (-8)

Share this post


Link to post
Share on other sites
Quote:
Original post by cache_hit
I meant to write (x + 7) & (-8)

Round up to nearest multiple of 8.

Share this post


Link to post
Share on other sites
Quote:
Original post by cache_hit
[1] Which is especially useful if you're trying to test whether a number is a power of 2, since that means x & (x - 1) == 0 if and only if x is a power of 2.


Watch your operator precedence! `x & (x - 1) == 0' if and only if x is 1.

Share this post


Link to post
Share on other sites
Sign in to follow this  

  • Advertisement