c - 仅使用按位函数求出表示 2 的补码需要多少位

Question

我们可以假设 int 是 32 位的 2 补码唯一合法的运营商是: ! 〜& ^ | + << >>

此时我正在使用暴力

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

...最后 2 个陈述重复了 32 次。每次 x 移动一位时，a 就会加 1，并且 != 0 对于所有 32 位

使用测试编译器，它说我的方法在测试用例 0x7FFFFFFF(0 后跟 31 个 1)上失败，并说这个数字需要 32 位来表示。我不明白为什么这不是 31(我的方法计算的)任何人都可以解释为什么吗？我需要改变什么来解决这个问题？

Answer 1

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

111 1111 1111 1111 1111 1111 1111 1111

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

0 111 1111 1111 1111 1111 1111 1111 1111

然后将其变为 32 位。

至于你需要改变什么——你当前的程序实际上有未定义的行为。如果 0x7FFFFFFFF (2³¹-1) 是允许的最大整数值，则无法计算 0x7FFFFFFF + 1。它可能会导致 -2³²，但绝对不能保证:标准允许编译器在这种情况下执行任何操作，而现实世界的编译器实际上会执行可能会给出的优化当您违反此要求时，结果会令人震惊。类似地，如果 ... 为负数，则无法具体保证 ... >> 1 的含义，尽管在这种情况下，编译器至少需要选择一个具体行为并记录下来。 (大多数编译器选择通过复制最左边的 1 位来生成另一个负数，但不能保证这一点。)

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

• 使用不存在这些问题的算法重写整个代码；或
• 专门检查x是否为0x7FFFFFFF(返回硬编码的32)以及x的情况code> 为负数(将其替换为 ~x，即 -(x+1)，并照常进行)。