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.
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).
User contributions licensed under CC BY-SA 3.0