布思算法——Java实现
前面一篇提到二进制队列实现了 N位二进制的补码,那么我们来实现布思算法。
关于BinaryQueue:https://www.cnblogs.com/XT-xutao/p/10050518.html
先来思考:我们这样实现二进制乘法呢?
对于无符号整数,是可以转化为加法的:
那么补码形式呢?好像一些也是可以用上面这种转化为加法的:
上面被乘数-7是小于0的,但是乘数为负的时候好像就不能工作了,因为不能正确地得出部分积。
怎么办呢?
还有一种方法: 就是在乘之前先判断符号,如果异号,则结果为负,用他们的绝对值形式乘就可以了,最后加符号就行。
但是,这种方法似乎太麻烦了,我们更偏向于——布思算法(BOOTH)
布思算法是基于: 2^n+2^n-1......2^n-k = 2^(n+1) - 2^(n-k)
它有两大优点:
1.避免了如上的那种复杂操作。
2.减少了不必要的加法,节约了时间。
那么在计算机底层是怎么实现的呢?
可以用几个寄存器搞定:
A:附加寄存器,初始化0
Q:乘数寄存器
M:被乘数寄存器
Q0:乘数的最低位,初始化0
根据流程图就可以实现了。最后的结果是AQ寄存器里的值。
更新:前面讲那个BinaryQueue方法不好,直接用字符串形式的二进制表示更简单:
public String multiply(String Q,String M){
char Q0 = '0';
String A = get01(Q.length(),"0");
for (int i=0;i<Q.length();i++){
String QQ0 =Q.charAt(Q.length()-1)+""+Q0;//不能把两个char字符放在一起,会变成加
System.out.println(QQ0);
if (QQ0.equals("10")){
A=substract(A,M).substring(1);
}
else if (QQ0.equals("01")){
A=add(A,M).substring(1);
}
String temp = shiftRight(A+Q+Q0);
A=temp.substring(0,A.length());
Q = temp.substring(A.length(),2*A.length());
Q0 = temp.charAt(temp.length()-1);
}
return A+Q;
}
那么代码怎么实现(BinaryQueue)呢?
package com.computerOrganizationAndArchitecture.IntegerOperation; import com.computerOrganizationAndArchitecture.BinaryQueue; /**
* Created by XuTao on 2018/12/1 19:27
* 用BinaryQueue实现布思算法 (Java语言)
*/
public class Booth {
BinaryQueue Q, M, A; // Q:乘数; M:被乘数; A: 附加
private String n1,n2;
public Booth(String str1, String str2) {//要进行操作的两个二进制数的字符串模式
this.n1=str1;
this.n2=str2;
int len; // 最长的长度(如果两个二进制不一样长的话)
//扩展短的那个
if (n1.length() > n2.length()) {
String s = "";
len = n1.length() - n2.length();
for (int i = 0; i < len; i++) {
s += n2.charAt(0);
}
n2 = s + n2;
}
else if (n1.length()<n2.length()){
String s = "";
len = n2.length() - n1.length();
for (int i = 0; i < len; i++) {
s += n1.charAt(0);
}
n1 = s + n1;
System.out.println(n1);
}
else len = n1.length(); Q = new BinaryQueue(n1);
M = new BinaryQueue(n2);
A = new BinaryQueue(len);
int Q0 = 0; //Q的最低位,初始化为0,用于判断要进行的操作 System.out.println(A.getStr() + " " + Q.getStr() + " " + Q0 + " " + M.getStr());
for (int i = 0; i < len; i++) {
if (Q.getLast() == 1 && Q0 == 0) {//1-0 模式,A= A-M,
A = A.subtract(M);
} else if (Q.getLast() == 0 && Q0 == 1) {
A = A.add(M);
}
//AQQ0右移一位
Q0 = Q.getLast();
Q.shiftRight();
Q.set(0, A.getLast());
A.shiftRightArithmetically(); System.out.println(A.getStr() + " " + Q.getStr() + " " + Q0 + " " + M.getStr());
}
BinaryQueue bq = new BinaryQueue(A.getStr() + Q.getStr());// A + Q
System.out.println(A.getStr() + Q.getStr());
System.out.println(bq.getInt());
} public static void main(String[] args) {
new Booth("0011", "1111"); //3 * -1 = -3
new Booth("111111", "001111"); //-1 * 15 = -15
new Booth("011110", "001111"); //30 * 15 = 450
} } demo: A Q Q0 M
0000 0011 0 1111 第0周期
0000 1001 1 1111 第1周期
0000 0100 1 1111 第2周期
1111 1010 0 1111 第3周期
1111 1101 0 1111 第4周期
结果:
11111101
-3
000000 111111 0 001111
111000 111111 1 001111
111100 011111 1 001111
111110 001111 1 001111
111111 000111 1 001111
111111 100011 1 001111
111111 110001 1 001111
111111110001
-15
000000 011110 0 001111
000000 001111 0 001111
111000 100111 1 001111
111100 010011 1 001111
111110 001001 1 001111
111111 000100 1 001111
000111 000010 0 001111
000111000010
450
最新文章
- 【GoLang】GoLang 的流程与函数
- CentOS6.5安装openLdap
- redis cluster搭建
- 裸设备和Oracle问答20例
- Python核心编程--学习笔记--7--字典和集合
- 【BZOJ】【3757】苹果树
- Activity的任务栈Task以及启动模式与Intent的Flag详解
- JAVA缓存技术之EhCache(转)
- 支付宝AR实景红包上线不久即遭破解,官方已提高技术门槛
- 初学 Python(十三)——匿名函数
- CodeForces731-C.Socks-并查集
- mongo中常用的增删改查
- Monkey测试简介
- 在VMware中为Redhat HAT配置本地yum源
- 动态创建js脚本和 css样式
- Mahout简介
- C/C+ 感触
- Angular 4.0 使用第三方类库
- 04-python的列表操作
- rpm-yum_install_software
热门文章
- ASP.NET Web API 2 之参数验证
- 微信小程序开发(4) 企业展示
- mybatis的两个核心对象SqlSessionFactory和SqlSession对象
- Java EE之Hibernate异常总结org.hibernate.MappingException: Repeated column in mapping for entity:
- CF809C Find a car
- Flume思维导图
- json对象转数组
- tomcat源码之connector启动过程
- nova 命令管理虚拟机
- list补充,append()、extend()、insert()、remove()、del()、pop()、分片