按位余数运算符

Question

我一直在弄乱我在互联网上发现的按位运算符问题，并发现一个只是完全残留下来的问题。

int rpwr2(int x, int n) 
{ 
    //Legal ops: ! ~^| + << >> 

    //My attempt at a solution: 
    int power = (1 << n) + ~0; 
    return x & power; 
} 

Answer 1

harold的suggestion几乎是正确的，但不是-result，负x，我们需要

result - (1 << n) 

除非结果为0。2的补

x & ((1 << n) - 1) 

是x模2^n每x（和n小到足以让1 << n正常工作）。这是x的残差类别[0, 2^n)的代表。

要求是为负数x获得负数（非正数，更确切的）余数（在区间(-2^n, 0]中）。这意味着，对于不是2^n的倍数的负数x，我们必须从x & ((1 << n) - 1)减去2^n。

int rempwr2(int x, int n) 
{ 
    //Compute x%(2^n) for 0 <= n <= 30. 
    //Negative arguments should yield a negative remainder. 
    //Examples: rempwr2(15, 2) = 3; rempwr2(-35, 3) = -3; 
    //Legal ops: ! ~^| + << >> 

    //My attempt at a solution: 
    int power = (1 << n) + ~0; // 2^n - 1 
    int mask = x >> 31; 
    int result = x & power; 
    return (x & power) + (((~((!!result) << n)) + 1) & mask); 
} 

如果x >= 0，然后mask = 0和(x & power) + (whatever & mask) = (x & power)是正确的结果。

对于x < 0，我们必须减去1 << n，除非result = 0。

(!!result) << n 

是0，如果是x的2^n，并2^n多否则。由于直接相减是不允许的，我们必须否定的是（以二的补-n = ~n + 1），所以我们发现

(~((!!result) << n)) + 1 

仍然是0，如果result = 0，并-2^n否则，因此这是我们必须添加负x。但是，对于正数x，这也可以是非零值，因此在这种情况下我们必须使其无效，我们通过按位并使用mask（对于x >= 0为0，并将所有位设置为x < 0）来做到这一点。