arithmetic right shift shifts in 0s when MSB is 1

0
votes

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);
3
cbit-manipulationbit-shift
Bitwise operations using signed values are always going to be a problem. – Some programmer dude
so I just need to come up with a different solution because c doesn't work as it states? – Duke
Can you please tell us some value of x where it doesn't work as you expect? And have you tried to divide the complex expressions you have into smaller and more easily debugable expressions to see that each small sub-expression gives the value you expect? – Some programmer dude
What's happening is that the 0x80000000 in x & 0x80000000 becomes an unsigned integer, making the whole expression unsigned. Or 0x80000000 is a long or long long value, which means it's not negative. So you're shifting an unsigned or otherwise non-negative number, which means it's filled up with zeros instead of ones. I'm trying to find a reference or quote about this behavior for an answer. – Some programmer dude
It's either an unsigned int or a 64-bit signed integer (long or long long, depending on platform and compiler). – Some programmer dude

3 Answers

3
votes

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
votes

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.

1
votes

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.