查找仅使用按位函数表示2的补码所需的位数

我们可以假设一个int是2位恭维中的32位唯一合法的运算符是：！ 〜＆^ | + <>

此时我正在使用蛮力 

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

…最后2个语句重复32次。 每增加1次，x移位一位，！= 0，全部32位

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

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替换它，即-(x+1) ，并照常进行）。

请尝试使用此代码检查有符号整数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)); }
Interesting Posts