[C] right shifting an int number

[C] right shifting an int number
by Zepper on 2010-03-16 (#58476)

- From what I know, for an integer number (let's say 32bit long), the MSB is 1 if the value is negative; else, equals to 0.

- By using a shifting decay, like value -= value >> n; does the MSB take effect? In code:

Code:

 let's say the binary 1000 0000 0000 0000 0000 0000 0000 0000

would right shift 1 result... 0100 0000 0000 0000 0000 0000 0000 0000 ?

by tepples on 2010-03-16 (#58477)

This behavior is implementation-defined. You cannot rely on it if you expect your program to be portable to all platforms capable of running C or C++ programs.

But if you care only about popular compilers for popular architectures (x86, PowerPC, ARM), operator >> behaves as follows:
Shifting an unsigned integer zero-extends the result.
Shifting a signed integer sign-extends the result.
Both shifts "round" toward negative infinity.

You'll want to use a compile-time assertion in any module that relies on this theoretically nonportable behavior.

But your shifting decay itself looks suspect. Ask yourself this: what happens once it gets within (1<<n) of the zero? The behavior becomes inconsistent for positive and negative numbers.

by blargg on 2010-03-16 (#58481)

If you want a portable semi-equivalent, divide by 2. A smart compiler will convert a divide by 2 into a shift and round internally.

If you must have a shift but want it portable and don't trust the compiler to optimize /2, convert to offset binary, shift right, then convert back to signed (you might note that the last operation is equivalent to sign the last step of sign extension on the Bit Twiddling Hacks page):
Code:
// equivalent to i>>1 with sign preservation, without depending on
// host platform performing said preservation. Can be generalized
// to i>>n easily.
inline int fast_right_shift( int i )
{
// i: INT_MIN ... -1 0 ... INT_MAX
unsigned u = (unsigned) i; // no-op on most CPUs
// u: INT_MAX+1 ... UINT_MAX 0 ... INT_MAX
u += (unsigned) INT_MIN;
// u: 0 ... INT_MAX INT_MAX+1 ... UINT_MAX
u >>= 1;
// u: 0 ... INT_MAX/2 (INT_MAX+1)/2 ... UINT_MAX/2
i = (int) u - (int) ((unsigned) INT_MIN >> 1);
// i: INT_MIN/2 ... -1 0 ... INT_MAX/2
return i;
}

by Jarhmander on 2010-03-18 (#58602)

In C (and C++) you can just right shift an ordinary signed integral type, it will extend the sign bit (MSB) and the value will be rounded toward negative infinity (that is, -1 >> 1 == 1) -- what you could call a ASR. If you right shift a unsigned integral type though, it will just put a zero at the MSB -- like a LSR.

by blargg on 2010-03-18 (#58608)

~J-@D!~ wrote:
In C (and C++) you can just right shift an ordinary signed integral type, it will extend the sign bit (MSB) and the value will be rounded toward negative infinity (that is, -1 >> 1 == 1) -- what you could call a ASR.

That's implementation-defined, as tepples noted. You could just as well have -1>>1 == INT_MAX. If you want divide by two, write i/2 (unfortunately C99 has standardized on round to zero, rather than the more useful round to negative, which can be implemented by ASR).