前文

一道算法題，涉及到了二進制的位操作，借這個機會整理一下相關(guān)的知識點，并且在這道算法題中進行了實踐

本文的解法來自于該算法題的一篇討論。

---

一、算法題介紹

對除數(shù)和被除數(shù)實現(xiàn)除法運算，其中不使用乘法、除法和求余操作，返回對應(yīng)的商。如，
Input: dividend = 10, divisor = 3
Output: 3

解法1：暴力解法

class Solution {public int divide(int dividend, int divisor){//定義除法，被除數(shù)是最小值，除以-1時，是最大值if(dividend == Integer.MIN_VALUE && divisor == -1)return Integer.MAX_VALUE;//^運算符，只有不同時，才為true ; sign定義商是否為負數(shù) int sign = (dividend < 0) ^ (divisor < 0) ? -1 : 1;int result = 0;//取除數(shù)和被除數(shù)的正數(shù)形式long x = Math.abs((long)dividend);long y = Math.abs((long)divisor);//統(tǒng)計被除數(shù)共減去多少個除數(shù)，即為商while(x >= y){x -= y;result++;}return sign > 0 ? result : -result;} } 復(fù)制代碼

暴力解法主要是通過不斷循環(huán)將y（除數(shù)）從x（被除數(shù)）中減去，直到x<y. x減去y的次數(shù)就是商，而最后剩下的小于y的部分就是余數(shù)。暴力解法的時間復(fù)雜度很高，比如說，當(dāng)x=2³¹-1,y=1時，需要循環(huán)2³¹-1次。

• 時間復(fù)雜度：O(x),x是被除數(shù)。
• 空間復(fù)雜度：O(1)。

解法2：除數(shù)左移位累加

class Solution {public int divide(int dividend, int divisor){if(dividend == Integer.MIN_VALUE && divisor == -1)return Integer.MAX_VALUE;int sign = (dividend < 0) ^ (divisor < 0) ? -1 : 1;int result = 0;long x = Math.abs((long)dividend);long y = Math.abs((long)divisor);while(x >= y){int shift = 1;//將y持續(xù)向左移位，相當(dāng)于y*2^(shift);//當(dāng)y*2^(shift)< x <y*2^(shift+1)時，循環(huán)結(jié)束while(x >= (y << shift)){shift++;}x -= y << (shift - 1);//相當(dāng)于x = y*2^(shift)+y*2^(shift-n)+.....+y*2^(0) + m;m是余數(shù)result += 1 << (shift - 1);}return sign > 0 ? result : -result;} } 復(fù)制代碼

這個方法，是計算最大的k,使得y*2^k<=x，然后將y*2^k從x中減去，將2^k加到商里面。比如說， 如果x= (1011)₂，y=(10)₂，那么因為2*2²<= 11而且2*2³>11 所以k=2。所以，我們將 (1011)₂減去 (1000)₂得到 (11)₂，然后，將2^k=2²=(100)₂加到商中，然后將x更新為(11)₂繼續(xù)運算。

使用y*2^k的優(yōu)勢在于，可以使用非常高效的移位操作，而且每次循環(huán)后，最差的情況下，x都會變?yōu)樵瓉淼囊话?。如果n是x/y的商的位數(shù)，那么總共需要n次循環(huán)。子循環(huán)中每次通過循環(huán)k次來找到y(tǒng)*2^k的最大的k，因此：

• 時間復(fù)雜度：O(n²),n是x/y的商的位數(shù)。
• 空間復(fù)雜度：O(1)。

解法3：除數(shù)左移位遞減

class Solution {public int divide(int dividend, int divisor){if(dividend == Integer.MIN_VALUE && divisor == -1)return Integer.MAX_VALUE;int sign = (dividend < 0) ^ (divisor < 0) ? -1 : 1;int result = 0;int power = 32;//long是8字節(jié)，64位；int是4字節(jié)，32位long x = Math.abs((long)dividend);long y = Math.abs((long)divisor);while(x >= y){//將y*2^32增加到最大，然后逐步減小，靠近x//y*2^power<x時結(jié)束while((y << power) > x){//每次只需要執(zhí)行有限步就能找到power，不像前面中的方法，是執(zhí)行O(n)步才能找到power--;}x -= y << power;result += 1 << power;}return sign > 0 ? result : -result;} } 復(fù)制代碼

1.在每次循環(huán)中找到最大的k的最好的方式就是認識到k其實是在不斷縮小的。因此，我們不需要在每次子循環(huán)的時候都檢驗一下2¹，2²，2³......是否小于或者等于x，我們可以在找到最大的k后，直接在后面的每次循環(huán)中檢驗x和2^k-1，2^k-2，2^k-3....的關(guān)系。
2. 我們可以繼續(xù)之前的例子。商為(100)₂后，我們繼續(xù)計算(11)₂。因為y*2^k<=x的最大k是0，所以我們把2⁰=(1)₂加到商里，因此商就變成了(101)₂。然后我們繼續(xù)算法，因此(1)₂<y，所以算法結(jié)束。最后，我們可以得到，x= (1011)₂，y=(10)₂相除，商為(101)₂，余數(shù)為(1)₂。

• 時間復(fù)雜度：O(n),n是x/y的商的位數(shù)。
• 空間復(fù)雜度：O(1)

總結(jié)

以上是生活随笔為你收集整理的实现除法操作的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。