TEST TIME ON BINARY PALINDROME

URL: [Link]

QR CODE:
 Java introduction, Features, Structure, Data type

BOOTH'S ALGORITHM
 Java introduction, Features, Structure, Data type

TOPICS

Introduction
Flow chart
Algorithm
Program
Interview questions
Booth’s algorithm
The booth’s algorithm is a multiplication algorithm that allows us to multiply the two
signed binary integers in 2's complement, respectively.
It is also used to speed up the performance of the multiplication process. It is very efficient
too.

It works on the string bits 0's in the multiplier that requires no additional bit. Only shift the
right-most string bits and a string of 1's in a multiplier bit weight 2^k to weight 2^m that
can be considered as 2^k+ 1 to 2^m.

As in all multiplication schemes, booth’s algorithm requires examination of the multiplier

bits and shifting of the partial product.
Explanation :

Prior to the shifting, the multiplicand may be added to the partial product, subtracted from
the partial product, or left unchanged according to following rules:

1. The multiplicand is subtracted from the partial product upon encountering the first
least significant 1 in a string of 1’s in the multiplier.

2. The multiplicand is added to the partial product upon encountering the first 0
(provided that there was a previous ‘1’) in a string of 0’s in the multiplier.

3. The partial product does not change when the multiplier bit is identical to the previous
multiplier bit.
Flow chart
START
An extra Flip-Flop Q-1 is appended to Q to facilitate a double
inspection of the multiplier.
Acc = 0, Q-1 – 0
M,<- Multiplicand
Initially, Acc and Q-1 bits are set to 0 Q <- Multiplier
Count <- n
There are M that represent the multiplicand bits, and Q represents
the multiplier bits.
The Count is a sequence counter that represents the total bits set n, 0, 1 Q, 1, 0
Acc <- Acc + M Q-1 Acc <- Acc - M
which is equal to the number of bits in the multiplier. ?

0, 0 1, 1
If the two of the multipliers equal to 0 1, we need to perform the
addition of the multiplicand to the partial product in accumulator Acc
Arithmetic Right Shift of Acc ,Q, Q-1
and then perform the Arithmetic Right Shift (ARS) operation. Count <- Count - 1

If the two bits of the multiplier is equal to 1 0, we have to subtract

the multiplier from the partial product in the Acc and then perform
N Count Y
the ARS operation. == 0 STOP
?
If the two bits of the multiplier is equal to 0 0 or 1 1, we has to
perform ASR operations.
And the Count is continuously decremented till the computational
loop is repeated (i.e. equal to the number of bits ‘n’).
Algorithm

Set the Multiplicand and Multiplier binary bits as M and Q, respectively.

Initially, we set the Ac and Q-1 registers value to 0.

Count represents the number of Multiplier bits (Q), and it is a sequence counter that is continuously
decremented till equal to the number of bits (n) or reached to 0.

A Qn represents the last bit of the Q, and the Q-1 shows the incremented bit of Qn by 1.
Algorithm
On each cycle of the booth algorithm, Qn and Q-1 bits will be checked on the following parameters as
follows:

• When two bits Qn and Q-1 are 0 0 or 1 1, we simply perform the Arithmetic Right Shift (ARS)
operation to the partial product Acc. And the bits of Qn and Q-1 is incremented by 1 bit.

• If the bits of Qn and Q-1 is shows to 0 1, the multiplicand bits (M) will be added to the Acc
(Accumulator register). After that, we perform the ARS operation to the AC and Q bits, by 1.

• If the bits of Qn and Q-1 is shows to 1 0, the multiplicand bits (M) will be subtracted from the
Acc. After that, we perform the right shift operation to the Acc and Q bits by 1.
Algorithm

The operation continuously works till we reached n - 1 bit in the booth algorithm.

Results of the Multiplication binary bits will be stored in the Acc and Q registers.
Multiplicand (M): 0 1 0 1 1
Multiplier (Q): 0 1 1 1 0 MxQ : 2j(M)+2i(Ḿ)
Accumulator (Acc) Multiplier (Q) Q-1

