除以2的冪的有符號整數

Question

我正在使用僅使用二元運算符的方式來劃分2的冪整數的有符號整數（< < >> + ^〜& |！），並且結果具有要繞到0.我也遇到了關於這個問題的Stackoverflow上的this question，但是，我不明白它爲什麼起作用。這裏的解決方案：

int divideByPowerOf2(int x, int n) 
{ 
    return (x + ((x >> 31) & ((1 << n) + ~0))) >> n; 
} 

我明白x >> 31部分（只添加下一個部分，如果x是負的，因爲如果它的正面x會自動向輪0）。但困擾我的是(1 << n) + ~0部分。它如何工作？

Answer 1

假設2補，只是比特移位被除數相當於某種分裂的：不是常規除法在這裏我們舍被除數向零除數的一個倍數。但是另一種我們將紅利轉向負無窮的方式。我在Smalltalk中重新發現了這個，見http://smallissimo.blogspot.fr/2015/03/is-bitshift-equivalent-to-division-in.html。

例如，讓我們提高8分-126傳統上，我們會寫

-126 = -15 * 8 - 6 

但是，如果我們對輪無窮，我們得到了一個積極的其餘部分，寫：

-126 = -16 * 8 + 2 

的根據位模式（假設8位長int爲了縮短），位移位正在執行第二操作：

1000|0010 >> 3 = 1111|0000 
1000|0010  = 1111|0000 * 0000|1000 + 0000|0010 

那麼，如果我們希望傳統的除法與商數四捨五入爲零並且餘數與紅利相同？簡單來說，我們只需要向商加1就可以了 - 當且僅當分紅是負數且分割不準確。

您看到x>>31對應於第一個條件，除數爲負數，假設int有32位。

第二項對應於第二個條件，如果劃分不精確。

看看如何在兩個補碼：1111 | 1111，1111 | 1110，1111 | 1100中編碼-1，-2，-4，...。所以二的n次方的否定有n個尾隨零。

當股利有n個尾隨零並且除以2^n時，則不需要將1加到最終的商。在任何其他情況下，我們需要添加1.

什麼（（1 < < n）+〜0）正在創建一個具有n個尾隨符的掩碼。

最後n位並不重要，因爲我們要轉移到右邊並將它們扔掉。所以，如果這個劃分是準確的，那麼n個被除數的尾部位是零，並且我們只添加將被跳過的n 1。相反，如果除法不精確，那麼被除數的n個尾隨位中的一個或多個爲1，並且我們肯定會導致進位到n + 1位位置：這就是我們如何給商加1（我們增加2^n的股息）。這是否解釋更多一點？

Answer 2

這是「只寫代碼」：不是試圖理解代碼，而是嘗試自己創建代碼。

例如，我們將一個數字除以8（右移3）。 如果數字是負數，則正常的右移將以錯誤的方向進行。讓我們加入了一些「固定」它：

int divideBy8(int x) 
{ 
    if (x >= 0) 
     return x >> 3; 
    else 
     return (x + whatever) >> 3; 
} 

在這裏，你能拿出一個數學公式whatever，或者做一些試驗和錯誤。無論如何，這裏whatever = 7：

int divideBy8(int x) 
{ 
    if (x >= 0) 
     return x >> 3; 
    else 
     return (x + 7) >> 3; 
} 

如何統一兩種情況？你需要看起來像這樣的表達式：

(x + stuff) >> 3 

其中stuff是7負x和0正x。特技這裏使用x >> 31，這是一個32位的數字，其位等於的x符號位：全0或全1。所以stuff是

(x >> 31) & 7 

結合所有這些，以及替換8和7通過2的更一般的權力，你得到你問的代碼。

---

注：在上面的描述中，我假定int表示32位硬件寄存器，以及硬件使用二的補碼錶示，以做右移。

Answer 3

OP的參考文獻是C#代碼，所以很多細微的差異導致它成爲錯誤的代碼與C，因爲這篇文章被標記。

int不一定是32位，所以使用32的幻數不能提供一個可靠的解決方案。

尤其是(1 << n) + ~0導致執行定義的行爲，當n導致一位移入標誌位。不好的編碼。

限制代碼只能用「二進制」運營商<< >> +^~ & | !鼓勵一個用於編碼承擔約int東西是不可移植的，也不符合與C規格。因此，OP的發佈代碼通常不「工作」，儘管可能在許多常見的實現中起作用。

當int不是2的補碼時，不使用範圍[-2147483648 .. 2147483647]或當1 << n使用不符合預期的實現行爲時，OP代碼失敗。

// weak code 
int divideByPowerOf2(int x, int n) { 
    return (x + ((x >> 31) & ((1 << n) + ~0))) >> n; 
} 

一個簡單的替代方案中，假設long long超過int的範圍如下。我懷疑這是否符合OP的目標的一些一些的角落，但OP給出的目標鼓勵非魯棒編碼。

int divideByPowerOf2(int x, int n) { 
    long long ill = x; 
    if (x < 0) ill = -ill; 
    while (n--) ill >>= 1; 
    if (x < 0) ill = -ill; 
    return (int) ill; 
}