对于某些输入，使用逐位操作完成的2除法器的舍入幂失败

Question

我编写了以下函数：

int divideBy2Power(int x, int y) { return (x >> y) + (x < 0 && x << (32 - y)); }

它应该以一种非常有效的方式（即没有分支！）计算{x/（2^y）}（向零取整）

在测试中，它适用于大多数输入，但对于divideBy2Power(-2, 0)，它产生-1。同样地，x=-1, y=0产生0（而不是-1）。它适用于其他负数串。

我在一台32位的机器上，检查了x << 32是否产生零。

有什么想法吗？

Answer 1

您有两个未定义行为（UB）来源和一个实现定义行为（IDB）来源：

• x << 32是所有x的UB（假设您的平台上有32位int）
• 对于所有CCD_ 11，CCD_
• CCD_ 12是用于所有CCD_ 13的IDB

因此，你观察到的divideBy2Power(-2, 0)的任何行为都完全取决于"机会"（因为没有更好的术语）。

我意识到这并不能直接回答你的问题，但从某种意义上说，这并不重要。应不惜一切代价避免在一个表达式中调用UB两次；你需要找到一种不同的方法来编写你的函数。

Answer 2

啊，一旦分解表达式，答案就显而易见了：

新代码：

#include <stdio.h>
int divideBy2Power(int x, int y)
{
    int a = x >> y;
    int b = x < 0;
    int c = x << (32-y);
    printf("a=%dn", a); 
    printf("b=%dn", b); 
    printf("c=%dn", c); 
    printf("b&&c=%dn", (b&&c));
    return a + (b && c); 
}
int main()
{
    printf("%dn", divideBy2Power(-2, 0));
    return 0;
}

然后你可以清楚地看到b=1，c=-2，所以b&amp；c＝1。

Answer 3

您的第一个问题是添加二进制AND比较的结果&amp；（非逐位）；其将是0或1。这是荒谬的，它确实使用了一个分支，还有其他值得怀疑的逻辑。

第二，参见https://stackoverflow.com/a/9874464/1110687以解释为什么使用带符号的数字失败，以及在这种情况下什么是未定义的行为。这是关于左移，但也适用于右移。

Answer 4

也许你指的是

int divideBy2Power(int x, int y) { return (x >> y) + ( (x < 0)& (x << (32 - y))); }

注意额外的括号。<lt；而>>往往不是你所期望的。