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);
```

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

`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

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