用位运算符饱和签名整数乘法
好的，所以我必须做的任务是将有符号整数乘以2并返回值。 如果数值溢出，则通过返回Tmin或Tmax来使其饱和。 挑战是仅使用这些逻辑运算符（！〜＆^ | + << >>）而不使用（if语句，循环等），并且最多只允许20个逻辑运算符。
现在我的思考过程是解决这个问题，首先找到了极限。 所以我把Tmin / max除以2来得到边界。 以下是我的：
正
这和更高的作品：
1100000...
这和更低不：
1011111...
如果它不起作用，我需要返回这个：
100000...
负
这和更低的作品：
0011111...
这个和更高的不是：
0100000...
如果它不起作用，我需要返回这个：
011111...
否则，我必须返回：
2 * x;
（顺便说一句，整数是32位）
我发现前两位对于确定问题是否应该返回2 * x或限制很重要。 例如，如果第一个比特相同，则应该返回2 * x，否则应该返回限制。 另一个if语句需要整数的符号，因为它是负的Tmin需要返回，否则Tmax需要。
现在我的问题是，你如何做到这一点，而不使用if语句？ xD或者更好的问题是我计划在这种限制下运作甚至可行的方式？ 或者更好的问题是是否有更简单的方法来解决这个问题，如果是的话，又如何？ 任何帮助将不胜感激！
a = (x>>31); // fills the integer with the sign bit
b = (x<<1) >> 31; // fills the integer with the MSB
x <<= 1; // multiplies by 2
x ^= (a^b)&(x^b^0x80000000); // saturate
那么这是如何工作的。 前两行使用算术右移来填充具有选定位的整个整数。
最后一行基本上是“if语句”。 如果a==b那么右侧的计算结果为0并且x中的位不会翻转。 否则，它肯定是a==~b和右边评估为x^b^0x80000000 。 在应用语句之后， x将等于x^x^b^0x80000000 => b^0x80000000 ，这正好是饱和度值。
编辑：
这是在一个实际的程序中。
#include<stdio.h>
main(){
int i = 0xFFFF;
while(i<<=1){
int a = i >> 31;
int b = (i << 1) >> 31;
int x = i << 1;
x ^= (a^b) & (x ^ b ^ 0x80000000);
printf("%d, %dn", i, x);
}
}
你有一个非常好的起点。 一个可能的解决方案是查看前两位。
abxx xxxx
乘以2相当于左移。 所以我们的结果是
bxxx xxx0
我们看到如果b = 1那么我们必须运用我们的特殊逻辑。 在这种情况下的结果是
accc cccc
其中c = ~a 。 因此，如果我们开始使用位掩码
m1 = 0bbb bbbb
m2 = b000 0000
m3 = aaaa aaaa & bbbb bbbb
那么当b = 1 ，
x << 1; // gives 1xxx xxxx
x |= m1; // gives 1111 1111
x ^= m2; // gives 0111 1111
x ^= m3; // gives accc cccc (flips bits for initially negative values)
显然，当b = 0 ，我们没有发生任何特殊的逻辑。 只需几个操作即可获得这些掩码。 免责声明：我没有测试过这个。
上一篇: Saturating Signed Integer Multiplication with Bitwise Operators