9

The book "C The Complete Reference" by Herbert Schildt says that "(In the case of a signed, negative integer, a right shift will cause a 1 to be brought in so that the sign bit is preserved.)"

What's the point of preserving the sign bit?

Moreover, I think that the book is referring to the case when negative numbers are represented using a sign bit and not using two's complement. But still even in that case the reasoning doesn't seem to make any sense.

Peter Mortensen
  • 30,738
  • 21
  • 105
  • 131
Nikunj Banka
  • 11,117
  • 16
  • 74
  • 112
  • 4
    Off topic a little - http://stackoverflow.com/a/579795/1520364 – Karthik T Jun 28 '13 at 06:22
  • 1
    Comprehensively answered already http://stackoverflow.com/questions/7622/shift-operator-in-c – Paul Dixon Jun 28 '13 at 06:26
  • "what 's the point of preserving the sign bit?" -- Because -2/2 is -1. " I think that the book is referring to the case when negative numbers are represented using a sign bit and not using 2s complement." -- No. "even in that case the reasoning doesn't seem to make any sense." -- No, you lack understanding. – Jim Balter Jun 28 '13 at 06:28
  • Not a duplicate because the duplicate cites irrelevant sources such as the obsolete K&R and Wikipedia. It's almost as bad as citing Schildt. I've posted an answer with the relevant source. – Lundin Jun 28 '13 at 06:34
  • 6
    @Lundin: If that answer is out of date, then arguably you should post a better answer there (or update the accepted answer). Either way, it doesn't stop this Q being a duplicate... – Oliver Charlesworth Jun 28 '13 at 06:37
  • @OliCharlesworth Fair enough, but the supposed duplicate asks whether right shift is arithmetic or logical, which is not really the same question as this one. A compiler could implement right shift on negative numbers as logical, arithmetic, rotation, "always shift-in 1" etc etc. – Lundin Jun 28 '13 at 06:42
  • @Lundin: it could not use rotation; 'always shift-in 1' for negative values is 'arithmetic shift right', so you have but two choices: arithmetic shift right or logical shift right. – Jonathan Leffler Jun 28 '13 at 06:45
  • 1
    @JonathanLeffler The C standard allows other forms of signedness than two's complement. It is not really clear to me what arithmetic shift means in practice, on a CPU that is not using two's complement. And why can't it use rotation? There is nothing in the C standard forbidding it. – Lundin Jun 28 '13 at 06:48
  • Always heard rumors about the infamous *Schildt*-books. But this question nails it. – Christian Rau Jun 28 '13 at 09:43
  • @Lundin: there is nothing permitting the use of rotate instructions. It doesn't matter which architecture you use (sign-magnitude, one's complement or two's complement), rotate is going to be wrong. I'm not going to fight over the rest; it isn't worth it. – Jonathan Leffler Jun 28 '13 at 13:15

4 Answers4

18

The Schildt book is widely acknowledged to be exceptionally poor.

In fact, C doesn't guarantee that a 1 will be shifted in when you right-shift a negative signed number; the result of right-shifting a negative value is implementation-defined.

However, if right-shift of a negative number is defined to shift in 1s to the highest bit positions, then on a 2s complement representation it will behave as an arithmetic shift - the result of right-shifting by N will be the same as dividing by 2N, rounding toward negative infinity.

caf
  • 233,326
  • 40
  • 323
  • 462
  • 2
    can you explain this line "the result of right-shifting by N will be the same as dividing by 2^N, rounding toward negative infinity."? – Jagdish Feb 06 '16 at 19:38
  • 5
    @JagsVG: For example, if you have the 8-bit 2s complement binary number 11111101 representing -3 in decimal, and you perform an arithmetic right shift to give 11111110 representing -2 in decimal, this is the same as dividing -3 by 2^1, giving -1.5 which rounds towards negative infinity resulting in -2. – caf Feb 07 '16 at 10:00
8

The statement is sweeping and inaccurate, like many a statement by Mr Schildt. Many people recommend throwing his books away. (Amongst other places, see The Annotated Annotated C Standard, and ACCU Reviews — do an author search on Schildt; see also the Definitive List of C Books on Stack Overflow).

It is implementation defined whether right shifting a negative (necessarily signed) integer shifts zeros or ones into the high order bits. The underlying CPUs (for instance, ARM; see also this class) often have two different underlying instructions — ASR or arithmetic shift right and LSR or logical shift right, of which ASR preserves the sign bit and LSR does not. The compiler writer is allowed to choose either, and may do so for reasons of compatibility, speed or whimsy.

ISO/IEC 9899:2011 §6.5.7 Bitwise shift operators

¶5 The result of E1 >> E2is 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.

Community
  • 1
  • 1
Jonathan Leffler
  • 730,956
  • 141
  • 904
  • 1,278
1

The point is that the C >> (right shift) operator preserves1 the sign for a (signed) int.

For example:

