c bit-manipulation twos-complement bitcount

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

发布于 2025-01-02 19:15:02 字数 411 浏览 3 评论 0原文

我们可以假设 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 次。每次 x 移动一位时，a 都会加 1，并且 != 0 对于所有 32 位

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

原文

We can assume an int is 32 bits in 2's compliment
The only Legal operators are: ! ~ & ^ | + << >>

At this point i am using brute force

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

...
with the last 2 statements repeated 32 times. This adds 1 to a everytime x is shifted one place and != 0 for all 32 bits

Using the test compiler it says my method fails on test case 0x7FFFFFFF (a 0 followed by 31 1's) and says this number requires 32 bits to represent. I dont see why this isnt 31 (which my method computes) Can anyone explain why? And what i need to change to account for this?

分享到QQ

分享到微博

如果你对这篇内容有疑问，欢迎到本站社区发帖提问参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。

发布评论

需要登录才能够评论，你可以免费注册一个本站的账号。

往日 2025-01-09 19:15:02

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 的情况为负（将其替换为 ~x，即 -(x+1)，并照常进行）。

0x7FFFFFFF does require 32 bits. It could be expressed as an unsigned integer in only 31 bits:

111 1111 1111 1111 1111 1111 1111 1111

but if we interpret that as a signed integer using two's complement, then the leading 1 would indicate that it's negative. So we have to prepend a leading 0:

0 111 1111 1111 1111 1111 1111 1111 1111

which then makes it 32 bits.

As for what you need to change — your current program actually has undefined behavior. If 0x7FFFFFFF (2³¹-1) is the maximum allowed integer value, then 0x7FFFFFFF + 1 cannot be computed. It is likely to result in -2³², but there's absolutely no guarantee: the standard allow compilers to do absolutely anything in this case, and real-world compilers do in fact perform optimizations that can happen to give shocking results when you violate this requirement. Similarly, there's no specific guarantee what ... >> 1 will mean if ... is negative, though in this case compilers are required, at least, to choose a specific behavior and document it. (Most compilers choose to produce another negative number by copying the leftmost 1 bit, but there's no guarantee of that.)

So really the only sure fix is either:

to rewrite your code as a whole, using an algorithm that doesn't have these problems; or
to specifically check for the case that x is 0x7FFFFFFF (returning a hardcoded 32) and the case that x is negative (replacing it with ~x, i.e. -(x+1), and proceeding as usual).

回复收藏 0 原文

初与友歌 2025-01-09 19:15:02

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

Please try this code to check whether a signed integer x can be fitted into n bits. The function returns 1 when it does and 0 otherwise.

// 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));
}

回复收藏 0 原文

~没有更多了~