Java使用位運算實現(xiàn)加減乘除詳解
在線OJ: LeetCode 29. 兩數(shù)相除
原題目的要求是不能使用乘法, 除法和取余運算符實現(xiàn)除法.
在本篇博客中把題目要求提高一點, 這里只使用位運算來實現(xiàn), 順便的也就把只使用位運算實現(xiàn)加減乘除實現(xiàn)了.
1 . 實現(xiàn)加法
首先我們需要知道兩數(shù)之和可以是兩個數(shù)位相加和不進位相加之和, 而兩數(shù)進行異或(^)運算其實就是兩個數(shù)對應二進制值的無進位相加.
我們可以把思路可以轉換一下, 把加法用異或替換, 如果我們能夠得到兩個數(shù)相加的二進制進位信息為0, 那么此時的無進位結果就是兩數(shù)相加的最終結果了.
只有二進制無進位信息, 相加的結果; 然后把這個結果加上進位信息, 就是兩個數(shù)相加的最終結果.
抽象一下:
我們要計算 a + b
先算 a ^ b = a' 得到的結果就是無進位相加的結果, 然后我們再得到 a 和 b 相加的進位信息 b’, 那么此時 a + b = a' + b' 就是兩數(shù)之和, 但我們這里是不能用加號, 所以我們需要逐個把進位信息再繼續(xù)疊加 (即讓a’ 和 b’ 再繼續(xù)運算, 得到進位信息和不進位信息…), 直到進位信息為 0 結束.
那么進位信息如何計算?
只有當 a 和 b 的二進制對應位置上都是1, 才會產生進位, 只需要 通過 (a & b) << 1 就可得到進位結果.
所以, 只使用位運算實現(xiàn)加法的代碼如下:
// 不使用算數(shù)運算實現(xiàn)兩數(shù)相加
public static int add (int a, int b) {
// 兩個數(shù)的和等于兩個數(shù)不進位相加和進位相加的和
// a ^ b 得到的就是兩數(shù)不進位相加的和
// (a & b) << 1 得到的就是兩數(shù)只相加進位的值
// 一直循環(huán)至進位值為0計算結束
int sum = a;
while (b != 0) {
sum = a ^ b;
b = (a & b) << 1;
a = sum;
}
return sum;
}2 . 實現(xiàn)減法
兩數(shù)相減, 等價于一個數(shù)加上另一個數(shù)的相反數(shù), 即 a - b = a + (-b), 但這里是不能不能出現(xiàn)減號的, 所以, 可以用加法來模擬一個數(shù)的相反數(shù), 因為 x 的相反數(shù)等于 x 取反再加 1 (~x + 1), 即 add(~x, 1).
所以, 只使用位運算實現(xiàn)減法可以在加法代碼的基礎上進行:
// 計算一個數(shù)字的相反數(shù)
public static int oppNum (int num) {
return add(~num, 1);
}
// 不使用算數(shù)運算實現(xiàn)兩數(shù)相減
public static int minus(int a, int b) {
// a - b 就相當于 a + (-b)
// 一個數(shù)的相反數(shù)等于這個數(shù)取反再加1
return add(a, oppNum(b));
}3 . 實現(xiàn)乘法
看下面計算兩個十進制數(shù)的乘法用的方法是不是很熟悉, 以 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 的答案.
只使用位運算實現(xiàn)乘法的代碼如下:
// 不使用算數(shù)運算實現(xiàn)兩數(shù)相乘
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 . 實現(xiàn)除法
在實現(xiàn)除法的時候, 為了防止溢出, 我們可以先把兩數(shù)轉換成正數(shù)來進行計算; 最后在計算末尾再判斷兩個數(shù)的符號決定是否把由正數(shù)計算出來的結果取其相反數(shù).
假設 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.
所以, 我們實現(xiàn)除法的思路可以轉換成 a 是由幾個 ( b * 2 的某次方) 的結果組成.
所以, 只使用位運算實現(xiàn)除法的核心代碼如下:
// 判斷是不是負數(shù)
public static boolean isNegavit(int num) {
return num < 0;
}
// 這個適用于a和b都不是系統(tǒng)最小值的情況下
public static int div(int a, int b) {
// 這里的除法一定要保證兩個數(shù)都是正數(shù), 如果有負數(shù)在計算邏輯最后加上即可
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 最接近的值, 移動的位數(shù)和上面也是一樣的, 不過要滿足 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) 來實現(xiàn)效果
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的某個次方) 相加得到.
但只有上面的實現(xiàn)還不夠, 這里是有一些特殊情況需要考慮的, 比如在 Java 中, int 類型的系統(tǒng)最小值Integer.MIN_VALUE取相反數(shù)的結果依然是Integer.MIN_VALUE.
所以, 除法的兩個操作數(shù)如果有系統(tǒng)最小值的話需要單獨的進行計算處理.
1.如果兩操作數(shù)都是系統(tǒng)最小值, 結果就是 1;
2.如果只有除數(shù) (b) 為系統(tǒng)最小值, 結果就是 0;
3.如果被除數(shù) (a) 為系統(tǒng)最小值, 除數(shù)為 -1 時, 根據(jù) LeetCode 題目要求, 結果就是Integer.MIN_VALUE / (-1) == Integer.MAX_VALUE;
4.如果被除數(shù) (a) 為系統(tǒng)最小值, 除數(shù)為 -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得到的還是原來值), 也就是沒辦法計算相反數(shù)
public static int divide(int a, int b) {
if (a == Integer.MIN_VALUE && b == Integer.MIN_VALUE) {
// 如果兩數(shù)都是系統(tǒng)最小值
return 1;
} else if (b == Integer.MIN_VALUE){
// 如果除數(shù)為系統(tǒng)最小值
return 0;
} else if (a == Integer.MIN_VALUE) {
// 被除數(shù)為系統(tǒng)最小值
// 且除數(shù)為-1
if (b == oppNum(1)) {
// 答案應該是 Integer.MAX_VALUE + 1 的這個值的, 但力扣系統(tǒng)返回 Integer.MAX_VALUE 就行了
return Integer.MAX_VALUE;
} else {
// 系統(tǒng)最小值沒法取相反數(shù)計算
// 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 {
// 兩數(shù)都不是系統(tǒng)最小值
return div(a, b);
}
}完整實現(xiàn)的代碼如下:
class Solution {
// 不使用算數(shù)運算實現(xiàn)兩數(shù)相加
public static int add (int a, int b) {
// 兩個數(shù)的和等于兩個數(shù)不進位相加和進位相加的和
// a ^ b 得到的就是兩數(shù)不進位相加的和
// (a & b) << 1 得到的就是兩數(shù)只相加進位的值
// 一直循環(huán)至進位值為0計算結束
int sum = a;
while (b != 0) {
sum = a ^ b;
b = (a & b) << 1;
a = sum;
}
return sum;
}
// 計算一個數(shù)字的相反數(shù)
public static int oppNum (int num) {
return add(~num, 1);
}
// 不使用算數(shù)運算實現(xiàn)兩數(shù)相減
public static int minus(int a, int b) {
// a - b 就相當于 a + (-b)
// 一個數(shù)的相反數(shù)等于這個數(shù)取反再加1
return add(a, oppNum(b));
}
// 不使用算數(shù)運算實現(xiàn)兩數(shù)相乘
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;
}
// 不使用算數(shù)運算實現(xiàn)除法
// 判斷是不是負數(shù)
public static boolean isNegavit(int num) {
return num < 0;
}
// 這個適用于a和b都不是系統(tǒng)最小值的情況下
public static int div(int a, int b) {
// 這里的除法一定要保證兩個數(shù)都是正數(shù), 如果有負數(shù)在計算邏輯最后加上即可
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 最接近的值, 移動的位數(shù)和上面也是一樣的, 不過要滿足 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) 來實現(xiàn)效果
return isNegavit(a) != isNegavit(b) ? oppNum(res) : res;
}
// 除法的計算如果有系統(tǒng)最小值需要進行特殊判斷(因為Integer.MAX_VALUE取反再+1得到的還是原來值), 也就是沒辦法計算相反數(shù)
public static int divide(int a, int b) {
if (a == Integer.MIN_VALUE && b == Integer.MIN_VALUE) {
// 如果兩數(shù)都是系統(tǒng)最小值
return 1;
} else if (b == Integer.MIN_VALUE){
// 如果除數(shù)為系統(tǒng)最小值
return 0;
} else if (a == Integer.MIN_VALUE) {
// 被除數(shù)為系統(tǒng)最小值
// 且除數(shù)為-1
if (b == oppNum(1)) {
// 答案應該是 Integer.MAX_VALUE + 1 的這個值的, 但力扣系統(tǒng)返回 Integer.MAX_VALUE 就行了
return Integer.MAX_VALUE;
} else {
// 系統(tǒng)最小值沒法取相反數(shù)計算
// 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 {
// 兩數(shù)都不是系統(tǒng)最小值
return div(a, b);
}
}
}當然, 按照原本的題意, 只是不能使用乘法, 除法和取余運算, 其他可以正常使用, 代碼就簡單了不少, 思路是一樣的, 代碼實現(xiàn)如下:
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) {
// 這里的除法一定要保證兩個數(shù)都是正數(shù), 如果有負數(shù)在計算邏輯最后加上即可
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 最接近的值, 移動的位數(shù)和上面也是一樣的, 不過要滿足 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) 來實現(xiàn)效果
return isNegavit(a) != isNegavit(b) ? oppNum(res) : res;
}
// 除法的計算如果有系統(tǒng)最小值需要進行特殊判斷(因為Integer.MAX_VALUE取反再+1得到的還是原來值), 也就是沒辦法計算相反數(shù)
public static int divide(int a, int b) {
if (a == Integer.MIN_VALUE && b == Integer.MIN_VALUE) {
// 如果兩數(shù)都是系統(tǒng)最小值
return 1;
} else if (b == Integer.MIN_VALUE) {
// 如果除數(shù)為系統(tǒng)最小值
return 0;
} else if (a == Integer.MIN_VALUE) {
// 被除數(shù)為系統(tǒng)最小值
// 且除數(shù)為-1
if (b == -1) {
// 答案應該是 Integer.MAX_VALUE + 1 的這個值的, 但力扣系統(tǒng)返回 Integer.MAX_VALUE 就行了
return Integer.MAX_VALUE;
} else {
// 系統(tǒng)最小值沒法取相反數(shù)計算
// 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 {
// 兩數(shù)都不是系統(tǒng)最小值
return div(a, b);
}
}
}上述代碼都是可以通過OJ的
以上就是Java使用位運算實現(xiàn)加減乘除詳解的詳細內容，更多關于Java位運算的資料請關注腳本之家其它相關文章！
相關文章
大家好，本篇文章主要講的是基于Java實現(xiàn)Avro文件讀寫功能，感興趣的同學趕快來看一看吧，對你有幫助的話記得收藏一下2022-02-02
Spring MVC返回的json去除根節(jié)點名稱的方法
這篇文章主要介紹了Spring MVC返回的json去除根節(jié)點名稱的方法，非常不錯，具有參考借鑒價值,需要的朋友可以參考下2016-09-09
這篇文章主要介紹了springboot集成redis存對象亂碼的問題及解決方案，具有很好的參考價值，希望對大家有所幫助。如有錯誤或未考慮完全的地方，望不吝賜教2022-06-06
同一種類型數(shù)據(jù)的集合。其實數(shù)組就是一個容器。運算的時候有很多數(shù)據(jù)參與運算,那么首先需要做的是什么下面我們就一起來看看。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實現(xiàn)圖片水平和垂直翻轉效果，圖片旋轉的靈活運用，具有一定的參考價值，感興趣的小伙伴們可以參考一下2019-01-01