10

我在理解这段代码的工作方式和原因时遇到了一些麻烦。我在这项任务中的合作伙伴完成了这部分，我无法让他了解它是如何以及为什么起作用的。我已经尝试了一些不同的方法来理解它，但是任何帮助都将不胜感激。此代码使用 2 的补码和 32 位表示。

/* 
 * fitsBits - return 1 if x can be represented as an 
 *  n-bit, two's complement integer.
 *   1 <= n <= 32
 *   Examples: fitsBits(5,3) = 0, fitsBits(-4,3) = 1
 *   Legal ops: ! ~ & ^ | + << >>
 *   Max ops: 15
 *   Rating: 2
 */
int fitsBits(int x, int n) {
    int r, c;
    c = 33 + ~n;
    r = !(((x << c)>>c)^x);
    return r;
}
4

3 回答 3

14 
c = 33 + ~n;

n这将计算在使用低位后剩余多少高位。

((x << c)>>c

这用与 的符号位相同的值填充高位x。

!(blah ^ x)

这相当于

blah == x
于 2013-02-09T22:59:49.320 回答
14

  • 在 2 的补码平台-n上等价于~n + 1. 因此，c = 33 + ~n在这样的平台上实际上相当于c = 32 - n. 这旨在表示如果低位被占用，则c32 位int值中剩余多少高位。n

    请注意此代码中存在的两个平台依赖性：2 的补码平台，32 位int类型。

  • 然后((x << c) >> c旨在对那些高阶位进行符号填充。c符号填充意味着那些在 bit-position 中的值x，0这些n - 1高阶位必须清零。但是对于那些在 bit-position 中的值x，1这些n - 1高位必须用1s 填充。这对于使代码对 . 的负值正常工作很重要x。

    这引入了另外两个平台依赖性：<<在移动负值或1移动到符号位时表现良好的运算符（正式地它是未定义的行为）和>>在移动负值时执行符号扩展的运算符（正式地它是实现定义的)

  • 其余的，如上面回答的，只是与原始值的比较x:!(a ^ b)相当于a == b。如果上述转换没有破坏 then 的原始值，x则x确实适合n2 的补码表示的低位。

于 2015-08-30T03:22:07.527 回答
3

对有符号整数使用按位补码（一元~）运算符具有实现定义和未定义的方面。换句话说，即使您只考虑二进制补码实现，此代码也不可移植。

重要的是要注意，即使是 C 中的二进制补码表示也可能有陷阱表示。6.2.6.2p2 甚至非常清楚地说明了这一点：

如果符号位为 1，则该值应通过以下方式之一进行修改：

-- 符号位为 0 的对应值取反（符号和幅度）；

-- 符号位的值为 -(2 M )（二进制补码）；

-- 符号位的值为 -(2 M - 1)（反码）。

其中哪个适用是实现定义的，符号位为 1 且所有值位为零（对于前两个）或符号位和所有值位为 1（对于一个补码）的值是否是陷阱表示或正常值。

重点是我的。使用陷阱表示是未定义的行为。

有一些实际的实现将该值保留为默认模式下的陷阱表示。我倾向于引用的值得注意的是OS2200 上的 Unisys Clearpath Dordado（转到 2-29）。请注意该文件上的日期；这样的实现不一定是古老的（因此我引用这个的原因）。

根据6.2.6.2p4，向左移动负值也是未定义的行为。我还没有对现实中存在哪些行为进行大量研究，但我有理由期望可能存在符号扩展的实现，以及没有符号扩展的实现。这也是形成上述陷阱表示的一种方式，其本质上是未定义的，因此是不受欢迎的。从理论上讲（或者可能在遥远或不那么遥远的将来的某个时间），您可能还会面临“对应于计算异常”的信号（这是一个类似于SIGSEGV落入的 C 标准类别，对应于诸如“除以零”）或其他不稳定和/或不良行为......

总之，问题中的代码有效的唯一原因是巧合，您的实现所做的决定恰好以正确的方式对齐。如果您使用我列出的实现，您可能会发现对于某些值，此代码无法按预期工作。

如此沉重的魔法（正如评论中所描述的）并不是真正必要的，而且对我来说看起来也不是那么理想。如果您想要一些不依赖魔法的东西（例如可移植的东西）来解决这个问题，请考虑使用这个（实际上，这段代码至少可以工作1 <= n <= 64）：

#include <stdint.h>

int fits_bits(intmax_t x, unsigned int n) {
    uintmax_t min = 1ULL << (n - 1),
              max = min - 1;
    return (x < 0) * min + x <= max;
}
于 2015-08-30T04:22:56.990 回答