2

好的，所以我要做的就是将有符号整数乘以 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 或者一个更好的问题是我计划这个工作的方式，甚至在限制条件下可行？或者更好的问题是是否有更简单的方法来解决这个问题，如果有，如何解决？任何帮助将不胜感激！

4

2 回答 2

3 
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, %d\n", i, x);
    }
}
于 2015-03-26T17:37:25.883 回答
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 = 0我们的特殊逻辑都没有发生时。只需几个操作即可轻松获得这些位掩码。免责声明：我没有测试过这个。

于 2015-03-26T04:47:21.033 回答