c - 按位 : different behaviour with negative input value

Question

我正在参加 Coursera 上的硬件/软件接口(interface)类(class)，我相信您已经从那里看到了很多这样的问题..

其中一项作业是确定 2 的补码整数 x 是否可以放入 n 位，仅使用运算符的子集等。我做得很好，但遇到了 2 种不同的方法，并用它们敲击了白板两者都充分理解它们。然后是困惑。

如果可能适合，函数返回 1，否则返回 0。

方法一(正确输出)

int fooBar(int x, int n) {
    return !(((x << (32-n)) >> (32-n)) ^x);
}    

以正整数执行

fooBar(5,3)  == 0

正确计算出 5 不能表示为 2 的补码 3 位整数。

以负整数执行

fooBar(-4,3) == 1

正确计算出 -4 可以表示为 2 的补码 3 位整数。

方法一分析

x=5, n=3

00000000000000000000000000011101    32 - n == 29
10100000000000000000000000000000    x<<29
00000000000000000000000000000101    >> 29


00000000000000000000000000000101    5
             XOR
00000000000000000000000000000101    5
--------------------------------    
00000000000000000000000000000000    0

00000000000000000000000000000001   !0 == answer, 1.

如您所见，这将返回 0，因为 5 不能表示为 3 位以内的 2 的补码整数。

方法二(输出不正确)

int fooBar(int x, int n) {
    return !((x & ~(1 << (32-n))) ^x);
}

以正整数执行

fooBar(5,3)  == 1

误报。

以负整数执行

fooBar(-4,3) == 0

假阴性。

方法二分析

x=5, n=3

00000000000000000000000000011101    32 - n == 29

11011111111111111111111111111111    ~(1<<29)
              AND
00000000000000000000000000000101    5
--------------------------------    
00000000000000000000000000000101    5


00000000000000000000000000000101    5
              XOR
00000000000000000000000000000101    5
--------------------------------
00000000000000000000000000000000    0

00000000000000000000000000000001   !0 == answer, 1.

我正在编译:

gcc version 4.7.2 (Debian 4.7.2-5)

问题

我不知道如何解释输出的差异，因为分析表明在位级别上一切都是相同的，所以任何关于我可以从哪里弄清楚这一点的提示/技巧都是非常重要的赞赏。

感谢您的宝贵时间!

科学。

Answer 1

在方法一中，你写

10100000000000000000000000000000    x<<29
00000000000000000000000000000101    >> 29

但这不正确(请注意，您的分析意味着 fooBar(5,3) == 1 )。

首先，5 << 29的结果导致有符号 32 位(或更小)溢出 int s，这是未定义的行为。

接下来，如果移位创建了指示的位模式(通常如此)，结果将为负数。

右移负整数是实现定义的，常见的是算术右移，这将符号扩展，这里导致

11111111111111111111111111111101    >> 29

其中，当与 5 进行异或运算时给出非零结果(然后应用 ! 产生 0)。

方法 2 根本不起作用，因为除了某些输入的未定义行为外，它所做的只是检查 (32-n) 是否存在。 - 第一位已设置。