Java利用位运算实现乘法运算详解
作者:Java星辰 发布时间:2023-03-19 20:29:24
前言
在上一篇中,我们介绍了使用位运算实现加法和减法运算,接下来本文主要介绍如何用位运算实现乘法运算,在实现乘法时要用位运算实现,并且不能出现加减乘除任何符号。
之前介绍过一篇如何用位运算实现加法和减法: 如何用位运算实现加减运算?
在用位运算实现之前,我们先来回忆一下小学时,学乘法时用的十字相乘法。
十进制相乘
例如,26 * 15
,在进行乘法操作时,我们一般这样算,先用5
乘以6
得到30
,把0
写下把3
记在一边,再用5
乘以2
得到10
再加上之前的3
写在下面,得到130
;计算完5
再计算1
分别乘以6
和2
把得到的结果26
记在下面,然后把130
和26
相加(有错位)得到390
。
二进制相乘
看完了十进制的相乘,再来看下二进制的相乘,基本原理是一样的,也是以十字相乘法为例,计算 5 * 7
。
5
的二进制为101
,7
的二进制为111
,来看下二进制的十字相乘法。
可以看到二进制为101
和二进制111
用传统的方式来计算,得到的结果为100011
,而二进制100011
对应的十进制为35
。
所以说,在计算的过程中,十进制和二进制的计算方式是一样的,当然这里就不进行举例和证明了。
思路分析
既然计算过程有了,那么怎么样用代码来实现呢?
我们再来看下上图中二进制的计算过程:
先用二进制
111
的最后一位1
乘上101
得到101
。再用二进制
111
的倒数第2位1
乘上101
得到101
。再用二进制
111
的倒数第3位1
乘上101
得到101
。得到的三个
101
进行二进制相加,得到100011
。
注意,第2
步和第3
步得到的结果101
都往前挪了一位,相当于1010
和10100
,也就是最后相加的计算为:10100 + 1010 + 101 = 100011
。
再来看得到最终相加的计算10100 + 1010 + 101 = 100011
,也就是只要我们找到如何把数据转换为几位数的相加就可以了,因为之前已经实现了如何用位运算实现加法操作。
这三个数101
、1010
、10100
的数量刚好与二进制111
的个数相同,也就是二进制(上图下面那个乘数111
)有几位就会产生几个数相加,如果是与11111
相乘就会产生5
个数相加。
再来看数据之前的关系:
第一次相乘结果:
101 = 101 + 0
第二次相乘结果:
1111 = 101 < 1 + 101 = 1010 + 101
第三次相乘结果:
100011 = 101 < 2 + 1111 = 10100 + 1010 + 101
从这里我们可以看到,每计算一次,101
只需要向左移一次再加上上一次的计算结果就可以了。
那么,怎么知道要左移多少次呢?从这里例子中看,111
每次计算后,向右移动一次,101
也跟着向左移动一次,直到111
只剩最后一位,则停止计算就好了。
代码实现
根据上面的思路,来实现一下代码:
// 用位运算实现加法
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 multi(int a, int b) {
int res = 0;
while (b != 0) {
if ((b & 1) != 0) {
res = add(res, a);
}
a <<= 1;
b >>>= 1;
}
return res;
}
运行一下代码,看下结果:
可以看到计算是正确的,而且还支持负数。
来源:https://juejin.cn/post/7221113101591445565
猜你喜欢
- ActiveMQ 结合 Spring 收发消息直接使用 ActiveMQ 的方式需要重复写很多代码,且不利于管理,Spring 提供了一种更
- 近日于LeetCode看题遇1114 按序打印,获悉一解法使用了Semaphore,顺势研究,记心得于此。此解视Semaphore为锁,以保
- List去重复,我们首先想到的可能是 利用List转Set集合,因为Set集合不允许重复。所以达到这个目的。 如果集合里面是简单对
- 前言在看一本关于高性能编程的时候发现 Java8 中关于接口的新特性的介绍,这个特性是真的棒,解决了一个接口中有多个方法,但并不想实现该接口
- 在早期开发的时候,我们完成的都是静态页面也就是html页面,随着时间轴的发展,慢慢的引入了jsp页面,当在后端服务查询到数据之后可以转发到j
- 背景:在Android中按照数据保存的方式,可以分为如下几种Content Provider (用的SQLite实现),SQLite,Sha
- 前言Java.util包中的List接口继承了Collection接口,用来存放对象集合,所以对这些对象进行排序的时候,要么让对象类自己实现
- 前言:在没有接触java8的时候,我们遍历一个集合都是用循环的方式,从第一条数据遍历到最后一条数据,现在思考一个问题,为什么要使用循环,因为
- 问题分析疑惑满满小枫听到这个面试题的时候,心想这是什么水面试官,怎么问这么简单的题目,心想一个for循环加上equal判断再删除不就完事了吗
- 委托定义类型,类型指定特定方法签名。可将满足此签名的方法(静态或实例)分配给该类型的变量,然后(使用适当参数)直接调用该方法,或将其作为参数
- 1、maven打包Spring Boot项目的pom.xml文件中默认使用spring-boot-maven-plugin插件进行打包:&l
- 本文实例讲述了Java实现的计算最大下标距离算法。分享给大家供大家参考,具体如下:题目描述给定一个整形数组,找出最大下标距离j−i, 当且A
- PipedOutputStream和PipedInputStream在java中,PipedOutputStream和PipedInputS
- 在实际工作中,重试重发请求处理是一个非常常见的场景,比如:1、发送消息失败。2、调用远程服务失败。3、争抢锁失败。这些错误可能是因为网络波动
- 如下所示:String.valueOf((char)10)在导出excel 的时候,如果原始文字中含有 \n 字符, 如果把 \n 替换为&
- 选择排序:(Selection sort)是一种简单直观的排序算法,也是一种不稳定的排序方法。选择排序的原理一组无序待排数组,做升序排序,我
- Java设计模式的模板方法模式定义一个操作中算法的框架,而将一些步骤延迟到子类中,使得子类可以不改变算法的结构即可重定义该算法中的某些特定步
- 1.首先,八种基本数据类型分别是:int、short、float、double、long、boolean、byte、char; &
- 本文介绍SpringBoot如何使用Prometheus配合Grafana监控。1.关于PrometheusPrometheus是一个根据应
- ELK环境安装ELK是指Elasticsearch、Kibana、Logstash这三种服务搭建的日志收集系统,具体搭建方式可以参考《Spr