Implement the long-hand multiplication algorithm for two n-bit unsigned numbers,
ID: 3752489 • Letter: I
Question
Implement the long-hand multiplication algorithm for two n-bit unsigned numbers, with no recursion, no divide-and-conquer, etc. Note that you need to multiply bitstrings not integers, and the return value of your program should also be a bitstring. E.g., x = 11110000, y = 10111100, then if z = x×y, your program should return z = 1011000001000000.
Hint. The bitstring is a simple string with many 0s and 1s, you need to parse the input strings x and y as boolean arrays, with the lsb at index 0 of array. Output z should also be stored in a boolean array.
Language- Java
Explanation / Answer
PROGRAM
import java.util.Scanner;
// declare main class BinaryMul
class BinaryMul
{
// implement mulBinary() method
public static String mulBinary(String a,String b)
{
// convert a and b string into reverse using StringBuilder class
// create two instances n1 and n2 of StringBuilder() class
String n1=new StringBuilder(a).reverse().toString();
String n2=new StringBuilder(b).reverse().toString();
int[] d=new int[a.length()+b.length()]; // two strings length into single array d
// multiply each digit and sum at the corresponding positions
for(int i=0;i<n1.length();i++){
for(int j=0;j<n2.length();j++)
d[i+j]+=(n1.charAt(i)-'0') * (n2.charAt(j)-'0');
}
StringBuilder sb = new StringBuilder(); // create instance sb fro StringBuilder()
for(int i=0; i<d.length; i++){ // create for loop
int m = d[i]%2; // calculate remainder store into m
int c = d[i]/2; // retrieve carry bits into c
if(i+1<d.length){ // check condition
d[i+1] += c; // store carry bit into array d
}
sb.insert(0, m); // using StringBuilder object sb adding of remainder bits
}
while(sb.charAt(0) == '0' && sb.length()> 1){ //create while loop first bit 0
sb.deleteCharAt(0); // delete first bits 0
}
return sb.toString(); // return sb object
}
public static void main(String args[])
{
Scanner scr=new Scanner(System.in); // create Scanner object scr
// read two binary numbers
System.out.print("Enter First Binary Number: ");
String a=scr.next();
System.out.print("Enter Second Binary Number: ");
String b=scr.next();
System.out.print("Multiplied a and b Value is: "+mulBinary(a,b)); // calling mulBinary() method and print result
}
}
OUTPUT-1
F:>javac BinaryMul.java
F:>java BinaryMul
Enter First Binary Number: 11110000
Enter Second Binary Number: 10111100
Multiplied a and b Value is: 1011000001000000
OUTPUT-2
F:>java BinaryMul
Enter First Binary Number: 01011101
Enter Second Binary Number: 1011101
Multiplied a and b Value is: 10000111001001