CODEWITHSUNDEEP
c++
Max
Max

Reputation: 1087

Why -1 >> 1 is -1 ? And 1 >> 1 is 0!

I have next code: 

std::cout << (-10 >> 1) << std::endl;
std::cout << (-9 >> 1) << std::endl;
std::cout << (-8 >> 1) << std::endl;
std::cout << (-7 >> 1) << std::endl;
std::cout << (-6 >> 1) << std::endl;
std::cout << (-5 >> 1) << std::endl;
std::cout << (-4 >> 1) << std::endl;
std::cout << (-3 >> 1) << std::endl;
std::cout << (-2 >> 1) << std::endl;
std::cout << (-1 >> 1) << std::endl;

The result is:

-5
-5
-4
-4
-3
-3
-2
-2
-1
-1

But why?

-1 is 1111 1111 (for 1 byte), -1 >> 1 must be : 1011 1111 and it is not -1 or 0! (sign-bit is not shifted, I know)

Can someone explain to me how this works?

Upvotes: 16

Views: 673

Answers (4)

Jay
Jay

Reputation: 27474

In general, right-shifts are defined as being implemented as either "arithmetic" or "logical" The difference is that with a logical right shift, the left-most bit is always set to zero. With an arithmetic right shift, the left-most bit is a copy of the previous value.

For example, let's pretend the value is just 8 bits to make things easier to keep track of. Then:

Logical:

0111 1111 >> 1 = 0011 1111
1111 1111 >> 1 = 0111 1111
1111 1110 >> 1 = 0111 1111

Arithmetic:

0111 1111 >> 1 = 0011 1111
1111 1111 >> 1 = 1111 1111
1111 1110 >> 1 = 1111 1111

An arithmetic right-shift is equivalent to dividing by 2 and rounding toward negative infinity.

In C++, whether the right-shift operator is logical or arithmetic is implementation-specific. i.e. each compiler writer may decide for himself, probably based on what is easier to do giving the architecture of the computer he's working on.

Your statement that the sign bit is not shifted is incorrect. The sign bit is shifted just like all the other bits. The only question is what replaces it.

Java has two different right-shift operators: >> is arithmetic and >>> is logical.

Upvotes: 3

Clifford
Clifford

Reputation: 93476

-1 >> 1 must be : 1011 1111

If that were true, -10 >> 1 would be 10111011 == -69 in two's complement. Not a very useful result!

Although the language behaviour is undefined (so the result, useful or otherwise cannot be relied upon), the common behaviour (and that exhibited in this case) is to perform "sign-extension".

It is not true that the "sign-bit is not shifted", it is shifted, and the vacated bit is filled with a value equal to the sign bit. This behavour both preserves the sign and provides the 'expected' divide-by-two operation that you have observed for all values except -1. For negative values -1 is the 'terminal value' of a right shift, as zero is for positive numbers. That is to say right shift of a negative number tends to -1, and a positive number tends to zero.

Upvotes: 3

Jason S
Jason S

Reputation: 189686

Right-shifting a negative number is implementation-defined.

Implementations which shift in a sign-extended bit to the leftmost bit, work as you reported.

As for why it is done this way, it's because right-shifting can be used to divide by a power of 2 with round-towards-negative-infinity (e.g. like floor()) rounding behavior:

(-8 >> 2) == -2
(-9 >> 2) == -3
(-10 >> 2) == -3
(-11 >> 2) == -3
(-12 >> 2) == -3

See this SO question.

Upvotes: 17

icecrime
icecrime

Reputation: 76755

Standard 5.8/3 (Shift operators) :

The value of E1 >> E2 is E1 right-shifted E2 bit positions. If E1 has an unsigned type or if E1 has a signed type and a nonnegative value, the value of the result is the integral part of the quotient of E1 divided by the quantity 2 raised to the power E2. If E1 has a signed type and a negative value, the resulting value is implementation-defined.

So to the question "why ?", the standard answer is : why not.

Upvotes: 24

Related Questions