bit manipulation - How can I perform arithmetic right shift in C in a portable way?

Question

We are writing an emulator where we need sign propagating right shift. The emulated system uses 2's complement numbers.

I read that the >> operator on signed integers in C is implementation defined. So I cannot rely on the fact it will result in the correct bit pattern in all platforms.

This means I'll need to use bit manipulation to reproduce the arithmetic right shift, and I would want to avoid unnecessary branching if possible.

EDIT:

In response to a comment:

"The missing bit is that OP needs to define what result is "correct" when the sign bit is set in x with x >> y"

I basically want to reproduce the SAR x86 instruction's behavior. There the negative numbers are represented using 2's complement. The right shift should basically mean division by 2 for negative numbers too.

This means for bit patterns starting with 1. So for 1xxxxxxx, a right shift with should result 11xxxxxx. For bit patterns starting with 0, so 0xxxxxxx right shift should result in 00xxxxxx. So MSB is "sticky". Shifting by more than word length is not defined.

Answer 1

int s = -((unsigned) x >> 31);
int sar = (s^x) >> n ^ s;

This requires 5 bitwise operations.

Explanation

As already mentioned, an arithmetic right shift x >> n corresponds to the division x / 2**n. In case the system supports only logical right shift, a negative number can be first converted into a positive number and then its sign is copied back afterwards sgn(x) * (abs(x)/2**n). This is equivalent to multiply with +/-1 before and after the right shift sgn(x) * ((sgn(x)*x)/2**n).

Multiplying an integer with +/-1 can be emulated with the conditional branchless negation s^(s+x) or (x^s)-s. When s is 0, nothing happens and x remains unchanged, so a multiplication with 1. When s is -1, we obtain -x, so a multiplication with -1.

The first line of the snippet, -((unsigned) x >> 31), extracts the sign bit. Here, the unsigned conversion ensures compilation into a logical right shift (SHR in assembly). Therefore, the immediate result is 0 or 1, and after the negation s is 0 or -1 as desired.

With two branchless negations before and after the shift, we arrive at ((s^s+x) >> n) + s ^ s. This performs a division with rounding the result towards zero (e.g. -5>>1 = -2). However, an arithmetic right shift (SAR in assembly) floors the result (i.e. -5>>1 = -3). To achieve this behaviour, one has to drop the +s operation.

A demo is here: https://godbolt.org/ and https://onlinegdb.com/Hymres0y8.

PS: I arrived here, because gnuplot has only logical shifts.