Bit shifts in C

Question

If the bit pattern corresponding to a signed integer is shifted to the right then

1   vacant bit will be filled by the sign bit 
2   vacant bit will be filled by 0 
3   The outcome is implementation dependent 
4   none of the above

The answer to this question is 3rd option.. Can anybody explain this,,

Also give some basic idea, about the theory behind left shift and right shift operators in C programming. E.g.

what is filled on the vacant bit when any of the operation is performed. I checked and noticed that left shifting fills the vacant bit by 0 and right shift fills by 1. Please clear the logic...

Answer 1

C does not guarantee that there is a sign bit, or anything about the bit-level representation of integers, that is why.

For two's complement, you will typically see the sign bit being shifted in, but that is up to the implementation.

Answer 2

I'd have to check the spec for the question of what precisely is implementation dependent. However, every implementation I've used in (mumble) years of embedded systems projects has been sensible:

• Left shifts always shift in a 0 at the low bit. No other value makes sense.

• Right shifts depend on the data type. A right shift of a signed integer duplicates the high bit as it shifts the rest to the right. This is called an "arithmetic shift", and has the nice property (in twos complement arithmetic, at least) that it divides the value by two while preserving the sign of the original number.

  A right shift of an unsigned integer shifts a 0 into the high bit, and is usually known as a "logical shift".

It makes sense for an implementation to provide both kinds of shifts because both are useful, and using signed/unsigned to select which is meant is a sensible choice.

Edit: At least one thing that absolutely is implementation dependent is that the C standard does not (completely) specify the underlying implementation of integers and their storage. For instance, it is possible to build a compliant C compiler for a machine that uses one's complement arithmetic. It would also be possible (I think) to build a compliant compiler for a machine whose native storage was signed magnitude BCD. (Nope, I was wrong, see below.)

In practice, the world is pretty much settled on two's complement binary for the CPU and some of the pedantry is mooted.

So part of the question really is: how do you define the meaning of the << and >> operators in a way that is stable regardless of the underlying arithmetic system used.

IIRC, the definition of n<<1 is effectively n*2, and n>>1 is effectively n/2, with a natural extension to shifts by more than 1 (but not more than 31... there be undefined dragons there...) and with the notion that the >> operator will preserve the sign if operating on a signed value.

Edit 2: Pete Kirkham points out in his fine answer that the C standard does specifically disallow the scary case of a BCD representation of integers, whether it is signed magnitude or ten's complement. I'm sure that is a good thing, even if Knuth did use a (optionally) BCD machine for his sample code in early editions of The Art of Computer Programming.

In those rare use cases where BCD is the right answer, then storing them in an unsigned long (8 digits ten's complement) or an unsigned 64-bit integer (room for 16 digits ten's complement or 15 digits plus sign and flags) and using a carefully crafted arithmetic library to manipulate them makes sense.

In practice, of course, C implementations map the operators as directly as allowed by the standard to the native machine instructions of the CPU. The folk who wrote the standard were very mindful of the existence of of many ways to implement even simple things like the representation of an integral value, and the C standard reflects that by allowing just enough implementation defined behavior to let operators be efficiently implemented in each machine.

The alternative leads swiftly to a world where all math operations are completely specified, and cannot be efficiently implemented on any machine.

Answer 3

The C language implementations tend to map bit shifting operations directly onto the corresponding machine code instructions. Since different hardware architectures have historically done different things, the C specification tends to leave things implementation defined so that C implementations can take advantage of whatever the hardware offers.

Answer 4

The outcome is implementation dependent. However, in practice, every single x86, PPC, and MIPS compiler I have ever worked with has followed this rule for shifting right:

1. If the operand is a signed integer, the vacant bit is filled with the sign bit (really the most significant bit)

2. If the operand is an unsigned integer, the vacant bit is filled with zero.

As RBerteig says, this is so that for signed integers, n >> 1 = n/2 (rounded down) for both positive and negative n, and for unsigned integers, n >> 1 = n/2 even for n > 2^31 (on a 32-bit architecture).

The corresponding hardware instructions are arithmetic (sign-extending) and logical (not sign-extending) shift; the compiler chooses between them based on whether the operand is signed or unsigned.

Answer 5

ISO C99 requires a sign bit somewhere in the representation, but gives the option between various compliment/sign and magnitude schemes and allows padding bits, all of which effect the operation of >>.

Section 6.2.6.2 (Integer types)

For signed integer types, the bits of the object representation shall be divided into three groups: value bits, padding bits, and the sign bit. There need not be any padding bits; there shall be exactly one sign bit.

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

It doesn't specify which of 1's compliment, 2's compliment or sign and magnitude is used, nor whether the sign bit is left or right of the value bits, or where any padding is, all of which would effect the output of the >> operator on signed negatives.

In answer to RBerteig's query, C99 precludes a BCD representation of integers:

Section 6.2.6.2 (Integer types)

If there are N value bits, each bit shall represent a different power of 2 between 1 and 2 N −1 , so that objects of that type shall be capable of representing values from 0 to 2 N − 1 using a pure binary representation; this shall be known as the value representation.