Booth's Algorithm
Submitted by
Marzit Talukdar
Semester: 4th
Roll No: 230103011
Department of Information Technology
Gauhati University Institute of Science and Technology
// Booth's Algorithm Implementation in Java
import java.util.Scanner;
public class BoothsAlgorithm {
static String toBinary(int num, int bits) {
StringBuilder bin = new StringBuilder();
for (int i = bits - 1; i >= 0; i--) {
bin.append((num >> i) & 1);
}
return bin.toString();
}
static int binaryToDecimal(String bin) {
int val = 0;
boolean isNegative = bin.charAt(0) == '1';
if (isNegative) {
StringBuilder inverted = new StringBuilder();
for (char c : bin.toCharArray())
inverted.append(c == '1' ? '0' : '1');
String one = "1";
for (int i = 1; i < bin.length(); i++) one = "0" + one;
bin = addBinary(inverted.toString(), one);
}
for (char c : bin.toCharArray())
val = (val << 1) + (c - '0');
return isNegative ? -val : val;
}
static String addBinary(String a, String b) {
StringBuilder res = new StringBuilder();
int carry = 0;
for (int i = a.length() - 1; i >= 0; i--) {
int sum = (a.charAt(i) - '0') + (b.charAt(i) - '0') + carry;
res.insert(0, sum % 2);
carry = sum / 2;
}
return res.toString();
}
static String twoComplement(String bin) {
StringBuilder inverted = new StringBuilder();
for (char c : bin.toCharArray())
inverted.append(c == '1' ? '0' : '1');
String one = "1";
for (int i = 1; i < bin.length(); i++) one = "0" + one;
return addBinary(inverted.toString(), one);
}
static void arithmeticRightShift(StringBuilder A, StringBuilder Q, char[] Q1) {
char lastA = A.charAt(0);
Q1[0] = Q.charAt(Q.length() - 1);
Q.insert(0, A.charAt(A.length() - 1));
Q.setLength(Q.length() - 1);
A.insert(0, lastA);
A.setLength(A.length() - 1);
}
static void boothsAlgorithm(int M, int Qnum, int bits) {
StringBuilder A = new StringBuilder("0".repeat(bits));
StringBuilder Q = new StringBuilder(toBinary(Qnum, bits));
String M_bin = toBinary(M, bits);
String M_neg = twoComplement(M_bin);
char[] Q1 = {'0'};
for (int i = 0; i < bits; i++) {
if (Q.charAt(bits - 1) == '1' && Q1[0] == '0')
A = new StringBuilder(addBinary(A.toString(), M_neg));
else if (Q.charAt(bits - 1) == '0' && Q1[0] == '1')
A = new StringBuilder(addBinary(A.toString(), M_bin));
arithmeticRightShift(A, Q, Q1);
}
String result = A.toString() + Q.toString();
System.out.println("Binary Result: " + result);
System.out.println("Decimal Result: " + binaryToDecimal(result));
}
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
System.out.print("Enter Multiplicand: ");
int M = sc.nextInt();
System.out.print("Enter Multiplier: ");
int Q = sc.nextInt();
int bits = 5;
boothsAlgorithm(M, Q, bits);
sc.close();
}
}
