本文主要介绍如何使用位运算来实现加减功能,也就是在整个运算过程中不能出现加减符号。
加减乘除运算在计算机中,实际上都是用位运算实现的,今天就用位运算来模拟下加法和减法的运算功能。
先分析如何用位运算实现加法运算。
假设a=23,b=36,使用位运算实现加法得到结果59。
首先来看下23、36、59的二进制信息。
从上面的图中可以看到,两个数相加的结果与两个数异或的结果很相似,只不过在图中的2位置相加的时候,产生了进位,而异或是没有进位的,如果能拿到进位信息,把两个数异或的结果和进位信息的结果相加就能得到最终结果了,那么如果能拿到进位信息呢?
上图中,59的二进制信息可以分为两部分,0110011 和 0001000,再结合23、36的二进制信息来看,0110011为23和36的异或结果,而23和36相与的结果跟0001000很相似,只不过0001000中的1比相与结果往前移了一位。
于是,我们可以得出,两个数的二进制进位信息为两个数的相与在左移一位。
经过上面的分析,我们可以得到了一个初步的运算结果,即两个数相加等于两个数异或加上两个数的相与左移1位,也就是a + b = (a ^ b) + ((a & b) << 1)。
先用23和36来验证下。
经过验证可以看到,刚才得出的结论是正确的。
但是,我们要做到在整个运算过程中不能出现加号,接下来要想办法把这个加号给去掉。
还是以23和36为例,经过上面的运算我们把运算的位运算结果给化简下。
23 + 36 = (23 ^ 36) + ((23 & 36) << 1) = 51 + 8
也就是把23和36的相加运算转化为了51和8的相加运算,接下来继续分析51和8的相加运算,也是通过异或和相与进行操作。
51 + 8 = (51 ^ 8) + ((51 & 8) << 1) = 59 + 0
嗯?可以发现我们已经得出59了,而且还加了个0,加了个0不就相当于加了个寂寞嘛,可以直接省略啊。
由此,我们又可以得出一个结论,两个数的二进制进位信息为两个数的相与在左移一位,不停地循环这个过程,直到有一个数变为0,就能得到结果。
现在来总结下整体的计算过程:
经过上面的分析,来看下代码实现。
public class Code19_Add {
public static int add(int a, int b) {
int sum = 0;
while (b != 0) {
sum = a ^ b;
b = (a & b) << 1;
a = sum;
}
return sum;
}
public static void main(String[] args) {
int sum = add(23, 36);
System.out.println(sum);
}
}
复制代码
运行程序,输出结果为59。
还是以23和36为例,如果要计算 36 - 23,该怎么办?
36 - 23 不就相当于36 + (-23),可以理解为加上一个负数,这就可以了吗?不不不,要求的是不能出现加减符号,-23里面是有减法这个符号的。
还记得前面我们分析的负数可以怎么表示吗?对了,负数是对一个数的取反再加1。嗯?又出现加号了,不过加法我们不是已经实现了吗?直接拿来用就好了。
有了加法操作,减法就很简单了,来看下代码。
public class Code20_Sub {
public static int add(int a, int b) {
int sum = 0;
while (b != 0) {
sum = a ^ b;
b = (a & b) << 1;
a = sum;
}
return sum;
}
public static int sub(int a, int b) {
return add(a, add(~b, 1));
}
public static void main(String[] args) {
int sum = sub(36, 23);
System.out.println(sum);
}
}
复制代码
运行一下输出结果为13。
嗯,Perfect!
本文主要介绍如何使用位运算来实现加减功能,至此功能都已经实现了。
那么问题来了,我们实现的加减运算与Java本身的加减相比,谁的效率更高呢?当然是Java中的更高了,因为我们是用Java实现的,代码运行后,要经过层层的翻译才能到达底层,所以效率肯定是有损失的。
当然我们的目的是熟悉位运算的操作,这个才是最重要的。
原文链接:https://juejin.cn/post/7183115929226575928
页面更新:2024-04-25
本站资料均由网友自行发布提供,仅用于学习交流。如有版权问题,请与我联系,QQ:4156828
© CopyRight 2008-2024 All Rights Reserved. Powered By bs178.com 闽ICP备11008920号-3
闽公网安备35020302034844号