一、加法
a+b
举例实现:13+9=22
13+9不考虑进位结果为12
只考虑进位结果为10
和刚好是22。
13二进制为1101,9二进制为1001。
不考虑进位结果为0100。算式为a^b
只考虑进位结果为10010。算式为(a&b)<< 1
然后它俩继续进行运算,直到进位为0。
算法实现:
1 //两种方式:
2 //1、递归形式实现
3 int add(int a ,int b){
4 if (b == 0)
5 return a;
6 else{
7 //进位值
8 int carry = (a & b) << 1;
9 a = a ^b;
10 return add(a,carry);
11 }
12 }
13
14 //非递归形式实现
15 int add2(int a ,int b){
16 //进位值
17 int carry;
18 while (b != 0){
19 carry = (a & b) << 1;
20 a = a ^b;
21 b = carry;
22 }
23 return a;
24 }
二、减法
a-b
先来证明一个等式。Java负数存储是以补码形式存储的(补码=反码+1)。所以反码=补码-1.即~n=-n-1=-(n+1)
所以a-b可以化简为a+(-b)=a+~b+1
算法实现:
1 //减法实现 a+(-b)=a+~b+1
2 int subtraction(int a ,int b){
3 b = ~b+1;
4 return this.add(a,b);
5 }
三、乘法
a*b
举例说明:
可以看到,二进制乘法的原理是:从乘数的低位到高位,遇到1并且这个1在乘数的右起第i(i从0开始数)位,那么就把被乘数左移i位得到 temp_i 。直到乘数中的1遍历完后,把根据各位1而得到的被乘数的左移值们 temp_i 相加起来即得乘法结果。那么根据这个原理,可以得到实现代码:这里要点为:用i记录当前遍历的乘数位,当前位为1则被乘数左移i位并加到和中,同时i++处理下一位;为0则乘数右移,i++,处理下一位......直到乘数==0说明乘数中的1遍历完了。此时把和返回即可。
算法实现:
1 //乘法实现
2 //a 被乘数,b 乘数
3 int multiplication(int a,int b){
4 int i = 0;
5 int res = 0;
6 //乘数不为0
7 while (b != 0){
8 //处理当前位
9 //当前位是1
10 if ((b & 1) == 1){
11 res += (a << i);
12 b = b >> 1;
13 //记录当前是第几位
14 i++;
15 }else {
16 //当前位是0
17 b = b >> 1;
18 i++;
19 }
20 }
21 return res;
22 }
四、除法
a/b
除法的意义就在于:求a可以由多少个b组成。那么由此我们可得除法的实现:求a能减去多少个b,做减法的次数就是除法的商。
1 //除法实现
2 int division(int a,int b){
3 int res;
4 if(a<b){
5 return 0;
6 }else{
7 res=division(subtraction(a, b), b)+1;
8 }
9 return res;
10 }
五、测试用例
1 package bitOperation;
2
3 /**
4 * @author zsh
5 * @company wlgzs
6 * @create 2019-02-15 9:46
7 * @Describe 位运算实现加减乘除操作
8 */
9 public class Test {
10 //两种方式:
11 //1、递归形式实现
12 int add(int a ,int b){
13 if (b == 0)
14 return a;
15 else{
16 //进位值
17 int carry = (a & b) << 1;
18 a = a ^b;
19 return add(a,carry);
20 }
21 }
22
23 //非递归形式实现
24 int add2(int a ,int b){
25 //进位值
26 int carry;
27 while (b != 0){
28 carry = (a & b) << 1;
29 a = a ^b;
30 b = carry;
31 }
32 return a;
33 }
34
35 //减法实现 a+(-b)=a+~b+1
36 int subtraction(int a ,int b){
37 b = ~b+1;
38 return this.add(a,b);
39 }
40
41 //乘法实现
42 //a 被乘数,b 乘数
43 int multiplication(int a,int b){
44 int i = 0;
45 int res = 0;
46 //乘数不为0
47 while (b != 0){
48 //处理当前位
49 //当前位是1
50 if ((b & 1) == 1){
51 res += (a << i);
52 b = b >> 1;
53 //记录当前是第几位
54 i++;
55 }else {
56 //当前位是0
57 b = b >> 1;
58 i++;
59 }
60 }
61 return res;
62 }
63
64 //除法实现
65 int division(int a,int b){
66 int res;
67 if(a<b){
68 return 0;
69 }else{
70 res=division(subtraction(a, b), b)+1;
71 }
72 return res;
73 }
74
75 public static void main(String[] args) {
76 System.out.println(new Test().add(100,8));
77 System.out.println(new Test().subtraction(100,8));
78 System.out.println(new Test().multiplication(-3,3));
79 System.out.println(new Test().division(100,3));
80 }
81 }