0 0 0 0 0 0 1 1 1 0 0
QLSB Q-1 Operations 0 0 0 0 0 0 0 1 1 1 0
Arithmetic Right Shift (ARS) 1 0 1 0 1
0 0
1 0 1 0 1 0 0 1 1 1 0
0 1 Acc <- Acc + M, ARS
1 1 0 1 0 1 0 0 1 1 1
Acc <- Acc + Ḿ, ARS 1 1 1 0 1 0 1 0 0 1 1
1 0 1 1
1 1 1 0 1 0 1 0 0
Arithmetic Right Shift (ARS) 0 1 0 1 1
1 1
1 0 1 0 0 1 1 0 1 0 0 1
0 0 1 0 0 1 1 0 1 0 0
Program
Sample IO
Input
Enter two integer numbers
7 -7
Output
A : 0111 0000 0
S : 1001 0000 0
P : 0000 1001 0

P : 1100 1100 1
P : 0001 1110 0
P : 0000 1111 0
P : 1100 1111 1

Result : 7 * -7 = -49
Program

import [Link];
public class Main {
public static Scanner s = new Scanner([Link]);
/** Function to multiply **/
public int multiply(int n1, int n2) {
int[] m = binary(n1);
int[] m1 = binary(-n1);
int[] r = binary(n2);
int[] A = new int[9];
int[] S = new int[9];
int[] P = new int[9];
for (int i = 0; i < 4; i++) {
A[i] = m[i];
S[i] = m1[i];
P[i + 4] = r[i];
}
Program

display(A, 'A');
display(S, 'S');
display(P, 'P');
[Link]();
for (int i = 0; i < 4; i++) {
if (P[7] == 0 && P[8] == 1) {
add(P, A);
} else if (P[7] == 1 && P[8] == 0) {
add(P, S);
}
rightShift(P);
display(P, 'P');
}
return getDecimal(P);
}
Program

/** Function to get Decimal equivalent of P **/

public int getDecimal(int[] B) {
int p = 0;
int t = 1;
for (int i = 7; i >= 0; i--, t *= 2)
p += (B[i] * t);
if (B[0] == 1) // if the result is negative
p = p - 256;
return p;
}
/** Function to right shift array **/
public void rightShift(int[] A) {
for (int i = 8; i > 0; i--) {
A[i] = A[i - 1];
}
// Sign extend
A[0] = A[1];
}
Program
/** Function to add two binary arrays **/
public void add(int[] A, int[] B) {
int carry = 0;
for (int i = 8; i >= 0; i--) {
int temp = A[i] + B[i] + carry;
A[i] = temp % 2;
carry = temp / 2;
}
}
/** Function to get binary of a number **/
public int[] binary(int n) {
int[] bin = new int[4];
int ctr = 3;
int num = n;
/** for negative numbers 2's complement **/
if (n < 0)
num = 16 + n;
while (num != 0) {
bin[ctr--] = num % 2;
num /= 2;
}
return bin;
}
Program
/** Function to print array **/
public void display(int[] P, char ch) {
[Link]("\n" + ch + " : ");
for (int i = 0; i < [Link]; i++) {
if (i == 4)
[Link](" ");
if (i == 8)
[Link](" ");
[Link](P[i]);
}
}
/** Main function **/
public static void main(String[] args) {
Scanner scan = new Scanner([Link]);
Main b = new Main();
[Link]("Enter two integer numbers -");
int n1 = [Link]();
int n2 = [Link]();
int result = [Link](n1, n2);
[Link]("\n\nResult : " + n1 + " * " + n2 + " = " + result);
}
}
Program
import [Link].*;
class Main {
public static void main(String[] args) {
Scanner sc = new Scanner([Link]);
int multiplicand = [Link]();
int multiplier = [Link]();

int product = 0;
int multiplicandBits = [Link](multiplicand).length();

for (int i = 0; i < multiplicandBits; i++) {

int currentBit = (multiplicand & 0b1);
if (currentBit == 1) {
product += multiplier;
}
multiplier <<= 1;
multiplicand >>>= 1;
}
[Link](product);
}
}
Methods used in Booth’s algorithm

RSC (Right Shift Circular)

It shifts the right-most bit of the binary number, and then it is added to the beginning of the binary bits.

RSA (Right Shift Arithmetic)

