# arithmetic right shift shifts in 0s when MSB is 1

0

As an exercise I have to write the following function:
multiply x by 2, saturating to Tmin / Tmax if overflow, using only bit-wise and bit-shift operations.
Now this is my code:

``````// xor MSB and 2nd MSB. if diferent, we have an overflow and SHOULD get 0xFFFFFFFF. otherwise we get 0.
int overflowmask = ((x & 0x80000000) ^ ((x & 0x40000000)<<1)) >>31;
// ^ this arithmetic bit shift seems to be wrong
// this gets you Tmin if x < 0 or Tmax if x >= 0
int overflowreplace = ((x>>31)^0x7FFFFFFF);

// if overflow, return x*2, otherwise overflowreplace
``````

now when `overflowmask` should be `0xFFFFFFFF`, it is 1 instead, which means that the arithmetic bit shift `>>31` shifted in 0s instead of 1s (MSB got XORed to 1, then shifted to the bottom).
x is signed and the MSB is 1, so according to C99 an arithmetic right shift should fill in 1s. What am I missing?

EDIT: I just guessed that this code isn't correct. To detect an overflow it suffices for the 2nd MSB to be 1.
However, I still wonder why the bit shift filled in 0s.

EDIT:
Example: x = 0xA0000000

``````x & 0x80000000 = 0x80000000
x & 0x40000000 = 0
XOR => 0x80000000
>>31 => 0x00000001
``````

EDIT:
Solution:

``````int msb = x & 0x80000000;
int msb2 = (x & 0x40000000) <<1;
int overflowmask = (msb2 | (msb^msb2)) >>31;
int overflowreplace = (x >>31) ^ 0x7FFFFFFF;
``````
c
bit-manipulation
bit-shift

3

Even on twos-complement machines, the behaviour of right-shift (`>>`) on negative operands is implementation-defined.

A safer approach is to work with unsigned types and explicitly OR-in the MSB.

While you're at it, you probably also want to use fixed-width types (e.g. `uint32_t`) rather than failing on platforms that don't meet your expectations.

1

`0x80000000` is treated as an unsigned number which causes everything to be converted to unsigned, You can do this:

``````// xor MSB and 2nd MSB. if diferent, we have an overflow and SHOULD get 0xFFFFFFFF. otherwise we get 0.
int overflowmask = ((x & (0x40000000 << 1)) ^ ((x & 0x40000000)<<1)) >>31;

// this gets you Tmin if x < 0 or Tmax if x >= 0
int overflowreplace = ((x>>31)^0x7FFFFFFF);

// if overflow, return x*2, otherwise overflowreplace
``````

OR write the constants in negative decimals

OR I would store all the constants in const int variables to have them guaranteed signed.

1

Never use bit-wise operands on signed types. In case of right shift on signed integers, it is up to the compiler if you get an arithmetic or a logical shift.

That's only one of your problems though. When you use a hex integer constant `0x80000000`, it is actually of type `unsigned int` as explained here. This accidentally turns your whole expression `(x & 0x80000000) ^ ...` into unsigned type because of the integer promotion rule known as "the usual arithmetic conversions". Whereas the `0x40000000` expression is signed int and works as (the specific compiler) expected.

Solution:

• All variables involved must be of type `uint32_t`.
• All hex constants involved must be `u` suffixed.
• To get something arithmetic shift portably, you would have to do
`(x >> n) | (0xFFFFFFFFu << (32-n))` or some similar hack.

User contributions licensed under CC BY-SA 3.0