百度360必应搜狗淘宝本站头条
当前位置:网站首页 > 文章教程 > 正文

算法 | 如何用位运算实现加减运算?

xsobi 2024-11-23 10:49 1 浏览

前言

本文主要介绍如何使用位运算来实现加减功能,也就是在整个运算过程中不能出现加减符号。

加减乘除运算在计算机中,实际上都是用位运算实现的,今天就用位运算来模拟下加法和减法的运算功能。

思路分析

先分析如何用位运算实现加法运算。

示例

假设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,就能得到结果。

整体思路

现在来总结下整体的计算过程:

  1. 把两个数相加,拆分成两步,两个数异或加上两个数相与左移1位。
  2. 判断相与左移的结果是否为0。
  3. 如果相与左移为0,两个数异或的结果即为相加的结果。
  4. 如果相与左移结果不为0,把得到的新结果,重复执行第1~3步操作。

加法代码实现

经过上面的分析,来看下代码实现。

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实现的,代码运行后,要经过层层的翻译才能到达底层,所以效率肯定是有损失的。

当然我们的目的是熟悉位运算的操作,这个才是最重要的。

感谢你的查看,如果本文能给你来的帮助,就辛苦动动你那英俊、美丽的手指,帮我点个赞或评论下吧~

相关推荐

js向对象中添加元素(对象,数组) js对象里面添加元素

一、添加一个元素对象名["属性名"]=值(值:可以是一个值,可以是一个对象,也可以是一个数组)这样添加进去的元素,就是一个值或对象或数组...

JS小技巧,如何去重对象数组?(一)

大家好,关于数组对象去重的业务场景,想必大家都遇到过类似的需求吧,这对这样的需求你是怎么做的呢。下面我就先和大家分享下如果是基于对象的1个属性是怎么去重实现的。方法一:使用.filter()和....

「C/C++」之数组、vector对象和array对象的比较

数组学习过C语言的,对数组应该都不会陌生,于是这里就不再对数组进行展开介绍。模板类vector模板类vector类似于string,也是一种动态数组。能够在运行阶段设置vector对象的长度,可以在末...

如何用sessionStorage保存对象和数组

背景:在工作中,我将[{},{}]对象数组形式,存储到sessionStorage,然后ta变成了我看不懂的形式,然后我想取之用之,发现不可能了~记录这次深刻的教训。$clickCouponIndex...

JavaScript Array 对象 javascript的array对象

Array对象Array对象用于在变量中存储多个值:varcars=["Saab","Volvo","BMW"];第一个数组元素的索引值为0,第二个索引值为1,以此类推。更多有...

JavaScript中的数组Array(对象) js array数组

1:数组Array:-数组也是一个对象-数组也是用来存储数据的-和object不同,数组中可以存储一组有序的数据,-数组中存储的数据我们称其为元素(element)-数组中的每一个元素都有一...

数组和对象方法&amp;数组去重 数组去重的5种方法前端

列举一下JavaScript数组和对象有哪些原生方法?数组:arr.concat(arr1,arr2,arrn);--合并两个或多个数组。此方法不会修改原有数组,而是返回一个新数组...

C++ 类如何定义对象数组?初始化数组?linux C++第43讲

对象数组学过C语言的读者对数组的概念应该很熟悉了。数组的元素可以是int类型的变量,例如int...

ElasticSearch第六篇:复合数据类型-数组,对象

在ElasticSearch中,使用JSON结构来存储数据,一个Key/Value对是JSON的一个字段,而Value可以是基础数据类型,也可以是数组,文档(也叫对象),或文档数组,因此,每个JSON...

第58条:区分数组对象和类数组对象

示例设想有两个不同类的API。第一个是位向量:有序的位集合varbits=newBitVector;bits.enable(4);bits.enable([1,3,8,17]);b...

八皇后问题解法(Common Lisp实现)

如何才能在一张国际象棋的棋盘上摆上八个皇后而不致使她们互相威胁呢?这个著名的问题可以方便地通过一种树搜索方法来解决。首先,我们需要写一个函数来判断棋盘上的两个皇后是否互相威协。在国际象棋中,皇后可以沿...

visual lisp修改颜色的模板函数 怎么更改visual studio的配色

(defunBF-yansemokuai(tuyuanyanse/ss)...

用中望CAD加载LISP程序技巧 中望cad2015怎么加载燕秀

1、首先请加载lisp程序,加载方法如下:在菜单栏选择工具——加载应用程序——添加,选择lisp程序然后加载,然后选择添加到启动组。2、然后是添加自定义栏以及图标,方法如下(以...

图的深度优先搜索和广度优先搜索(Common Lisp实现)

为了便于描述,本文中的图指的是下图所示的无向图。搜索指:搜索从S到F的一条路径。若存在,则以表的形式返回路径;若不存在,则返回nil。...

两个有助于理解Common Lisp宏的例子

在Lisp中,函数和数据具有相同的形式。这是Lisp语言的一个重大特色。一个Lisp函数可以分析另一个Lisp函数;甚至可以和另一个Lisp函数组成一个整体,并加以利用。Lisp的宏,是实现上述特色的...