It adds the two binary bits and then shift the result to the right by 1-bit position.

Example: 0100 + 0110 => 1010, after adding the binary number shift each bit by 1 to the right and put
the first bit of resultant to the beginning of the new bit.
Example
 Java introduction, Features, Structure, Data type

INTERVIEW QUESTIONS
Interview questions
1. What is Booth’s Algorithm?

Answer:

Booth's Algorithm is a multiplication algorithm that allows for the multiplication of two signed binary

integers represented in 2's complement form. It optimizes the multiplication process by reducing the

number of necessary addition and subtraction operations, thus speeding up the performance.
Interview questions
2. How does Booth’s Algorithm handle the multiplication process?

Answer:

Booth's Algorithm examines the bits of the multiplier and performs specific operations based on the

following rules:

If a pair of bits is "10", subtract the multiplicand from the accumulator.

If a pair of bits is "01", add the multiplicand to the accumulator.

If the bits are "00" or "11", simply perform an arithmetic right shift (ARS) on the partial product.
Interview questions
3. What initial values are set in Booth's Algorithm before starting the multiplication process?

Answer:

Before starting the multiplication process, the following initial values are set:

"Acc" (Accumulator) is set to 0.

"Q-1" (an extra bit appended to the multiplier for double inspection) is set to 0.

"M" (Multiplicand) is assigned the value of the multiplicand.

"Q" (Multiplier) is assigned the value of the multiplier.

"Count" is set to the number of bits in the multiplier.

Interview questions
4. Explain the role of the "Q-1" bit in Booth’s Algorithm.

Answer:

The "Q-1" bit is an extra bit appended to the right of the multiplier. It facilitates the examination of pairs

of bits ("Q[n]" and "Q[n-1]") to decide the arithmetic operation (addition, subtraction, or shift) to be

performed during each cycle of the algorithm.

Interview questions
5. What happens during each cycle of Booth’s Algorithm?

Answer:During each cycle of Booth’s Algorithm, the following steps occur:

1. Check the bits "Q0" (the least significant bit of "Q") and "Q-1".

2. Perform one of the following operations based on the values of "Q0" and "Q-1":

If "Q0 Q-1" is "10", subtract the multiplicand from the accumulator and perform an ARS.

If "Q0 Q-1" is "01", add the multiplicand to the accumulator and perform an ARS.

If "Q0 Q-1" is "00" or "11", perform an ARS.

3. Decrement the count.

4. Repeat the process until the count reaches zero.

Interview questions
[Link] are the advantages of using Booth’s Algorithm?

Answer:

The advantages of using Booth’s Algorithm include:

Reduced number of additions and subtractions, leading to faster computation.

Efficient handling of both positive and negative numbers.

Optimization of the multiplication process for numbers with large sequences of 0s or 1s, resulting in

fewer operations compared to straightforward multiplication.

Practice questions
Question 1: Multiplication of Two Positive Integers Using Booth's Algorithm
Implement a method to multiply two positive integers using Booth's Algorithm. Ensure your method
correctly handles the binary multiplication process.
Sample Test Cases:
1. Input: multiplicand = 6, multiplier = 3
Output: 18
Explanation: The binary multiplication of 6 (110) and 3 (011) results in 18 (10010 in binary).
2. Input: multiplicand = 9, multiplier = 5
Output: 45
Explanation: The binary multiplication of 9 (1001) and 5 (0101) results in 45 (101101 in binary).
Practice questions
Question 2: Multiplication of a Positive and a Negative Integer Using Booth's Algorithm
Implement a method to multiply a positive integer and a negative integer using Booth's Algorithm. Ensure your method
correctly handles the binary multiplication of signed integers.
Sample Test Cases:
1. Input: multiplicand = 7, multiplier = -3
Output: -21
Explanation: The binary multiplication of 7 (0111) and -3 (1101 in 2's complement) results in -21 (101011 in 2's
complement).
2. Input: multiplicand = -8, multiplier = 4
Output: -32
Explanation: The binary multiplication of -8 (1000 in 2's complement) and 4 (0100) results in -32 (11100000 in 2's
complement).
 THANK YOU

+91 78150 95095 codemithra@[Link] [Link]