c - 位余数运算符

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的建议几乎是正确的，但是-result对于否定x，我们需要代替 ,

result - (1 << n)

除非结果为 0。在二进制补码中，

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

与每个x模数一致（并且足够小以正常工作）。那是区间中的残差类的代表。2^nxn1 << nx[0, 2^n)

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

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

如果x是 的倍数，则为 0 2^n，2^n否则为 0。由于不允许直接减法，我们必须否定它（-n = ~n + 1在二进制补码中），所以我们发现

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

如果 ，则仍然为 0 result = 0，-2^n否则，这就是我们必须为负添加的内容x。但这也可以是 positive 的非零值x，因此我们必须在这种情况下将其无效，我们通过按位和 with 来mask实现（它是 0x >= 0并且所有位都设置为x < 0）。