7

so, lets say I have a signed integer (couple of examples): 

-1101363339 = 10111110 01011010 10000111 01110101 in binary.
-2147463094 = 10000000 00000000 01010000 01001010 in binary.
-20552      = 11111111 11111111 10101111 10111000 in binary.

now: -1101363339 >> 31 for example, should equal 1 right? but on my computer, I am getting -1. Regardless of what negative integer I pick if x = negative number, x >> 31 = -1. why? clearly in binary it should be 1.

Bill Lynch
  • 80,138
  • 16
  • 128
  • 173
dgamma3
  • 2,333
  • 4
  • 26
  • 47
  • 1
    Pretty sure this is still undefined behavior in C. Which is to say, there's no hard rule about what'll happen on other systems. – cHao Jun 21 '13 at 00:16
  • @cHao I remember hearing that it is up to the implementation wether to make the shift arithmetic, however most choose to do so – aaronman Jun 21 '13 at 00:17
  • 1
    @aaronman: Yeah, apparently the standard (or my copy of the draft, at least) says it's implementation-defined. Oops. :) – cHao Jun 21 '13 at 00:21
  • If you're trying to use this as a test for branch-optimization or something, just mask it afterwards: `(x >> 31) & 1`. Or even better, treat it as unsigned: `(unsigned)x >> 31`. – paddy Jun 21 '13 at 00:27
  • 1
    @paddy: Or use `(x < 0)`. – jxh Jun 21 '13 at 00:41
  • "should equal 1 right?" -- Nope. "clearly in binary it should be 1" -- Nope. See http://en.wikipedia.org/wiki/Arithmetic_shift – Jim Balter Jun 21 '13 at 00:49

4 Answers4

20

Per C99 6.5.7 Bitwise shift operators:

If E1 has a signed type and a negative value, the resulting value is implementation-defined.

where E1 is the left-hand side of the shift expression. So it depends on your compiler what you'll get.

Jeff Walden
  • 7,008
  • 2
  • 38
  • 55
  • @aaronman: Cause people love a good standards quote. :) – cHao Jun 21 '13 at 00:23
  • 9
    @aaronman: cause his answer is the only correct one. – liori Jun 21 '13 at 00:23
  • 2
    @liori actually his isn't even an answer to the OP – aaronman Jun 21 '13 at 00:24
  • 1
    @aaronman: Sometimes the only correct answer is "it depends". Absent information about the CPU and compiler, you don't really know what's supposed to be the right answer. – cHao Jun 21 '13 at 00:25
  • 1
    @cHao I do not think the OP cares about the c standard rather his question is referring to the arithmetic shift of a number which is what he didn't understand, all this answer is is a quote of the standard without actually explaining what arithmetic shift is – aaronman Jun 21 '13 at 00:27
  • 2
    @aaronman: This is the only correct answer as far as the C language is concerned... – Kerrek SB Jun 21 '13 at 00:29
  • @all so, if its arithmetic it will be replace with all 1's, if the HSB is 1. so like -1101363339 >> 31 = FF FF FF FF = -1 . right? – dgamma3 Jun 21 '13 at 00:30
  • @KerrekSB just because it is correct doesn't mean it is helpful, anyone can quote the standard, this is the only answer that doesn't explain what is happening which is arithmetic bit shifting – aaronman Jun 21 '13 at 00:32
  • @dgamma3: Depends on the implementation. Each compiler/CPU combo can do things however it pleases. On your machine, with your compiler, that's apparently how it works. – cHao Jun 21 '13 at 00:32
  • 2
    @aaronman: Because it's C. *You can't count on that even happening.* – cHao Jun 21 '13 at 00:33
  • @cHao how else could it be though. the only other type of shift is logical. so your saying, it will either pick logical or arithmetic ? – dgamma3 Jun 21 '13 at 00:33
  • 3
    @dgamma3 it's implementation defined, so the OP's implementation defined it to be an arithmetic shift – aaronman Jun 21 '13 at 00:34
  • 2
    @dgamma3: It might. It might just keep the sign bit and rotate the rest. It might pick a random number. C leaves it entirely up to the compiler to specify what happens when you shift a negative number. – cHao Jun 21 '13 at 00:35
  • 2
    @aaronman: This website isn't just about being useful to any one person. It's about being useful to the community. Votes reflect that. Value to an individual is reflected by "accept" bounty. – Kerrek SB Jun 21 '13 at 00:36
  • thanks for your help guys. C is crazy right? – dgamma3 Jun 21 '13 at 00:37
  • 3
    @dgamma3: If you were to implement signed arithmetic with sign-magnitude or one's-complement representations, what would such a shift mean? The fact that there's "no natural best choice" is the reason why it's explicitly implementation-defined. An implementation can pick whichever methods suits it best (e.g. corresponds most closely to the hardware). – Kerrek SB Jun 21 '13 at 00:39
  • @KerrekSB imo quoting a part of the standard that basically says do whatever here is not helpful but I guess people are entitled to their opinions – aaronman Jun 21 '13 at 00:39
  • 1
    @cHao "Because it's C. You can't count on that even happening." This is certainly correct in the grand scheme of things. However, the behavior demonstrated by the OP can be explained by more than just saying "it depends". – Code-Apprentice Jun 21 '13 at 00:42
  • @dgamma3 - "C is crazy right?" C is what it is. Like most mainstream languages, it is very good for some applications and very bad for others. It is harder than most to use "correctly", since it defines "correctly" in a way that is impossible for a compiler to check fully. In exchange, you get portable, almost-direct access to the metal. – Nemo Jun 21 '13 at 00:52
  • @Code-Guru: Hardly. The compiler can do whatever it likes. Though the behavior is generally expected to be sane, only the docs can tell you for sure what happens. What if the compiler's behavior were to set the value to -1? Any discussion of arithmetic vs logical vs whatever becomes irrelevant without details about what behavior the implementation has defined in that case. – cHao Jun 21 '13 at 00:53
  • @Nemo: The dialects used in the 1990s provided almost-direct access to the metal. That has become unfashionable, however. If you can't imagine any reason why, on a 32-bit system with 16-bit `short`, the function `unsigned mult(unsigned short x, unsigned short y) { return x*y;}` should ever do anything other than return the arithmetical product of x and y, you lack imagination. From the standpoint of gcc's authors, the fact a processor would behave predictably doesn't give programmers any right to expect that a compiler for that processor will do likewise. – supercat May 05 '16 at 18:53
