如何在不使用班次的情况下找到 TMax

Question

仅使用

 ! ~ & ^ | +

如何确定 32 位数字是否为 TMax？

TMax 是最大的二进制补码数。

到目前为止，我的想法是：

 int isTMax(int x)
{
  int y = 0;
  x = ~x;
  y = x + x;
  return !y;
}

这只是我尝试过的许多事情之一，但我想不出 TMax 的属性可以让我恢复 TMax。与所有其他整数相比，就像将 tmax 添加到自身将是唯一的。

---

这是实际的问题：

 /*
 * isTMax - return 1 if x is the maximum, two's complement number,
 *     and 0 return otherwise.
 *   Legal ops: ! ~ & ^ | +
 *   Max ops: 10
 *   Rating: 1
 */
int isTMax(int x) {
  int y = 0;
  x = ~x;
  y = x + x;

  return !y;
}

int 是 32 位，所以最大签名可能是 0x7FFFFFFF

原文由 David 发布，翻译遵循 CC BY-SA 4.0 许可协议

Answer 1

大概是这样的？ 0x7FFFFFFF 是最大正符号 32 位二进制补码数。

 int isTMax(int x){
    return !(x ^ 0x7FFFFFFF);
}

我不确定，您可能需要将其强制转换为未签名才能正常工作。

原文由 Ben Goodrich 发布，翻译遵循 CC BY-SA 3.0 许可协议

Answer 2

在这个问题上花 3 个小时。我知道这来自 csapp 的数据实验室，它的最新要求是

1. Integer constants 0 through 255 (0xFF), inclusive. You are
  not allowed to use big constants such as 0xffffffff
....

* isTmax - returns 1 if x is the maximum, two's complement number,
 *     and 0 otherwise
 *   Legal ops: ! ~ & ^ | +
 *   Max ops: 10
 *   Rating: 1

因此，从接受的答案转移运算符（ << / >> 和 0x7FFFFFFF 现在被禁止）

下面是我的方式：

TDD 风格：

 isTmax(2147483647) == isTmax(0b011111111111...1) == 1
isTmax(2147483646) == isTmax(0b011111111111...0) == 0
isTmax(-1) == isTmax(0b111111111...1) == 0
isTmax(-2147483648) == isTmax(0b100000000...0) == 0

返回应该是 0 或 1 。在 c 中， ! 所有非零将返回 0 。所以 ! 是必须的，否则，我们不能保证所有数字都得到 0 。

第一次天真的尝试：

because 0b0111111...1 (aka 2147483647 ) is the only argument that should make isTmax return 1 and 2147483647 + 1 should be 10000000...0 （又名 -2147483648 ）

0b011111111...1 xor 0b1000000000...0 是 0b11111111111...111 。因为我们必须使用 ! ，所以我们希望看到的是 0 （又名 0b0000000000000...0 ）。显然，将 _逻辑不_（又名 ! ）应用于 0b1111111...1 ），然后我们将得到 0b000000000000 ）：

 !(~(x ^ (x + 1))

让我们打印它

void print(int x)
{
     printf("%d\n", !(~(x ^ (x + 1))));
}
int main() {
        print (2147483647);
        print(2147483646);
        print(-1);
        print(-2147483648);
}

1

0

1

0

live demo

还不错，只有 -1 没有像我们预期的那样工作。

第二次尝试：

让我们比较一下 -1 和 2147483647

11111111111111111111111111111111

01111111111111111111111111111111

我们可以找到 -1 + 1 = 0 而 2147483647 + 1 = -2147483648 。再次强调，我们想要的是 diff -1 和 2147483647 ，因为它们都返回 1 如上所示。回顾 不在 c 中的逻辑 属性： 所有非零都将返回 0 ，因此 !-2147483648 == 0 和 !(-1 + 1) != 0 。只需将 x ^ (x + 1) ( x ) 的左侧部分修改为 x + !(x + 1) 。如果 x 是 2147483647 ， x + !(x + 1) 将等于 x 。

再次运行：

 void print(int x)
{
    printf("%d\n", !(~( x + !(x + 1) ^ (x + 1))));
}
int main() {
        print (2147483647);
        print(2147483646);
        print(-1);
        print(-2147483648);
}

1

0

0

0

live demo

完毕！

原文由 Chen Li 发布，翻译遵循 CC BY-SA 4.0 许可协议