Bitwise multiplication with correction for overflow

-1

I am trying to use Bitwise operators ( ! ~ & ^ | + << >> ) in C to achieve a multiplication of 4 while also correcting for Positive and Negative overflow by returning the Max value and Minimum value, respectively. For example,

Function(0x10000000) = 0x40000000
Function(0x20000000) = 0x7FFFFFFF
Function(0x80000000) = 0x80000000

My primary method is checking the sign of the product to find if it changed expectedly.

    int funcMultBy4(int x){
        int signedBit=(x>>31);                                                                            
        int minValue= 1<<31;
        int xtimes4= x<<2;
        int maxValue= (x ^ xtimes4) >> 31;
        int saturate= maxValue & (signedBit ^ ~minValue);
        return saturate | (xtimes4 ^ ~maxValue) ;
     }

Currently, when multiplying 0x7fffffff, I am getting -1 rather than an expected 0x7FFFFFFF. I understand there is probably a necessary shift by 1 somewhere, but am having trouble finding my error.

c
bit-manipulation
asked on Stack Overflow Oct 4, 2019 by letsgetphysical • edited Oct 4, 2019 by letsgetphysical

1 Answer

2

It is the ^ in the last line that needs to be & and overflow must be detected in both the first and second bit-shift.

This slight reorganisation of the function seems more intuitive to me:

     int funcMultBy4(int x)
     {
        int signedBit = (x>>31);
        int minValue = 1<<31;
        int xtimes4 = x<<2;
        int overflow = (x ^ (x<<1) | (x ^ (x<<2))) >> 31;
        int saturate = (signedBit ^ ~minValue);
        return (overflow & saturate) | (~overflow & xtimes4) ;
     }

Of course, the code depends on the int size to be 32 bits. You may either use the fixed-width type int32_t or replace 31 by ((int)((sizeof(int)<<3)-1)) (could be defined in a macro).

answered on Stack Overflow Oct 4, 2019 by nielsen • edited Oct 4, 2019 by nielsen

User contributions licensed under CC BY-SA 3.0