C - 使用按位运算符饱和有符号整数乘法

Question

好的，所以我要做的作业是将一个带符号的整数乘以 2 和 return 的值。如果该值溢出，则通过 returning Tmin 或 Tmax 使其饱和。挑战在于仅使用这些逻辑运算符 (! ~ & ^ | + << >>) 而没有（if 语句、循环等）并且最多只允许使用 20 个逻辑运算符。

现在我解决这个问题的思维过程首先是找到极限。所以我将 Tmin/max 除以 2 得到边界。这是我拥有的：

积极

此作品及更高作品：

1100000...

这个和更低的不是：

1011111...

如果它不起作用，我需要 return 这个：

100000...

否定

这个和更低的作品：

0011111...

这个和更高版本没有：

0100000...

如果它不起作用，我需要 return 这个：

011111...

否则我必须return:

2 * x;

（整数是 32 位的）

我看到前两位对于确定问题是否应该 return 2*x 或限制很重要。例如，XOR 会执行，因为如果第一个到位相同，则 2*x 应该 returned，否则限制应该 returned。然后需要另一个 if 语句来表示整数的符号，因为它是负数 Tmin 需要 returned，否则 Tmax 需要

现在我的问题是，你如何在不使用 if 语句的情况下做到这一点？ xD 或者一个更好的问题是我计划如何在限制条件下工作或什至可行？或者更好的问题是是否有更简单的方法来解决这个问题，如果有的话如何解决？任何帮助将不胜感激！

Answer 1

你的出发点很好。一种可能的解决方案是查看前两位。

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 = 0none我们的特殊逻辑就发生了。只需几次操作即可直接获得这些位掩码。免责声明：我没有测试过这个。

Answer 2

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 statement"。如果 a==b 则右侧的计算结果为 0 并且 x 中的 none 位被翻转。否则它必须是 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, %d\n", i, x);
    }
}

C - 使用按位运算符饱和有符号整数乘法

C - Saturating Signed Integer Multiplication with Bitwise Operators

c

bit-manipulation

multiplication

saturation-arithmetic