43

I have C code in which I do the following.

int nPosVal = +0xFFFF;   // + Added for ease of understanding
int nNegVal = -0xFFFF;   // - Added for valid reason

Now when I try

printf ("%d %d", nPosVal >> 1, nNegVal >> 1);

I get

32767 -32768

Is this expected?

I am able to think something like

65535 >> 1 = (int) 32767.5 = 32767
-65535 >> 1 = (int) -32767.5 = -32768

That is, -32767.5 is rounded off to -32768.

Is this understanding correct?

Peter Mortensen
  • 30,738
  • 21
  • 105
  • 131
Alphaneo
  • 12,079
  • 22
  • 71
  • 89
  • Right bit shift functions as "floored division". It always rounds towards negative infinity. In Python syntax: `-5 // 4 = -2`. – Aaron Franke Apr 13 '18 at 08:37

6 Answers6

58

It looks like your implementation is probably doing an arithmetic bit shift with two's complement numbers. In this system, it shifts all of the bits to the right and then fills in the upper bits with a copy of whatever the last bit was. So for your example, treating int as 32-bits here:

nPosVal = 00000000000000001111111111111111
nNegVal = 11111111111111110000000000000001

After the shift, you've got: 

nPosVal = 00000000000000000111111111111111
nNegVal = 11111111111111111000000000000000

If you convert this back to decimal, you get 32767 and -32768 respectively.

Effectively, a right shift rounds towards negative infinity.

Edit: According to the Section 6.5.7 of the latest draft standard, this behavior on negative numbers is implementation dependent:

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.

Their stated rational for this:

The C89 Committee affirmed the freedom in implementation granted by K&R in not requiring the signed right shift operation to sign extend, since such a requirement might slow down fast code and since the usefulness of sign extended shifts is marginal. (Shifting a negative two’s complement integer arithmetically right one place is not the same as dividing by two!)

So it's implementation dependent in theory. In practice, I've never seen an implementation not do an arithmetic shift right when the left operand is signed.

Boojum
  • 6,592
  • 1
  • 30
  • 34
  • +1, thats what I wanted to know. The right shift rounds towards negative infinity. But is it documented? – Alphaneo Dec 08 '09 at 01:34
  • 3
    It's implementation dependent. (See my edit above.) As I said though, I've never seen an implementation differ on this, but it theoretically could. – Boojum Dec 08 '09 at 06:33
23

No, you don't get fractional numbers like 0.5 when working with integers. The results can be easily explained when you look at the binary representations of the two numbers:

      65535: 00000000000000001111111111111111
     -65535: 11111111111111110000000000000001

Bit shifting to the right one bit, and extending at the left (note that this is implementation dependant, thanks Trent):

 65535 >> 1: 00000000000000000111111111111111
-65535 >> 1: 11111111111111111000000000000000

Convert back to decimal:

 65535 >> 1 = 32767
-65535 >> 1 = -32768
Mark Byers
  • 811,555
  • 193
  • 1,581
  • 1,452
  • 9
    Note that extending at the left is implementation dependent. – Trent Dec 07 '09 at 05:23
  • 3
    The standard says: "If the value of the right operand is negative or is greater than or equal to the width of the promoted left operand, the behavior is undefined." – Gonzalo Dec 07 '09 at 05:49
  • @Trent: are you sure? I thought the sign extension depends on the signedness of the left operand. – Gunther Piez Dec 07 '09 at 09:53
  • 2
    @Gonzalo: the standard does say that, but in this case the right operand is `1`. That is not negative, and neither is it >= the width of an `int`. – Steve Jessop Dec 07 '09 at 13:25
10

The C specification does not specify if the sign bit is shifted over or not. It is implementation dependent.

Trent
  • 13,249
  • 4
  • 39
  • 36
  • Q-1 asked if the result was expected. My answer suggests that no, you cannot expect any given result for the right shift of the negative number without first consulting your compilers documentation – Trent Dec 07 '09 at 06:39
  • Can you give me a link, where the standard say so? – Gunther Piez Dec 07 '09 at 09:54
3

When you right-shift, the least-significant-bit is discarded.

0xFFFF = 0 1111 1111 1111 1111, which right-shifts to give 0 0111 1111 1111 1111 = 0x7FFF

-0xFFFF = 1 0000 0000 0000 0001 (2s complement), which right-shifts to 1 1000 0000 0000 0000 = -0x8000

Anon.
  • 58,739
  • 8
  • 81
  • 86
3

A-1: Yes. 0xffff >> 1 is 0x7fff or 32767. I'm not sure what -0xffff does. That's peculiar.

A-2: Shifting is not the same thing as dividing. It is bit shifting—a primitive binary operation. That it sometimes can be used for some types of division is convenient, but not always the same.

wallyk
  • 56,922
  • 16
  • 83
  • 148
  • Integer literals are signed ints, so `- 0xFFFF` negates `0xFFFF`. That is, it's equal to `(~ 0xFFFF)-1`, interpreted as a signed integer. – outis Dec 07 '09 at 06:12
2

Beneath the C level, machines have a CPU core which is entirely integer or scalar. Although these days every desktop CPU has an FPU, this was not always the case and even today embedded systems are made with no floating point instructions.

Today's programming paradigms and CPU designs and languages date from the era where the FPU might not even exist.

So, CPU instructions implement fixed point operations, generally treated as purely integer ops. Only if a program declares items of float or double will any fractions exist. (Well, you can use the CPU ops for "fixed point" with fractions but that is now and always was quite rare.)

Regardless of what was required by a language standard committee years ago, all reasonable machines propagate the sign bit on right shifts of signed numbers. Right shifts of unsigned values shift in zeroes on the left. The bits shifted out on the right are dropped on the floor.

To further your understanding you will need to investigate "twos-complement arithmetic".

DigitalRoss
  • 143,651
  • 25
  • 248
  • 329
  • I think your definition of a "reasonable machine" is a narrow one. – Trent Dec 07 '09 at 05:27
  • If my definition is narrow then please name a single machine for which `x >> 1`, in C, will turn a negative number into a positive one. – DigitalRoss Dec 07 '09 at 05:31
  • The Microchip C18 compiler (a link to the user guide can be found here: http://tinyurl.com/ybt2svs - see section B.4) – Trent Dec 07 '09 at 06:14
  • Heh, OK. All I can say is *exceptio probat regulam in casibus non exceptis*, also known as "the exception that proves the rule", see: http://en.wikipedia.org/wiki/Exception_that_proves_the_rule – DigitalRoss Dec 07 '09 at 06:26
  • +1 ;-), thanks for the explanation about FP operations and Integer operations. Actually, I was wondering about the strange behavior of right shifting 2's complement numbers. This was different from division. – Alphaneo Dec 08 '09 at 01:43