-1

我们可以假设 int 在 2 的补码中是 32 位唯一合法的运算符是：！~ & ^ | + << >>

在这一点上，我正在使用蛮力

int a=0x01;
x=(x+1)>>1; //(have tried with just x instead of x+1 as well)
a = a+(!(!x));

...最后两条语句重复了 32 次。每次将 x 移动一位时，这会将 1 加到 a 上，对于所有 32 位，!= 0

使用测试编译器，它说我的方法在测试用例 0x7FFFFFFF（一个 0 后跟 31 个 1）上失败，并说这个数字需要 32 位来表示。我不明白为什么这不是 31 （我的方法计算出来的） 谁能解释为什么？我需要改变什么来解决这个问题？

4

2 回答 2

2

0x7FFFFFFF确实需要32位。它可以表示为仅 31 位的无符号整数：

111 1111 1111 1111 1111 1111 1111 1111

但是如果我们将其解释为使用二进制补码的有符号整数，那么前导1将表明它是负数。所以我们必须在前面加上一个前导0：

0 111 1111 1111 1111 1111 1111 1111 1111

然后使它成为32位。

至于你需要改变什么——你当前的程序实际上有未定义的行为。如果0x7FFFFFFF(2 31 -1) 是允许的最大整数值，则0x7FFFFFFF + 1无法计算。它可能会导致 -2 32，但绝对不能保证：标准允许编译器在这种情况下绝对做任何事情，而现实世界的编译器实际上会执行优化，当您违反此要求时可能会产生令人震惊的结果. ... >> 1同样，如果为负数，也没有具体的保证意味着什么...，尽管在这种情况下，至少需要编译器来选择特定的行为并记录它。（大多数编译器选择通过复制最左边的来产生另一个负数1位，但不能保证这一点。）

所以真的唯一确定的解决方法是：

  • 使用不存在这些问题的算法将代码作为一个整体重写；或者
  • 专门检查情况x（0x7FFFFFFF返回硬编码32）和x否定情况（将其替换为~x, ie-(x+1)并照常进行）。
于 2012-02-03T01:55:26.970 回答
2

请尝试使用此代码检查有符号整数x是否可以适合n位。该函数在执行时返回 1，否则返回 0。

// http://www.cs.northwestern.edu/~wms128/bits.c
int check_bits_fit_in_2s_complement(signed int x, unsigned int n) {
  int mask = x >> 31;

  return !(((~x & mask) + (x & ~mask))>> (n + ~0));
}
于 2013-04-19T13:00:51.697 回答