bit shift (tilde sign)

[chipp]

i'm confused, why this code

#include <iostream>

int main() {
	unsigned int num1 = 0;
	std::cout << ~num1 << std::endl;
	std::cin.get();
	return 0;
}

prints 4294967295

and this code

#include <iostream>

int main() {
	int num1 = 0;
	std::cout << ~num1 << std::endl;
	std::cin.get();
	return 0;
}

prints -1 ? i thought it would convert all the binary digits 0s to 1s then displays the maximum number of an integer can hold...

[Disch]

i thought it would convert all the binary digits 0s to 1s

You are correct, that is exactly what it does.

then displays the maximum number of an integer can hold...

This is incorrect.

With signed integers... on a 2's compliment machine... the high bit is the sign bit, which means it has a negative weight.

For example... with 8 bit numbers:

binary   signed   unsigned
===========================
00000000     0      0
00000001     1      1
00000010     2      2
00000011     3      3
...
01111110   126    126
01111111   127    127
10000000  -128    128    <- notice!  sign!
10000001  -127    129
10000010  -126    130
...
11111110    -2    254
11111111    -1    255

[Duthomhas]

Not in two's complement.

All bits set is the first negative value, or -1.

See the numeric_limits class for information about nmbers.
http://www.cplusplus.com/reference/limits/numeric_limits/

If you want to do it yourself, use unsigned and keep the most significant bit clear:

#include <iostream>

int main()
{
  unsigned int u;

  u = ~0;
  u >>= 1;

  std::cout << u << "\n";
}

Hope this helps.

[chipp]

If you want to do it yourself, use unsigned and keep the most significant bit clear

do you mean by "most significant bit" is the left most binary digit?

All bits set is the first negative value, or -1.

do you mean is 11111111 = -1?

[Duthomhas]

Yes. In any representation the leftmost digit is the most significant, because it has greater value (or significance) than values to the right.

In two's complement, the leftmost digit is treated specially -- it is not part of the magnitude value -- it is the sign of the value.

0 == non-negative
1 == negative

So 0xxxxxxx is the same as xxxxxxx -- a non-negative value.

But 1xxxxxxx means that the value is negative. To get the absolute (non-negative) value, we need to manipulate the bits: complement (flip) all the bits and add one. Hence:

11111111
== negative ~1111111 + 1
== negative 0000000 + 1
== negative 0000001


Since an int is a signed value, simply flipping all the bits takes it from all zeros (non-negative zero) to all ones (negative one).

That's why the maximum value is all ones except the sign bit -- which is the msb if you treat the bits as unsigned instead of signed.


Hope this helps.

[chipp]

To get the absolute (non-negative) value, we need to manipulate the bits: complement (flip) all the bits and add one. Hence:

11111111
== negative ~1111111 + 1
== negative 0000000 + 1
== negative 0000001


Since an int is a signed value, simply flipping all the bits takes it from all zeros (non-negative zero) to all ones (negative one).

i don't understand this part...

[Chervil]

You should read up on twos complement
There are many articles on this topic, its a matter of finding one at the right level so as to be understood easily.
http://www.cs.cornell.edu/~tomf/notes/cps104/twoscomp.html

[chipp]

But 1xxxxxxx means that the value is negative. To get the absolute (non-negative) value, we need to manipulate the bits: complement (flip) all the bits and add one. Hence:

11111111
== negative ~1111111 + 1
== negative 0000000 + 1
== negative 0000001


Since an int is a signed value, simply flipping all the bits takes it from all zeros (non-negative zero) to all ones (negative one).

what i don't understand yet is that duoas said that flip the bits (the other 7 bits, not the 8th bit (the most significant bit, the leftmost)) is a way to get the absolute number (non-negative value, maximum number?) but the result would be:
10000001 == -127
like disch said.
so what duoas mean with "absolute number"?

[Duthomhas]

If you don't follow the math then you won't get the right answer.

Take the sign off of a signed number then it becomes unsigned, right? You now have seven bits of value, not eight.

11111111       packed is:
1 1111111      1 sign bit and 7 value bits
  1111111      toss the sign bit
  0000000      flip all bits
  0000001      add one

result is -1:

  sign bit was set
  value bits, properly adjusted, are 1

Hope this helps.

[Disch]

Duoas explanation is correct, though I personally find it easier to follow this way:

Each bit is assigned a "number". The 'least significant' or lowest bit is "bit 0":

0010 1000
^       ^
|       |
|      bit 0
|
bit 7

Each bit has a "weight" of 2ⁿ where 'n' is the bit number.

IE:

