按位运算和转换

Question

我很难理解这段代码的工作方式和原因.我在这个任务中的合作伙伴完成了这一部分,我无法得到他,以了解它的工作原理和原因.我已经尝试了一些不同的东西来理解它,但任何帮助将非常感激.此代码使用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;
}

Answer 1

c = 33 + ~n;

这计算使用n低阶位后剩余的高阶位数.

((x << c)>>c

这将填充高位,其值与符号位相同x.

!(blah ^ x)

这相当于

blah == x

Answer 2

• 在2的补充平台-n上相当于~n + 1.出于这个原因,c = 33 + ~n在这样的平台上实际上相当于c = 32 - n.这c旨在表示int如果n较低位被占用,则在32位值中保留多少个高阶位.

  注意此代码中存在两个平台依赖:2位补码平台,32位int类型.

• 然后((x << c) >> c打算对那些更高阶的位进行符号填充c.符号填充意味着那些x具有0位位置的值n - 1,这些高阶位必须被清零.但是对于x具有1位位置的那些值n - 1,这些高阶位必须用1s 填充.这对于使代码适用于负值非常重要x.

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

• 如上所述,其余的只是与原始值的比较x:!(a ^ b)相当于a == b.如果上述变换没有破坏原始值x那么x确实适合n2的补码表示的低位.