Java使用位運算實現加減乘除詳解
在線OJ: LeetCode 29. 兩數相除
原題目的要求是不能使用乘法, 除法和取余運算符實現除法.
在本篇博客中把題目要求提高一點, 這里只使用位運算來實現, 順便的也就把只使用位運算實現加減乘除實現了.
1 . 實現加法
首先我們需要知道兩數之和可以是兩個數位相加和不進位相加之和, 而兩數進行異或(^)運算其實就是兩個數對應二進制值的無進位相加.
我們可以把思路可以轉換一下, 把加法用異或替換, 如果我們能夠得到兩個數相加的二進制進位信息為0, 那么此時的無進位結果就是兩數相加的最終結果了.
只有二進制無進位信息, 相加的結果; 然后把這個結果加上進位信息, 就是兩個數相加的最終結果.
抽象一下:
我們要計算 a + b
先算 a ^ b = a' 得到的結果就是無進位相加的結果, 然后我們再得到 a 和 b 相加的進位信息 b’, 那么此時 a + b = a' + b' 就是兩數之和, 但我們這里是不能用加號, 所以我們需要逐個把進位信息再繼續(xù)疊加 (即讓a’ 和 b’ 再繼續(xù)運算, 得到進位信息和不進位信息…), 直到進位信息為 0 結束.
那么進位信息如何計算?
只有當 a 和 b 的二進制對應位置上都是1, 才會產生進位, 只需要 通過 (a & b) << 1 就可得到進位結果.
所以, 只使用位運算實現加法的代碼如下:
// 不使用算數運算實現兩數相加
public static int add (int a, int b) {
// 兩個數的和等于兩個數不進位相加和進位相加的和
// a ^ b 得到的就是兩數不進位相加的和
// (a & b) << 1 得到的就是兩數只相加進位的值
// 一直循環(huán)至進位值為0計算結束
int sum = a;
while (b != 0) {
sum = a ^ b;
b = (a & b) << 1;
a = sum;
}
return sum;
}2 . 實現減法
兩數相減, 等價于一個數加上另一個數的相反數, 即 a - b = a + (-b), 但這里是不能不能出現減號的, 所以, 可以用加法來模擬一個數的相反數, 因為 x 的相反數等于 x 取反再加 1 (~x + 1), 即 add(~x, 1).
所以, 只使用位運算實現減法可以在加法代碼的基礎上進行:
// 計算一個數字的相反數
public static int oppNum (int num) {
return add(~num, 1);
}
// 不使用算數運算實現兩數相減
public static int minus(int a, int b) {
// a - b 就相當于 a + (-b)
// 一個數的相反數等于這個數取反再加1
return add(a, oppNum(b));
}3 . 實現乘法
看下面計算兩個十進制數的乘法用的方法是不是很熟悉, 以 a = 12, b = 22 為例, a * b 通過如下方式計算;
19
x 22
------
38
38
------
418
這樣的方法也適用于二進制, 19 的二進制是 10011, 22 的二進制是 10110, 計算過程如下;
10011
x 10110
-------------
00000
10011
10011
00000
10011
------------
110100010
得到的計算結果 110100010 就是 418.
其實這里的二進制計算就對應著這樣一個過程, 要求 a * b 的結果, 就從右往左開始遍歷 b 的每一位二進制值, 如果 b 的第 i 位是 1, 則把 a 左移 i 位的累值加到結果中; 如果 b 的第 i 位是 0, 不需要處理, 最后累加完的結果就是 a * b 的答案.
只使用位運算實現乘法的代碼如下:
// 不使用算數運算實現兩數相乘
public static int mulit (int a, int b) {
// 就小學手算十進制類似
// 讓 a 的每一位去乘 b 的每一位
int res = 0;
while (b != 0) {
if ((b & 1) != 0) {
res = add(res, a);
}
a <<= 1;
// 要注意 b 必須是無符號右移
b >>>= 1;
}
return res;
}4 . 實現除法
在實現除法的時候, 為了防止溢出, 我們可以先把兩數轉換成正數來進行計算; 最后在計算末尾再判斷兩個數的符號決定是否把由正數計算出來的結果取其相反數.
假設 a / b = c, 則 a = b * c, 使用位運算就需要結合二進制來思考, 這里假設:
a = b * (2^7) + b * (2^4) + b * (2^1), 則 c 的二進制一定是10010010.
抽象一下, 如果a = b * (2 ^ m1) + b * (2 ^ m2) + b * (2 ^ m3), 則 c 的 m1 位置, m2 位置, m3 位置一定是 1, 其他位置都是 0.
所以, 我們實現除法的思路可以轉換成 a 是由幾個 ( b * 2 的某次方) 的結果組成.
所以, 只使用位運算實現除法的核心代碼如下:
// 判斷是不是負數
public static boolean isNegavit(int num) {
return num < 0;
}
// 這個適用于a和b都不是系統(tǒng)最小值的情況下
public static int div(int a, int b) {
// 這里的除法一定要保證兩個數都是正數, 如果有負數在計算邏輯最后加上即可
int x = isNegavit(a) ? oppNum(a) : a;
int y = isNegavit(b) ? oppNum(b) : b;
int res = 0;
// 計算的是 x / y
// 每次循環(huán) y 向左移動到和 x 最接近的值, 但要滿足 y <= x, 如果是這個條件下, 也就是讓 y 左移, 可能會溢出到符號位, 就可能會出錯
// 實際上將 x 向右移動到和 y 最接近的值, 移動的位數和上面也是一樣的, 不過要滿足 x >= y;
for (int i = 30; i >= 0; i = minus(i, 1)) {
if ((x >> i) >= y) {
// 這個比特位一定是1
res |= (1 << i);
// x 減去 y << i;
x = minus(x, y << i);
}
}
// isNegavit(a) != isNegavit(b) 這個也可以用 isNegavit(a) ^ isNegavit(b) 來實現效果
return isNegavit(a) != isNegavit(b) ? oppNum(res) : res;
}其中
if ((x >> i) >= y) {
// 這個比特位一定是1
res |= (1 << i);
// x 減去 y << i;
x = minus(x, y << i);
}就是讓 a 不斷嘗試其值是否由 (b * 2的某個次方) 相加得到.
但只有上面的實現還不夠, 這里是有一些特殊情況需要考慮的, 比如在 Java 中, int 類型的系統(tǒng)最小值Integer.MIN_VALUE取相反數的結果依然是Integer.MIN_VALUE.
所以, 除法的兩個操作數如果有系統(tǒng)最小值的話需要單獨的進行計算處理.
1.如果兩操作數都是系統(tǒng)最小值, 結果就是 1;
2.如果只有除數 (b) 為系統(tǒng)最小值, 結果就是 0;
3.如果被除數 (a) 為系統(tǒng)最小值, 除數為 -1 時, 根據 LeetCode 題目要求, 結果就是Integer.MIN_VALUE / (-1) == Integer.MAX_VALUE;
4.如果被除數 (a) 為系統(tǒng)最小值, 除數為 -1 和 Integer.MIN_VALUE時 (即a = Integer.MIN_VALUE且b != -1 && b != Integer.MIN_VALUE), a / b應該通過如下方式來計算;
- 可以先讓先讓系統(tǒng)最小值 +1 (a + 1), 此時就可以按照正常上面的正常流程去計算除法了, 即(a + 1) / b = c.
- 接著計算a - (b * c) = d, 得到由于 a + 1 少/多算的.
- 然后d / b = e
- 最后將 c 和 e 相加就得到了 a / b 的值, c + e = ((a + 1)/b) + ((a - (b * c)) / b) = a / b
除了這些特殊, 就是正常的流程了, 所以, 加上針對系統(tǒng)最小值的特殊判斷的代碼如下:
// 除法的計算如果有系統(tǒng)最小值需要進行特殊判斷(因為Integer.MAX_VALUE取反再+1得到的還是原來值), 也就是沒辦法計算相反數
public static int divide(int a, int b) {
if (a == Integer.MIN_VALUE && b == Integer.MIN_VALUE) {
// 如果兩數都是系統(tǒng)最小值
return 1;
} else if (b == Integer.MIN_VALUE){
// 如果除數為系統(tǒng)最小值
return 0;
} else if (a == Integer.MIN_VALUE) {
// 被除數為系統(tǒng)最小值
// 且除數為-1
if (b == oppNum(1)) {
// 答案應該是 Integer.MAX_VALUE + 1 的這個值的, 但力扣系統(tǒng)返回 Integer.MAX_VALUE 就行了
return Integer.MAX_VALUE;
} else {
// 系統(tǒng)最小值沒法取相反數計算
// 1. c = (Integer.MAX_VALUE + 1) / b , 先讓系統(tǒng)最小值 +1 后再除以 b
// 2. (Integer.MAX_VALUE - c * b) / b
// 3. 再將 1 和 2 的結果相加節(jié)課
int c = div(add(a, 1), b);
return add(c, div(minus(a, mulit(c, b)), b));
}
} else {
// 兩數都不是系統(tǒng)最小值
return div(a, b);
}
}完整實現的代碼如下:
class Solution {
// 不使用算數運算實現兩數相加
public static int add (int a, int b) {
// 兩個數的和等于兩個數不進位相加和進位相加的和
// a ^ b 得到的就是兩數不進位相加的和
// (a & b) << 1 得到的就是兩數只相加進位的值
// 一直循環(huán)至進位值為0計算結束
int sum = a;
while (b != 0) {
sum = a ^ b;
b = (a & b) << 1;
a = sum;
}
return sum;
}
// 計算一個數字的相反數
public static int oppNum (int num) {
return add(~num, 1);
}
// 不使用算數運算實現兩數相減
public static int minus(int a, int b) {
// a - b 就相當于 a + (-b)
// 一個數的相反數等于這個數取反再加1
return add(a, oppNum(b));
}
// 不使用算數運算實現兩數相乘
public static int mulit (int a, int b) {
// 就和小學手算十進制類似
// 讓 a 的每一位去乘 b 的每一位
int res = 0;
while (b != 0) {
if ((b & 1) != 0) {
res = add(res, a);
}
a <<= 1;
// 要注意 b 必須是無符號右移
b >>>= 1;
}
return res;
}
// 不使用算數運算實現除法
// 判斷是不是負數
public static boolean isNegavit(int num) {
return num < 0;
}
// 這個適用于a和b都不是系統(tǒng)最小值的情況下
public static int div(int a, int b) {
// 這里的除法一定要保證兩個數都是正數, 如果有負數在計算邏輯最后加上即可
int x = isNegavit(a) ? oppNum(a) : a;
int y = isNegavit(b) ? oppNum(b) : b;
int res = 0;
// 計算的是 x / y
// 每次循環(huán) y 向左移動到和 x 最接近的值, 但要滿足 y <= x, 如果是這個條件下, 也就是讓 y 左移, 可能會溢出到符號位, 就可能會出錯
// 實際上將 x 向右移動到和 y 最接近的值, 移動的位數和上面也是一樣的, 不過要滿足 x >= y;
for (int i = 30; i >= 0; i = minus(i, 1)) {
if ((x >> i) >= y) {
// 這個比特位一定是1
res |= (1 << i);
// x 減去 y << i;
x = minus(x, y << i);
}
}
// isNegavit(a) != isNegavit(b) 這個也可以用 isNegavit(a) ^ isNegavit(b) 來實現效果
return isNegavit(a) != isNegavit(b) ? oppNum(res) : res;
}
// 除法的計算如果有系統(tǒng)最小值需要進行特殊判斷(因為Integer.MAX_VALUE取反再+1得到的還是原來值), 也就是沒辦法計算相反數
public static int divide(int a, int b) {
if (a == Integer.MIN_VALUE && b == Integer.MIN_VALUE) {
// 如果兩數都是系統(tǒng)最小值
return 1;
} else if (b == Integer.MIN_VALUE){
// 如果除數為系統(tǒng)最小值
return 0;
} else if (a == Integer.MIN_VALUE) {
// 被除數為系統(tǒng)最小值
// 且除數為-1
if (b == oppNum(1)) {
// 答案應該是 Integer.MAX_VALUE + 1 的這個值的, 但力扣系統(tǒng)返回 Integer.MAX_VALUE 就行了
return Integer.MAX_VALUE;
} else {
// 系統(tǒng)最小值沒法取相反數計算
// 1. c = (Integer.MAX_VALUE + 1) / b , 先讓系統(tǒng)最小值 +1 后再除以 b
// 2. (Integer.MAX_VALUE - c * b) / b
// 3. 再將 1 和 2 的結果相加節(jié)課
int c = div(add(a, 1), b);
return add(c, div(minus(a, mulit(c, b)), b));
}
} else {
// 兩數都不是系統(tǒng)最小值
return div(a, b);
}
}
}當然, 按照原本的題意, 只是不能使用乘法, 除法和取余運算, 其他可以正常使用, 代碼就簡單了不少, 思路是一樣的, 代碼實現如下:
class Solution29 {
public static boolean isNegavit(int num) {
return num < 0;
}
public static int oppNum (int num) {
return (~num) + 1;
}
public static int mulit (int a, int b) {
// 就和小學手算十進制類似
// 讓 a 的每一位去乘 b 的每一位
int res = 0;
while (b != 0) {
if ((b & 1) != 0) {
res += a;
}
a <<= 1;
// 要注意 b 必須是無符號右移
b >>>= 1;
}
return res;
}
public static int div(int a, int b) {
// 這里的除法一定要保證兩個數都是正數, 如果有負數在計算邏輯最后加上即可
int x = isNegavit(a) ? oppNum(a) : a;
int y = isNegavit(b) ? oppNum(b) : b;
int res = 0;
// 計算的是 x / y
// 每次循環(huán) y 向左移動到和 x 最接近的值, 但要滿足 y <= x, 如果是這個條件下, 也就是讓 y 左移, 可能會溢出到符號位, 就可能會出錯
// 實際上將 x 向右移動到和 y 最接近的值, 移動的位數和上面也是一樣的, 不過要滿足 x >= y;
for (int i = 30; i >= 0; i--) {
if ((x >> i) >= y) {
// 這個比特位一定是1
res |= (1 << i);
// x 減去 y << i;
x -= (y << i);
}
}
// isNegavit(a) != isNegavit(b) 這個也可以用 isNegavit(a) ^ isNegavit(b) 來實現效果
return isNegavit(a) != isNegavit(b) ? oppNum(res) : res;
}
// 除法的計算如果有系統(tǒng)最小值需要進行特殊判斷(因為Integer.MAX_VALUE取反再+1得到的還是原來值), 也就是沒辦法計算相反數
public static int divide(int a, int b) {
if (a == Integer.MIN_VALUE && b == Integer.MIN_VALUE) {
// 如果兩數都是系統(tǒng)最小值
return 1;
} else if (b == Integer.MIN_VALUE) {
// 如果除數為系統(tǒng)最小值
return 0;
} else if (a == Integer.MIN_VALUE) {
// 被除數為系統(tǒng)最小值
// 且除數為-1
if (b == -1) {
// 答案應該是 Integer.MAX_VALUE + 1 的這個值的, 但力扣系統(tǒng)返回 Integer.MAX_VALUE 就行了
return Integer.MAX_VALUE;
} else {
// 系統(tǒng)最小值沒法取相反數計算
// 1. c = (Integer.MAX_VALUE + 1) / b , 先讓系統(tǒng)最小值 +1 后再除以 b
// 2. (Integer.MAX_VALUE - c * b) / b
// 3. 再將 1 和 2 的結果相加節(jié)課
int c = div(a + 1, b);
return c + ((a - mulit(c, b)) / b);
}
} else {
// 兩數都不是系統(tǒng)最小值
return div(a, b);
}
}
}上述代碼都是可以通過OJ的
以上就是Java使用位運算實現加減乘除詳解的詳細內容，更多關于Java位運算的資料請關注腳本之家其它相關文章！
相關文章
大家好，本篇文章主要講的是基于Java實現Avro文件讀寫功能，感興趣的同學趕快來看一看吧，對你有幫助的話記得收藏一下2022-02-02
Spring MVC返回的json去除根節(jié)點名稱的方法
這篇文章主要介紹了Spring MVC返回的json去除根節(jié)點名稱的方法，非常不錯，具有參考借鑒價值,需要的朋友可以參考下2016-09-09
這篇文章主要介紹了springboot集成redis存對象亂碼的問題及解決方案，具有很好的參考價值，希望對大家有所幫助。如有錯誤或未考慮完全的地方，望不吝賜教2022-06-06
同一種類型數據的集合。其實數組就是一個容器。運算的時候有很多數據參與運算,那么首先需要做的是什么下面我們就一起來看看。2016-07-07
這篇文章主要介紹了Spring depends-on的使用，具有很好的參考價值，希望對大家有所幫助。如有錯誤或未考慮完全的地方，望不吝賜教2021-07-07
springboot的http.server.requests服務請求流程源碼
這篇文章主要為大家介紹了springboot的http.server.requests服務請求流程源碼,有需要的朋友可以借鑒參考下,希望能夠有所幫助,祝大家多多進步,早日升職加薪2023-12-12
本文給大家介紹的是java中的文本框和文本區(qū)的概念和使用方法，以及簡單的示例，十分實用，有需要的小伙伴可以參考下。2015-06-06
這篇文章主要介紹了JavaFX 監(jiān)聽窗口關閉事件實例詳解的相關資料,需要的朋友可以參考下2017-05-05
這篇文章主要給大家介紹了關于MyBatis使用Map與模糊查詢的相關資料，文中通過示例代碼介紹的非常詳細，對大家的學習或者工作具有一定的參考學習價值，需要的朋友們下面隨著小編來一起學習學習吧2021-05-05
這篇文章主要為大家詳細介紹了java實現圖片水平和垂直翻轉效果，圖片旋轉的靈活運用，具有一定的參考價值，感興趣的小伙伴們可以參考一下2019-01-01