bit 0 =   2^0   =   1
bit 1 =   2^1   =   2
bit 2 =   2^2   =   4
bit 3 =   2^3   =   8
bit 4 =   2^4   =   16
bit 5 =   2^5   =   32
bit 6 =   2^6   =   64
bit 7 =   2^7   =   128

To find the numerical value of a binary number, you sum the weights of each bit that is set (1). Using my previous example:

0010 1000
^       ^
|       |
|      bit 0
|
bit 7

Here, bits 3 and 5 are set, all other bits are clear.

Therefore this number is equal to:

2³ + 2⁵
= 8 + 32
= 40


Two's compliment signed integers operate exactly the same except for one very minor difference... the most significant bit has a negative weight.

By which I mean... in an 8 bit unsigned number, bit 7 has a weight of 2⁷ = 128.

However in an 8 bit signed number, bit 7 has a weight of -(2⁷) = -128


For a final example:

1100 0010   <- bits 1, 6, and 7 set

unsigned ->   2^1 + 2^6 + 2^7   =  2 + 64 + 128  =    194
  signed ->   2^1 + 2^6 - 2^7   =  2 + 64 - 128  =    -62
                        ^                 ^
                        |                 |
                     Notice the sign difference

[Duthomhas]

...which is exactly why 2's comp works...

;o)

[chipp]

@duoas:

If you don't follow the math then you won't get the right answer.

Take the sign off of a signed number then it becomes unsigned, right? You now have seven bits of value, not eight.

11111111 packed is:
1 1111111 1 sign bit and 7 value bits
1111111 toss the sign bit
0000000 flip all bits
0000001 add one

result is -1:

sign bit was set
value bits, properly adjusted, are 1

Hope this helps.

sorry if i'm asking too much :D but there's some part i haven't perfectly understand yet. hope all of you are not tired with my questions :D

can you explain what do you mean by "sign bit was set"? and why result is still -1? i've tried too, like this:

#include <iostream>
using namespace std;

int main() {
	int num1;
	num1 = ~0; //num1 value should be: 11111111 <- 8 bits
	num1 = (num1 >> 1); //num1 is: 01111111 <- 7 bits, am i right or not?
	cout << num1 << endl; //result is still -1 i thought it would be 127
	return 0;
}

and what do you mean with "absolute (non-negative) value" in here?

But 1xxxxxxx means that the value is negative. To get the absolute (non-negative) value, we need to manipulate the bits: complement (flip) all the bits and add one.

[cire]

	num1 = ~0; //num1 value should be: 11111111 <- 8 bits
	num1 = (num1 >> 1); //num1 is: 01111111 <- 7 bits, am i right or not?
	cout << num1 << endl; //result is still -1 i thought it would be 127 

The behavior of num1 >> 1 is implementation defined, because you're right shifting a negative value. The result of this, then, is whatever your compiler says it should be. There's not any logic or rules you can follow from the standard to derive the correct pattern of bits in this case.

[edit: And, of course, you will always still have the same number of bits after a right shift. Only the bit pattern changes (if it does.)]

[Duthomhas]

Bits are "set" or "clear" (1 or 0).

The absolute value of a signed number is something you should know from grade school mathematics.


arithmetic shift
What usually happens on x86 systems is that a signed right shift keeps the sign -- the leftmost bit does not change. This is called an arithmetic shift.

    11111111 >> 1 == 11111111

To see that again, let's make the number a little different:

    10110001 >> 1 == 11011000

The underlined digits have not changed value -- that is, they haven't been changed to zero as they would be in an unsigned shift.


the standard
However, the C and C++ standards prescribe no behavior -- bitshifting a negative value (signed int, sign bit is set) is undefined.

The reasons are simple -- not all processors can perform an arithmetic shift (though I don't know how true that holds for most modern processors today), but, more importantly, those that can lead to a logical equivalence error: shifting is not the same as division when dealing with signed numbers.^[1]

So what you want to do is cast that there int to an unsigned int before you start messing with it.

  // Since we're playing with eight bits, we'll use eight-bit types.
  // This would work with 'int' and 'unsigned int' as well.
  typedef signed   char sbyte;
  typedef unsigned char ubyte;
  
  sbyte n = ~0;         cout << (int)n << endl;  // all bits set == -1
  n = (ubyte)n >> 1;    cout << (int)n << endl;  // all but msb set == 127
  
  // flipping all but the sign bit:
  n = /*the mask*/((ubyte)~0 >> 1) & /*the inverted bit value*/~n;
  n = n + 1;
  cout << "negative " << (int)n << endl;

Also, take another look at Disch's explanation. He explains quite nicely why it works.

Hope this helps.

[1] Guy L Steele Jr, Arithmetic Shifting Considered Harmful
http://dspace.mit.edu/bitstream/handle/1721.1/6090/AIM-378.pdf