二进制的加减乘除实现
程序员文章站
2022-07-15 10:02:30
...
1. 加法
当二进制加法没有进位时,两个数的加法其实就是按位异或,例如3 + 4 = 7,011 + 100 = 111,这个结果就是按位异或得到的结果,但是我们的加法肯定是存在进位的,那我们进位怎么表示呢,我们想一下,我同样使用异或运算,当只考虑一位的时候(a表示其中一个数的第i位,b表示另外一个数的第i位),只有两个1才会有进位,这就和与运算是一样的,但是进位肯定是要往前移位的,所以进位可以表示为 a & b << 1
递归写法
public int sum(int a, int b) {
// 如果b为0,则表示没有进位了,那么a就是结果
if (b == 0) {
return a;
}
return sum(a ^ b, (a & b) << 1);
}
非递归写法
public int sum(int a, int b) {
while (b != 0) {
// 保留a的值
int t = a;
a = a ^ b;
b = (t & b) << 1;
}
return a;
}
2. 减法
减法可以转换为加法,就不赘述了,例如a - b = a + (-b)
3. 乘法
关于二进制的乘法,例如 110 * 1010101,a * b 我们可以以其中a为基准,判断a的最低位是否为1,如果最低位是1,则结果加上b,然后a右移一位,b左移一位,直到a等于0,最后的结果就是结果 + b,我们判断最低位是否为1是因为我们右移的时候会丢失这个1,其实就是一个数除2,另外一个数乘2,对于结果是没有影响的,例如 6 * 43 = 3 * 86 = 86 + (1 * 172) = 86 + 172,就是这样的一个过程
代码实现
public int mul(int a, int b) {
int res = 0;
while (a != 0) {
if ((a & 1) == 1) {
res += b;
}
a >>= 1;
b <<= 1;
}
return res;
}
4. 除法(整数除法)
关于二级制的除法,其实和乘法是相反的,分为以下几个步骤,a / b,默认 b < a
- 将 b 的位数通过移位与 a 对齐,记为b1
- 如果 a >= b1,则 a = a - b1,res += 2 的(b的位数- b1的位数)次方,然后 b1 右移一位
- 如果 b1 大于等于 b,继续步骤 2
- 最后得到结果res,a 就是 a / b 的余数
整体过程描述:10 / 3
- a = 10 b = 3 res = 0 b1 = 12
- a = 10 b = 3 res = 0 b1 = 6
- a = a - b1 = 4 b = 3 res += 2 ^ (3 - 2) = 2 b1 = 3
- a = a - b1 = 1 b = 3 res += 2 ^ (2 - 2) = 2 + 1 = 3 b1 = 1
即最后的结果 res = 3,余数 a = 1
代码实现
// 默认a b和运算中的结果都在int范围内
// 默认都是正数,如果出现负数,则符号统一处理
public int div(int a, int b) {
// 如果 a < b,直接返回0
if (a < b) {
return 0;
}
int count = 0; // 记录b移位的次数,即 b 和 b1 相差位数(二进制)
int b1 = b;
int res = 0; // 记录结果
// 模拟移位
while (b1 < a) {
++count;
b1 <<= 1;
}
while (b1 >= b) {
if (a >= b1) {
a -= b1;
res += (1 << count);
}
b1 >>= 1;
--count;
}
return res;
}
PS: 这个除法并不适用于所有的 int 整数的除法,当出现一些特殊值时,可能导致溢出,例如Integer.MIN_VALUE等
上一篇: 写一个函数返回参数二进制中1的个数
下一篇: JNI学习笔记(一)——C语言基础