计算机内部实现数据的加减乘除运算是通过对二进制位运算来实现的，基本运算" + - × ÷ " 均可转换为位运算。
在介绍加减乘除运算前，我们需要了解一些基本的位运算。
与 &
1 and 1 = 1
1 and 0 = 0
0 and 1 = 0
0 and 0 = 0
或 |
1 or 1 = 1
1 or 0 = 1
0 or 1 = 1
0 or 0 = 0
异或 ^
1 xor 1 = 0
1 xor 0 = 1
0 xor 1 = 1
0 xor 0 = 0
加法运算
假如右两个32位的int整数：
a=10: 00000000000000000000000000001010
b=13: 00000000000000000000000000001101
将这两个数10和13相加：
a=01010 (10)
b=01101 (13)
c=10111 (23)
把上面的二进制分割为每一位后a+b=c
| a |
b |
xor ^ |
and & |
c |
| 0 |
1 |
1 |
0 |
1 |
| 1 |
0 |
1 |
0 |
1 |
| 0 |
1 |
1 |
0 |
1 |
| 1 |
1 |
0 |
1 |
0 |
| 0 |
0 |
0 |
0 |
1 |
我们发现 位异或^ 单纯的将两个数相加，不过并没有考虑 进位 )，但是 与运算& 能够表示两个二进制相加是否发生了进位（如上表所示）。
也就是说，利用 xor 将两个数相加，and 判断是否有进位，如果有，那个满2进1位 carry<<=1
sum = a^b
carry = a&b
carry <<= 1
假如这样计算会发生什么?
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
| add(a,b)
a=01010
b=01101
sum=a^b => 00111
carry=a&b => 01000
carry=carry<<1 => 10000
如果carry进位!=0,否则就结束
假设
a=sum= 00111
b=carry=10000
重复之前的步骤...此时新的a=sum,b=carry
sum=a^b => 10111
carry=a&b => 00000
carry=carry<<1 => 00000
此时sum=10111 且 carry=0
结果正确！
|
sum=a^b 表明对a和b求和（不考虑进位），而 (a&b)<<1 表明求a和b中哪个位发生了进位，并且将该位置于最高位(通过左移一位)
因此C++代码如下:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
|
int add(int a,int b){
int sum=0;
int carry=0;
do
{
sum=a^b;
carry=(a&b)<<1;
a=sum;
b=carry;
} while (carry);
return sum;
}
int add(int a,int b){
int sum=a;
int carry=b;
while (carry){
int temp=sum;
sum=temp^carry;
carry=(temp&carry)<<1;
}
return sum;
}
int add(int a,int b){
if(b==0) return a;
int carry=(a&b)<<1;
int sum=a^b;
add(sum,carry);
}
|
减法运算
由于计算机只会进行加法运算，那么减法就可以转变为加法运算，这涉及到计算机的原码反码和补码知识了。这里简单提下
- 正数的 原码=反码=补码
- 负数的 原码=正数的原码且最高位置为1。
如32位-3原码可表示为 10000000000000000000000000000011
- 负数的反码为其原码的最高位1不变，其余位取反(~)
如32位-3反码可表示为 11111111111111111111111111111100
- 负数的补码为其反码+1
如32位-3补码可表示为 11111111111111111111111111111101
目前补码普遍是计算机内部数值的表示方式，它很好的解决了 +0 和 -0的问题
因此减法运算就变得十分简单的
代码如下
|
int subtract(int a,int b){
int negative=add(~b,1);
return add(a,negative);
}
|
负数和正数转换(设x>0)：
-x=(~x+1) 如 -10=(~10+1)
x=~(-x-1) 如 10=~(-10-1)
x=~(-x)+1 如 10=~(-10)+1
乘法运算
其实乘法也就是多个加法的累积求和，在我们小学时，25×5应该是这样计算的
| 2 5
× 0 5
————————
1 2 5
+ 0 0
————————
1 2 5
|
二进制也可以这样计算，不过就是满2进1。这里还是以25×5=125为例
| 0 1 1 0 0 1 = 25
× 1 0 1 = 5
————————————————————
0 1 1 0 0 1 = 25
+ 0 0 0 0 0 0 = 0
+ 0 1 1 0 0 1 = 25<<2 = 25*2^2=120
———————————————————
0 1 1 1 1 1 0 1 = 125 = 25+120
|
将乘法分解为加法即可实现位运算，大致思路如下，
存在一个函数 int multiply(int a,int b);
1.若b<0，则对b求负化为正数，同时设置一个标识neagtive_mask记录该b是负数
2.对除数b不断右移b>>=1并且取得b最低位的值(0或1)，直到b=0
3.若为1，则add操作得sum
4.a不断左移1位 a<<=1
5.结尾判断neagtive_mask来设置sum的正负
注意，除数如果为负数，假设为 11111111111111111111111111111011 (-5)，那么其右移得不到b=0，至于被除数可以小于0
具体代码如下
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
| int multiply(int a,int b){
bool neagtive_mask=(b<0);
if(b<0){2
b=~(b-1);
}
int sum=0;
while (b)
{
if(b&0x1){
sum=add(sum,a);
}
b>>=1;
a<<=1;
}
if(neagtive_mask){
sum=~(sum-1);
}
return sum;
}
|
除法运算
除法就相对来说复杂了，不过除法类似减法，不断地减去除数得到商，最后剩下余数
这里还是以小学数学除法为例子 37÷3=12…1
| 12
-----
3 | 37
- 3
----
7
- 6
---
1
|
其中这操作还可以转换为
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
| 步骤1
1
-----
30 | 37
- 30
----
7
步骤2
2
----
3| 7
-6
---
1
商: 1*10^1 + 2*10^0 = 10+2=12
最后余下1
|
发现了什么吗？
现在我们把上面十进制换成二进制
37: 100101
3: 0011
7: 1101
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
| 步骤1
1
--------
11000| 100101 ->a=37
- 11000
-------
1101 ->7
步骤2
1
------
1100| 1101 ->a=7
- 1100
------
1
步骤3
0
------
110| 1
- 0
------
1
商: 1*2^3 + 1*2^2 + 0
= 1<<3 + 1<<2 + 0
= 8+4+0=12
最后余下1
|
在上面例子中，除数3左移3位变为 11000，接着除数3左移2位变为 1100，最后左移1位变为 110。
此时发现 被除数1 小于 除数110，因此商为0（C++语言中除法运算导致返回一个整数）。
因此如果发现被除数小于除数，那么直接返回0即可。
于是要先找到除数应该左移的位数，且使得除数是<=除数
然后利用减法 :a=subtract(a,b<<nMove)
利用加法 :当前累加值r=add(前一个值累加值r,1<<nMove)
代码如下
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
| int divide(int a,int b){
int nMove=0;
bool negative_mask=false;
if(a<0){
a=~(a-1);
negative_mask=true;
}
if(b<0){
b=~(b-1);
negative_mask=negative_mask==false?true:false;
}
if(a<b){return 0;}
for ( nMove = 0; nMove<32;nMove++){
if((b<<nMove)>=a){
break;
}
}
int r=0;
for (int i = nMove; i >=0; i--){
int t=b<<i;
if(a<t)
continue;
a=subtract(a,t);
r=add(r,1<<i);
}
if(negative_mask){
r=~(r-1);
}
return r;
}
|
输出二进制
| void printBinary(int number){
char strBinary[33]{ 0 };
unsigned int bitmask = 1 << 31;
for (int i = 0; i < 32; i++)
{
char k = ((number & bitmask)>>31)?'1':'0';
strBinary[i] = k;
number <<= 1;
}
cout << strBinary << endl;
}
|
简单数据交换
利用xor位异或来实现值交换
原理:
a ^ a = 0
a ^ 0 = a
0 ^ a = a
| int a=10,b=20;
a=a^b;
b=a^b;
a=a^b;
|
bye~