11

In most languages when you shift to the right it does an arithmetic shift, meaning it preserves the most significant bit. Therefore in your case you have all 1's in binary, which is -1 in decimal. If you use an unsigned int you will get the result you are looking for.

Per C 2011 6.5.7 Bitwise shift operators:

The result 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/ 2E2. If E1 has a signed type and a negative value, the resulting value is implementation-defined.

Basically, the right-shift of a negative signed integer is implementation defined but most implementations choose to do it as an arithmetic shift.

jxh
  • 69,070
  • 8
  • 110
  • 193
aaronman
  • 18,343
  • 7
  • 63
  • 78
5

The behavior you are seeing is called an arithmetic shift which is when right shifting extends the sign bit. This means that the MSBs will carry the same value as the original sign bit. In other words, a negative number will always be negative after a left shift operation.

Note that this behavior is implementation defined and cannot be guaranteed with a different compiler.

Code-Apprentice
  • 81,660
  • 23
  • 145
  • 268
2

What you are seeing is an arithmetic shift, in contrast to the bitwise shift you were expecting; i.e., the compiler, instead of "brutally" shifting the bits, is propagating the sign bit, thus dividing by 2N.

When talking about unsigned ints and positive ints, a right shift is a very simple operation - the bits are shifted to the right by one place (inserting 0 on the left), regardless of their meaning. In such cases, the operation is equivalent to dividing by 2N (and actually the C standard defines it like that).

The distinction comes up when talking about negative numbers. Several negative numbers representation exist, although currently for integers most commonly 2's complement representation is used.

The problem of a "brutal" bitwise shift here is, for starters, that one of the bits is used in some way to express the sign; thus, shifting the binary digits regardless of the negative integers representation can give unexpected results.

For example, commonly in 2's representation the most significant bit is 1 for negative numbers, 0 for positive numbers; applying a bitwise shift (with zeroes inserted to the left) to a negative number would (between other things) make it positive, not resulting in the (usually expected) division by 2N

So, arithmetic shift is introduced; negative numbers represented in 2's complement have an interesting property: the division by 2N behavior of the shift is preserved if, instead of inserting zeroes from the left, you insert bits that have the same value of the original sign bit.

In this way, signed divisions by 2N can be performed with just a bit of extra logic in the shift, without having to resort to a fully-fledged division routine.

Now, is arithmetic shift guaranteed for signed integers? In some languages yes1, but in C it's not like that - the behavior of the shift operators when dealing with negative integers is left as an implementation-defined detail.

As often happens, this is due to different hardware support for the operation; C is used on vastly different platforms, and, especially in the past, there was quite a difference in the "cost" of operations depending on the platform.

For example, if the processor does not provide an arithmetic right shift instruction, the compiler would be mandated to emit a much slower DIV instruction of some kind, which could be a problem in an inner loop on slower processors. For these reasons, the C standard leaves it up to the implementor to do the most appropriate thing for the current platform.

In your case, your implementation probably chose arithmetic shift because you are running on an x86 processor, that uses 2's complement arithmetic and provides both bitwise and arithmetic shift as single CPU instructions.

  1. Actually, languages like Java even have separated arithmetic and bitwise shift operators - this is mainly due to the fact that they do not have unsigned types to e.g. store bitfields.
Matteo Italia
  • 123,740
  • 17
  • 206
  • 299