int main() {
  int a;
  unsigned int b;

  a = -8;
  printf("%d (0x%X) >> 1 = %d (0x%X)\n", a, a, a>>1, a>>1);

  b = 0xFFEEDDCC;
  printf("%d (0x%X) >> 1 = %d (0x%X)\n", b, b, b>>1, b>>1);

  return 0;
}

Output:

-8 (0xFFFFFFF8) >> 1 = -4 (0xFFFFFFFC)                    [sign preserved, LSB=1]
-1122868 (0xFFEEDDCC) >> 1 = 2146922214 (0x7FF76EE6)      [MSB = 0]

If it didn't preserve the sign, the result would make absolutely no sense. You would take a small negative number, and by shifting right one (dividing by two), you would end up with a large positive number instead.

1 - This is implementation-defined, but from my experience, most compilers choose an arithmetic (sign-preserving) shift instruction.

Jonathon Reinhart
  • 132,704
  • 33
  • 254
  • 328
  • And here I was thinking that I had an easy question to answer for once... way to have the quick fingers! – It'sPete Jun 28 '13 at 06:24
  • 9
    Nope; this is implementation-defined. – Oliver Charlesworth Jun 28 '13 at 06:26
  • @NikunjBanka "But why does it preserve the sign? Is there any specific reason for this?" -- it was just explained to you. – Jim Balter Jun 28 '13 at 06:31
  • @NikunjBanka Probably because `int` is a signed type. If you don't want this behavior, use an `unsigned type`. – Jonathon Reinhart Jun 28 '13 at 06:32
  • @OliCharlesworth: While it is technically implementation-defined, I would expect that implementations where `-1>>1 != -1` are even rarer than ones where `(unsigned char)(-1) != 0xFF`. If what one wants is the behavior that 99% of compilers will implement for `x>>1`, I know of no nicer or clearer way of expressing it. – supercat Nov 20 '13 at 00:45
  • then why <<(left shift) operator doesn't preserve the sign in signed system? – pankaj prasad Sep 05 '20 at 17:24
0

In the case of a signed, negative integer, a right shift will cause a 1 to be brought in so that the sign bit is preserved

Not necessarily. See the C standard C11 6.5.7:

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.

This means that the compiler is free to shift in whatever it likes (0 or 1), as long as it documents it.

Jonathan Leffler
  • 730,956
  • 141
  • 904
  • 1,278
Lundin
  • 195,001
  • 40
  • 254
  • 396
  • I've used more compilers where `CHAR_BITS != 8` than where `-1 >> 1 != -1`. Have you encountered compilers which didn't copy the sign bit? – supercat Nov 20 '13 at 00:47
  • @supercat I can't recall any such compiler, in my experience most compilers use arithmetic right shift rather than logical right shift for signed numbers. But then in 99% of the cases, it doesn't make much sense to use bitwise operators on signed types. – Lundin Nov 20 '13 at 10:26
  • Given four signed numbers a, b, c, d, such that |a+b+c+d| < INT_MAX, how would you compute an average such that the computed value is within +/- 1/2 of the correct value? If signed right-shift is defined, then `(a+b+c+d+2)>>2` is apt to be both clearer and faster than any alternative I can think of. A floored division operator might be preferable if one existed, but none does. Using the division operator with signed operands wouldn't make sense, since the compiler would have to do extra work to handle negative values differently, and then user code would have to do extra work to undo that. – supercat Nov 20 '13 at 16:12
  • I'm curious how truncated division came to be the norm; I recall reading that in the earliest versions of FORTRAN the behavior of integer division was only defined for positive operands, and from a "don't pay for what you don't use" standpoint that would have made sense for C as well. If there were many cases where a truncated result could be used without regard for the signs of the operands (as the floored result could in the average above) it might make sense, but such cases seem very rare. In cases where code needs to care about the signs of the operands... – supercat Nov 20 '13 at 16:21
  • ...it could generally ensure that division operands are always positive. For example, `(total < 0 ? (signed)((1u-total) / 4u)-1 : (signed)((total+2u)/4u)` is probably about as efficient than any other approach using the division operator, but it never needs to divide negative values. – supercat Nov 20 '13 at 16:25
  • @supercat Replacing shift with division for the sake of performance is a classic example of premature optimization. Nowadays, any half-decent compiler will do that optimization for you, behind the lines. Thus the correct way to write such an algorithm is the most readable one: use an array, use a for loop for the addition, then divide using the `/` operator. How the division is handled and how effective it will be, is completely CPU-dependent. Leave it to the compiler to determine whether right shift or a hardware "DIV" instruction is more efficient for the specific case. – Lundin Nov 21 '13 at 07:22
  • I think you missed my point, unless you regard the workarounds which are necessary to make division yield the *correct answer* as being more readable than simply using a shift which *inherently* gives the correct answer on 99.9% or more of actively-maintained C compilers. – supercat Nov 21 '13 at 15:47