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
return ((x<<1) & ~overflowmask)|(overflowreplace & overflowmask);

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;
return ((x<<1) & ~overflowmask) | (overflowreplace & overflowmask);
c
bit-manipulation
bit-shift
asked on Stack Overflow Jan 9, 2020 by Duke • edited Jan 9, 2020 by Duke

3 Answers

▲
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.

answered on Stack Overflow Jan 9, 2020 by Toby Speight
▲
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
return ((x<<1) & ~overflowmask)|(overflowreplace & overflowmask);

OR write the constants in negative decimals

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

answered on Stack Overflow Jan 9, 2020 by Topa
▲
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.
answered on Stack Overflow Jan 9, 2020 by Lundin

User contributions licensed under CC BY-SA 3.0