前言

Leetcode中有一道這樣的題:給定兩個整數，被除數 dividend 和除數 divisor。將兩數相除，要求不使用乘法、除法和 mod 運算符。返回被除數 dividend 除以除數 divisor 得到的商。
如果正常的四則運算符號不允許使用，呢這道題的考點我覺得應該是位運算來實現，遇到了就好好復習一下，下面將介紹二進制實現四則運算:

二進制碼

位運算是基于二進制運算的，實際上目前的計算機都只識別二進制碼，我們所寫的一切指令事實上都是一串010101數字、傳輸數據也是按比特流的形式傳輸的。所以先介紹二進制碼:

原碼

最高位表示符號位（0代表正數，1代表負數）。剩下的位數，是這個數的絕對值的二進制。
比如 一個int變量大小為4字節，在32位的編譯器中的二進制表示就是00000000 00000000 00000000 0000000

10 的原碼 00000000 00000000 00000000 00001010 ?10的原碼 10000000 00000000 00000000 00001010

反碼

正數的反碼和其原碼是一樣的
負數的反碼就是在其原碼的基礎上 符號位不變 其他位取反。

10的反碼： 00000000 00000000 00000000 00001010 ?10的反碼：11111111 11111111 11111111 11110101

補碼

正數的補碼就是其原碼
負數的補碼就是在其反碼的基礎上+1

10的補碼：00000000 00000000 0000000 00001010 ?10的補碼：11111111 11111111 11111111 11110110

在計算機系統中，數值一律用補碼來表示:因為補碼可以是符號位和數值位統一處理，同時可以試減法按照加法來處理。

位運算加法

0111 ^ 0101 = 0010; //結果的每一位等于對應位相加模二，剛好是不帶進位的加法結果。 0111 & 0101 = 0101; //結果的1表示對應位相加為2，0表示對應位相加小于二，剛好是進位標識。

所以有:

int add(int a, int b) {return (b == 0) ? a : add(a^b, (a&b) << 1); }

位運算減法

減法其實就是加上這個數的相反數，這個數原來是用正數的補碼表示的，現在變成負數的補碼形式了:所以只需要將這個數每一位取反再末尾家一就行了:

int subtraction(int a, int b) {b = add(~b, 1);return add(a, b); }

位運算乘法

對于a * b，每次只需要將a左移一位乘上b的對應位，然后同上一次的結果做加法即可。
當b的對應位為1時，對a左移一位然后同上一次的結果做加法;如果b的對應位為0，只對a左移一位。

int getsign(int n) {return n >> 31; }int positive(int n) {return (getsign(n) & 1) ? add(~n,1): n; }int multiply(int a, int b) {bool flag = (getsign(a) ^ getsign(b)) ? 1 : 0;a = positive(a);b = positive(b);int res = 0;while (b) {if (b & 1)res = add(res, a); //只有當前b末尾為1時才運算a = a << 1; b = b >> 1;}if (flag)add(~res, 1);return res; }

位運算除法

同乘法一樣，除法也可以進行二進制筆算，以a / b為例，只有當a >= b時才可以上商，又因為是二進制，所以商每次只會多1，在每次上1之后a都要減去一次b。

int divide(int a, int b) {if (b == 0)throw runtime_error("DIVIDED CANNOT BE 0");bool flag = (getsign(a) ^ getsign(b)) ? 1 : 0;a = positive(a);b = positive(b);int res = 0;while (a >= b){res = add(res, 1);a = subtraction(a, b);}return flag ? add(~res, 1) : res; }

總代碼如下:

int add(int a, int b) {return (b == 0) ? a : add(a^b, (a&b) << 1); }int subtraction(int a, int b) {b = add(~b, 1);return add(a, b); }int getsign(int n) {return n >> 31; }int positive(int n) {return (getsign(n) & 1) ? add(~n,1): n; }int multiply(int a, int b) {bool flag = (getsign(a) ^ getsign(b)) ? 1 : 0;a = positive(a);b = positive(b);int res = 0;while (b) {if (b & 1)res = add(res, a); //只有當前b末尾為1時才運算a = a << 1; b = b >> 1;}if (flag)add(~res, 1);return res; }int divide(int a, int b) {if (b == 0)throw runtime_error("DIVIDED CANNOT BE 0");bool flag = (getsign(a) ^ getsign(b)) ? 1 : 0;a = positive(a);b = positive(b);int res = 0;while (a >= b){res = add(res, 1);a = subtraction(a, b);}return flag ? add(~res, 1) : res; }

轉載于:https://www.cnblogs.com/yunlambert/p/9845897.html

創作挑戰賽新人創作獎勵來咯，堅持創作打卡瓜分現金大獎

總結

以上是生活随笔為你收集整理的位运算实现四则运算(C++实现)的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。