c - 带溢出校正的按位乘法

Question

我尝试在 C 中使用位运算符 (!~ & ^ | + << >>) 来实现 4 的乘法，同时还通过分别返回最大值和最小值来纠正正溢出和负溢出。例如，

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

我的主要方法是检查产品的标志，看看它是否发生了预期的变化。

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

目前，当乘以 0x7fffffff 时，我得到 -1，而不是预期的 0x7FFFFFFF。我知道某处可能需要移动 1，但我无法找到我的错误。

Answer 1

这是^最后一行需要是 &并且必须在第一个和第二个位移位中检测到溢出。

对功能的这种轻微重组对我来说似乎更直观:

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

当然，代码取决于 int 大小是否为 32 位。您可以使用固定宽度类型 int32_t或替换31通过((int)((sizeof(int)<<3)-1)) (可以在宏中定义)。