4

我正在参加 Coursera 上的硬件/软件界面课程，我相信你已经看到了其中的一些问题。

其中一项任务是确定 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，如在 3 位内不能将 5 表示为 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)

问题

当分析表明在位级别上一切都相同时，我无法解释输出的差异，因此高度赞赏任何关于我可以在哪里为自己阐明这一点的提示/提示。

感谢您的时间！

sc。

4

1 回答 1

3

在方法1中，你写

10100000000000000000000000000000    x<<29
00000000000000000000000000000101    >> 29

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

首先，结果5 << 29导致带符号的 32 位（或更小）ints 溢出，这是未定义的行为。

接下来，如果移位创建了指示的位模式（如通常那样），则结果将为负数。

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

11111111111111111111111111111101    >> 29

其中，当与 5 异或时给出非零结果（然后应用!产生 0）。

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

于 2013-04-25T14:28:42.980 回答