Portable C and arithmetic shifts

Bitshifts are a very fast way of doing multiplication and division by powers of two, and most CPUs can execute them with just a single cycle of latency. However, there are problems with negative numbers.

Assuming that one is working with two's complement signed integers of just four bits, then one can represent the numbers -8 (1000) to +7 (0111). Left shifts, <<, fill from the left with zeros, and work as one would hope.

  0010 << 1 = 0100   (  2<<1 =  4 )
  1110 << 1 = 1100   ( -2<<1 = -4 )

Right shifts on positive numbers are also as expected.

  0100 >> 1 = 0010  ( 4>>1 = 2 )

Again we have filled with zeros.

But negative numbers are trickier.

  1100 >> 1 = 0110  ( -4>>1 = +6 )

Probably not what was expected. So for right shifts the concept of an arithmetic, as opposed to logical, shift is introduced. A logical shift fills from the right with zeros, whereas an arithmetic shift fills from the right by repeating the first bit. For positive numbers that first bit will be zero, so the two types are identical.

  1100 >> 1 = 1110  ( -4>>1 = -2 )

But this still leaves an asymmetry with respect to positive numbers.

  0001 >> 1 = 0000  (  1>>1 =  0 )
  1111 >> 1 = 1111  ( -1>>1 = -1 )

  0011 >> 1 = 0001  (  3>>1 =  1 )
  1101 >> 1 = 1110  ( -3>>1 = -2 )

etc. That repeatedly right-shifting never reaches zero is the biggest surprise.

If integers are represented in the sign and magnitude form, rather than two's complement, then -1>>1 = 0, -3>>1 = 1, etc. This is the case in python3 and the GMP library for big integers. One might say that the arithmetic shift rounds away from zero, and the sign-magnitude shift rounds towards zero, when performing division on negative numbers.

So -1>>1 can reasonably take one of three different values: 0, -1 or 2^n-1-1 where n is the number of bits in the data type.

The C language states that right shifts on signed quantities may fill either with zeros or with the highest bit. (Shifts on unsigned quantities always fill with zero.) Note too that in C, and many other languages, the number of places to shift by must be positive. It is not the case that a left shift by -2 places is equal to a right shift of 2 places, rather it is an error. Some languages offer separate logical and arithmetic shift operations (shiftr and shifts in Fortran, >>> and >> in Java).

Most C compilers, including Gnu's, follow the convention that right shifts on signed quantities are arithmetic, but this behaviour is not required by the language standard.

Portable code

Forcing arithmetic shifts

  if (x>=0)
    x=x>>i;
  else
    x=~((~x)>>i);

Forcing sign-magnitude shifts

  if (x>=0)
    x=x>>i;
  else
    x=-((-x)>>i);

Assuming one's font can distinguish between ~ (bit flip or one's complement) and - (negation).

Neither solution is ideal, as both introduce a conditional branch which may be hard to predict. There are cunning, but less readable, ways of avoiding branches whilst ensuring an arithmetic shift.