按位餘數運算符

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）來做到這一點。