5.1 Addition Algorithm

The addition algorithm is a fundamental process used in computers to perform the arithmetic operation of adding two numbers. In digital systems, this typically involves binary addition, but the algorithm can be extended to other number systems, such as decimal. The algorithm is implemented in the Arithmetic Logic Unit (ALU) of the CPU.

Key Concepts of Addition Algorithm

1. Binary Addition:
   • Binary numbers consist of two digits: 0 and 1. The basic rules for binary addition are as follows:
     • 0 + 0 = 0
     • 0 + 1 = 1
     • 1 + 0 = 1
     • 1 + 1 = 10 (which is 0 with a carry of 1)
2. Carry Propagation:
   • When adding two binary digits (bits), if the result exceeds 1, a carry is propagated to the next higher bit. This carry must be considered in the final sum.
   • For example, adding 1 + 1 produces a sum of 0 and a carry of 1, which is added to the next pair of bits.
3. Unsigned Addition:
   • The simplest form of binary addition, where two non-negative binary numbers are added without considering any sign bit.
4. Signed Addition (Using Two’s Complement):
   • In modern computer systems, signed numbers are usually represented using two’s complement. When adding two signed numbers, the same binary addition algorithm is used, but special attention must be paid to overflow conditions and sign extension.

Steps of the Basic Binary Addition Algorithm

The following steps outline the binary addition process:

1. Initialize:
   • Start with two binary numbers (A and B) that need to be added, and a carry initialized to 0.
2. Bitwise Addition:
   • Add the least significant bits (LSBs) of both numbers along with any carry from the previous step.
3. Carry Propagation:
   • If the result of the addition is 2 (binary 10), set the carry to 1 for the next higher bit; otherwise, the carry is 0.
4. Repeat:
   • Repeat the process for the next higher bit, considering the carry from the previous step.
5. Final Carry:
   • If there is a carry after the most significant bit (MSB) addition, it may be propagated as an overflow or included as part of a larger word.

Example of Binary Addition

Consider the addition of two 4-bit binary numbers:

1. Add the LSBs: 1 + 1 = 10 (sum = 0, carry = 1).
2. Add the next bits with carry: 1 + 1 + carry 1 = 11 (sum = 1, carry = 1).
3. Add the next bits with carry: 0 + 1 + carry 1 = 10 (sum = 0, carry = 1).
4. Add the MSBs with carry: 1 + 0 + carry 1 = 10 (sum = 0, carry = 1).
5. Final carry: 1 (overflow if not handled in a larger word).

Final result: 10010 (which is 18 in decimal).

Addition Algorithm for Multi-bit Binary Numbers (Pseudocode)

Addition Algorithm in Hardware

In hardware, the addition algorithm is implemented using full adders. A full adder is a combinational logic circuit that adds two binary digits and accounts for carry from previous bits. The full adder provides a sum bit and a carry bit.

• Ripple Carry Adder: A common implementation where the carry from each bit addition is passed to the next full adder. This can be slow for large numbers due to the carry propagation delay.
• Carry-Lookahead Adder: This design improves speed by generating carry signals in advance, reducing the delay caused by carry propagation.

5.2       Subtraction Algorithm

The subtraction algorithm in digital computers typically involves subtracting one number (the subtrahend) from another (the minuend). In binary systems, subtraction can be performed directly using basic rules of binary subtraction or indirectly using methods like two’s complement. The two’s complement method transforms the subtraction problem into an addition problem, which simplifies hardware design.

Key Concepts in Subtraction Algorithm

1. Binary Subtraction: Binary subtraction follows rules similar to decimal subtraction but with only two digits: 0 and 1. The basic rules for binary subtraction are:
   • 0 − 0 = 0
   • 1 − 0 = 1
   • 1 − 1 = 0
   • 0 − 1 = 1 (with a borrow from the next higher bit)
2. Borrow in Binary Subtraction:
   • When subtracting a larger digit from a smaller one (e.g., 0 − 1), a borrow is required from the next higher bit.
   • Borrowing in binary involves taking a 1 from the higher bit, which reduces its value by 1 and adds 2 to the current bit.
3. Two’s Complement Subtraction:
   • To simplify the design of subtraction circuits, binary subtraction is often done by adding the two’s complement of the subtrahend to the minuend.
   • The two’s complement of a binary number is obtained by inverting all bits (changing 1 to 0 and 0 to 1) and adding 1 to the least significant bit (LSB).
   • This transforms the subtraction problem into an addition problem, which can be handled by the same hardware used for binary addition.

Steps of Binary Subtraction

Direct Binary Subtraction:

1. Initialize:
   • Start with two binary numbers: the minuend (A) and the subtrahend (B).
2. Bitwise Subtraction:
   • Subtract each bit of B from the corresponding bit of A, starting from the least significant bit (LSB).
3. Borrow:
   • If the result of a subtraction is negative (e.g., 0 − 1), borrow from the next higher bit, just like in decimal subtraction.
4. Repeat:
   • Continue the process for each pair of bits, taking into account any borrows from previous steps.
5. Final Result:
   • The result will be the difference between A and B.

Two’s Complement Subtraction (Preferred in Digital Systems):

1. Find Two’s Complement:
   • Compute the two’s complement of the subtrahend B.
     • Invert all bits of B.
     • Add 1 to the inverted bits.
2. Add:
   • Add the two’s complement of B to A.
3. Handle Overflow:
   • If an overflow occurs, discard the extra carry bit.
4. Final Result:
   • The result of the addition will be the same as A − B.

Example of Binary Subtraction Using Two’s Complement

Suppose we want to subtract B = 7 (0111 in binary) from A = 13 (1101 in binary):

1. Two’s Complement of B (0111):
   • Invert all bits: 1000
   • Add 1: 1001 (This is −7 in two’s complement form)
2. Add A and Two’s Complement of B:
   1101 (13 in binary)

• 1001 (−7 in two’s complement)

10110

0110 (This is 6 in decimal, which is the correct result)

Direct Binary Subtraction Example

Let’s subtract B = 0101 (5 in decimal) from A = 1010 (10 in decimal):

1. LSB: 0 − 1 (borrow from next bit), result = 1.
2. Next bit: 1 − 0 (no borrow), result = 1.
3. Next bit: 0 − 1 (borrow from next bit), result = 1.
4. MSB: 1 − 0 (after borrowing), result = 0.

Final result: 0111 (which is 7 in decimal, the correct result).

Subtraction Algorithm in Hardware

In modern processors, subtraction is typically implemented using a binary adder circuit with the following modifications:

• Inversion Circuit: The subtrahend is passed through a circuit that inverts its bits.
• Adder Circuit: The inverted bits are then added to the minuend along with an initial carry of 1, effectively implementing two’s complement subtraction.
• Overflow Detection: An overflow detection circuit checks whether the result of the subtraction falls outside the allowable range for signed numbers.

5.3       Multiplication Algorithm

The multiplication algorithm in computer systems is used to multiply two numbers, typically binary numbers. The algorithm can be implemented in different ways depending on the size of the numbers and the required precision. Just like in arithmetic, binary multiplication involves repetitive addition, shifting, and accumulation of partial products.

Key Concepts of Binary Multiplication

1. Binary Multiplication Rules:
   • Binary multiplication is simpler than decimal multiplication because the only digits are 0 and 1. The rules for binary multiplication are:
     • 0 × 0 = 0
     • 0 × 1 = 0
     • 1 × 0 = 0
     • 1 × 1 = 1
   • Similar to decimal multiplication, binary multiplication also involves the concept of partial products and carries.
2. Partial Products:
   • Each bit of the multiplier is multiplied by the entire multiplicand, resulting in partial products. These partial products are then added together to obtain the final result.
   • The position of each partial product is determined by the bit position of the multiplier (just like shifting in decimal multiplication).
3. Shift-and-Add Multiplication:
   • The basic method for binary multiplication involves shifting the multiplicand to the left for each bit of the multiplier and adding the partial products together. This is similar to long multiplication in decimal systems.

Steps of Binary Multiplication

The process of multiplying two binary numbers (A and B) can be summarized as follows:

1. Initialize:
   • Start with two binary numbers: the multiplicand (A) and the multiplier (B).
   • Set the product (P) to 0.
2. Multiply and Shift:
   • For each bit of the multiplier (starting from the least significant bit):
     • If the bit is 1, add the multiplicand (shifted according to the bit position) to the product.
     • If the bit is 0, skip to the next bit.
   • Shift the multiplicand to the left by 1 bit for each subsequent bit of the multiplier.
3. Add Partial Products:
   • Add each shifted multiplicand (partial product) to the final product.
4. Final Product:
   • The accumulated sum of the partial products gives the final result.

Example of Binary Multiplication

Let’s multiply A = 1011 (11 in decimal) by B = 1101 (13 in decimal):

Partial products:

Hardware Implementation of Multiplication

In hardware, multiplication can be performed using various algorithms that differ in complexity and speed:

1. Shift-and-Add Multiplier:
   • This is the simplest method of binary multiplication and is implemented by shifting the multiplicand and adding partial products. It is similar to the manual method described above but implemented in hardware.
2. Booth’s Algorithm:
   • Booth’s algorithm is an efficient multiplication algorithm that reduces the number of required additions by encoding the multiplier in a way that takes advantage of sequences of 1s and 0s.
   • For example, a sequence of consecutive 1s in the multiplier can be replaced by a subtraction followed by a left shift, which reduces the number of operations.
3. Wallace Tree Multiplier:
   • A more complex hardware implementation is the Wallace Tree, which uses parallelism to add the partial products in fewer steps. This improves the speed of multiplication, particularly for large numbers.

Example of Booth’s Algorithm

Consider multiplying A = 9 (1001 in binary) and B = 3 (0011 in binary) using Booth’s algorithm. Booth’s algorithm encodes runs of 1s to simplify the multiplication. Each run of 1s in the multiplier results in fewer shifts and additions compared to the basic method.

5.4       Division Algorithm

The division algorithm in computer systems is used to divide two numbers, typically in binary form. Just like multiplication, division can be complex and involves several steps, including subtraction and shifting. Division algorithms are used in Arithmetic Logic Units (ALUs) of processors, and there are several methods to implement division, ranging from basic repetitive subtraction to more advanced algorithms like restoring and non-restoring division.

Key Concepts in Binary Division

1. Binary Division Rules: Binary division follows rules similar to long division in decimal systems, but the operation is simplified since we are dealing with only two digits (0 and 1). The basic steps involve:
   • Repeated subtraction of the divisor from the dividend.
   • If the divisor can be subtracted from the dividend, the quotient gets a 1; otherwise, it gets a 0.
2. Quotient and Remainder: Just like in regular division, binary division results in two parts: the quotient and the remainder. The quotient represents how many times the divisor fits into the dividend, while the remainder is the leftover part of the dividend.
3. Restoring and Non-Restoring Division: Two common methods of binary division are restoring division and non-restoring division:
   • Restoring Division: After every subtraction, if the result (partial remainder) is negative, the divisor is added back to “restore” the previous value.
   • Non-Restoring Division: Instead of restoring the value when the remainder goes negative, the algorithm moves on to the next step without restoring, with adjustments made later.

Steps of Binary Division (Restoring Method)

The restoring division algorithm follows these steps:

1. Initialize:
   • Start with the dividend (the number to be divided) and the divisor (the number by which the dividend is divided).
   • Set the quotient and remainder to 0.
2. Align Divisor:
   • Align the divisor with the most significant part of the dividend.
3. Subtract Divisor:
   • Subtract the divisor from the aligned portion of the dividend (starting from the most significant bit).
   • If the result is positive or zero, write 1 in the corresponding position of the quotient.
   • If the result is negative, restore the original value by adding back the divisor and write 0 in the quotient.
4. Shift:
   • Shift the divisor right and move to the next bit of the dividend.
   • Repeat the process until all bits are processed.
5. Final Result:
   • The quotient and remainder are the final results of the division.

Example of Binary Division

Let’s divide A = 1011 (11 in decimal) by B = 0101 (5 in decimal):

Steps:

1. Align the divisor under the dividend:
   1011 (dividend)
   -0101 (divisor)
   ——-
   010 (remainder, positive)
   Quotient: 1
2. Shift the divisor and repeat:
   010 (shifted remainder)
   000 (shift divisor and subtract)
   Quotient: 10

So, the quotient is 2 and the remainder is 1.

Restoring Division Algorithm (Pseudocode)

Non-Restoring Division Algorithm (Pseudocode)

Division in Hardware

In hardware, division is typically implemented using a shift-and-subtract method. The division unit performs repeated subtraction and shifting operations, similar to the software algorithms described above. Some key hardware methods include:

1. Restoring Division: This method includes restoring the remainder when a subtraction results in a negative value, which is the traditional long division approach.
2. Non-Restoring Division: This method avoids restoring the remainder and optimizes the process by making corrections at the end, improving efficiency.

5.5       Logical Operations.

Logical operations are fundamental to computer systems, used for manipulating binary data and performing decision-making tasks in both hardware and software. These operations are performed at the bit level, where each bit is treated as a separate entity (either 0 or 1). Logical operations are essential in areas such as control flow, arithmetic, data manipulation, and bitwise calculations.

Common Logical (Bitwise) Operations

1. AND Operation (&):
   • The AND operation compares two bits and returns 1 if both bits are 1, otherwise it returns 0.
   • Truth table for AND:
     A | B | A AND B
     —————-
     0 | 0 | 0
     0 | 1 | 0
     1 | 0 | 0
     1 | 1 | 1
   • Example: 1101 & 1011 = 1001
2. OR Operation (|):
   • The OR operation compares two bits and returns 1 if either of the bits is 1, otherwise it returns 0.
   • Truth table for OR:
     A | B | A OR B
     —————
     0 | 0 | 0
     0 | 1 | 1
     1 | 0 | 1
     1 | 1 | 1
   • Example: 1101 | 1011 = 1111
3. XOR Operation (^):
   • The exclusive OR (XOR) operation compares two bits and returns 1 if the bits are different, otherwise it returns 0.
   • Truth table for XOR:
     A | B | A XOR B
     —————-
     0 | 0 | 0
     0 | 1 | 1
     1 | 0 | 1
     1 | 1 | 0
   • Example: 1101 ^ 1011 = 0110
4. NOT Operation (~):
   • The NOT operation (also called complement) inverts a bit, turning 1 into 0 and 0 into 1.
   • Truth table for NOT:
     A | NOT A
     ———-
     0 | 1
     1 | 0
   • Example: ~1101 = 0010 (assuming 4 bits)
5. NAND Operation:
   • The NAND operation is the complement of the AND operation. It returns 1 if at least one of the bits is 0, otherwise it returns 0.
   • Truth table for NAND:
     A | B | A NAND B
     —————–
     0 | 0 | 1
     0 | 1 | 1
     1 | 0 | 1
     1 | 1 | 0
6. NOR Operation:
   • The NOR operation is the complement of the OR operation. It returns 1 if both bits are 0, otherwise it returns 0.
   • Truth table for NOR:
     A | B | A NOR B
     —————-
     0 | 0 | 1
     0 | 1 | 0
     1 | 0 | 0
     1 | 1 | 0

Bitwise Operations in Programming (C Example)

In programming, logical operations are often used for bit manipulation. Here is a simple C program demonstrating these operations:

Output:

In this example:

• A = 1101 (0x0D in hexadecimal)
• B = 1011 (0x0B in hexadecimal)

Applications of Logical Operations

1. Masking:
   • Logical operations are commonly used to mask bits in data. For example, using AND with a specific mask can turn off certain bits, while OR can turn them on.
2. Setting or Clearing Flags:
   • In systems programming, logical operations are used to set or clear specific flags in a status register (e.g., enabling or disabling certain functionalities).
3. Parity Checking:
   • XOR is often used in parity checking, where it can determine whether the number of 1s in a binary number is odd or even.
4. Bit Shifting:
   • Logical operations combined with bit shifting are useful for moving bits around within a word, which is important in low-level programming tasks like encryption or compression.
5. Arithmetic:
   • Logical operations play a role in arithmetic operations such as addition, multiplication, and division at the binary level (e.g., the XOR gate is used in binary addition).

•           Write a program to demonstrate the Addition of two unsigned integers binary number

#include <stdio.h>

int binaryAddition(int a, int b) {
int carry;

while (b != 0) {
// Calculate carry
carry = a & b;

// Sum without carry
a = a ^ b;

// Shift carry by one to the left (to add it to the next position)
b = carry << 1;
}

return a;
}

void printBinary(int n) {
// Print the binary representation of an integer
int i;
printf(“Binary: “);
for (i = 31; i >= 0; i–) {
printf(“%d”, (n >> i) & 1);
}
printf(“\n”);
}

int main() {
int num1, num2, sum;

// Input two unsigned integers
printf(“Enter first binary number: “);
scanf(“%d”, &num1);

printf(“Enter second binary number: “);
scanf(“%d”, &num2);

// Perform binary addition
sum = binaryAddition(num1, num2);

// Output the result
printf(“Sum of two binary numbers: %d\n”, sum);
printBinary(sum);

return 0;
}

Example:

Input:

Output:

In this example, the binary numbers 5 (101 in binary) and 3 (011 in binary) are added to get the result 8 (1000 in binary).

•           Write a program to demonstrate multiplication of two unsigned integer binary numbers by Partial-Product method

The Partial-Product Method for multiplying two binary numbers is similar to how you multiply decimal numbers by hand. For each bit in the second binary number (multiplier), if the bit is 1, you add a shifted version of the first binary number (multiplicand) to a result.

Here’s a C program that demonstrates the multiplication of two unsigned integer binary numbers using the partial-product method:

Explanation:

1. binaryMultiplication Function: This function performs multiplication using the partial-product method:
   • It iterates through each bit of the multiplier, checking if the least significant bit is 1 by using the bitwise AND (multiplier & 1).
   • If the bit is 1, it shifts the multiplicand left by shift positions and adds it to the result.
   • The multiplier is shifted right (multiplier >>= 1) to process the next bit.
   • This process continues until all bits of the multiplier have been processed.
2. printBinary Function: This function prints the binary representation of the result.
3. Main Function:
   • Takes two binary numbers (in integer form) as input.
   • Calls the binaryMultiplication function to multiply them.
   • Prints the product both as an integer and in binary form.

Example:

Input:

Output:

How it works:

• Multiplicand = 5 (101 in binary)
• Multiplier = 3 (011 in binary)

Steps:

• Multiply 5 by the least significant bit of 3 (which is 1), so add 5 to the result.
• Shift 5 left by 1 (which becomes 1010), then multiply by the next bit of 3 (which is 1), so add 10 to the result.
• The total sum is 15 (1111 in binary).

This method simulates the manual partial-product multiplication but with binary numbers.

•           Write a program to demonstrate the Subtraction of two unsigned integers binary number

To perform the subtraction of two unsigned binary numbers, we can use the 2’s complement method. This method involves taking the 2’s complement of the second number (the subtrahend) and adding it to the first number (the minuend). The 2’s complement of a number is formed by inverting all the bits (1’s complement) and adding 1 to the result.

Here’s a C program that demonstrates the subtraction of two unsigned integer binary numbers using the 2’s complement method:

Explanation:

1. 1’s Complement: This is achieved by inverting the bits of a binary number using the bitwise NOT operator ~.
2. 2’s Complement: To get the 2’s complement, we add 1 to the 1’s complement of the number.
3. binaryAddition Function: This function adds two binary numbers. It uses bitwise operations to calculate the sum and the carry. The carry is then shifted left to add it to the next higher bit.
4. binarySubtraction Function: Subtraction is performed by adding the minuend (a) to the 2’s complement of the subtrahend (b).
5. printBinary Function: This function prints the binary representation of a number.
6. Main Function:
   • Takes two unsigned binary numbers (as integers) from the user.
   • Performs the subtraction by using the 2’s complement method.
   • Prints the result as an integer and in binary form.

Example:

Input:

Output:

How it works:

• Minuend = 10 (1010 in binary)
• Subtrahend = 3 (0011 in binary)

Steps:

1. Compute the 2’s complement of 3:
   • 1’s complement of 3: 1100
   • Add 1: 1101
2. Add 1010 (minuend) to 1101 (2’s complement of subtrahend):
   • Result: 0111 (7 in decimal)

This program simulates binary subtraction by using the 2’s complement method, a widely used technique in computer systems.

•           Write a program to demonstrate the Division using restoring

The restoring division algorithm is a technique for performing binary division. It works by repeatedly subtracting the divisor from the portion of the dividend and adjusting the quotient based on whether the subtraction result is positive or negative. The algorithm restores the original value if a subtraction results in a negative remainder, hence the name “restoring.”

Here’s a C program that demonstrates division of two unsigned binary numbers using the restoring division method:

Explanation:

1. restoringDivision Function: This is where the main logic of the restoring division algorithm occurs:
   • The remainder is initially set to 0.
   • The loop iterates through each bit of the dividend (starting from the most significant bit).
   • In each iteration:
     • The remainder is shifted left by 1, and the next bit of the dividend is brought down.
     • The divisor is subtracted from the remainder.
     • If the result is non-negative, the current quotient bit is set to 1.
     • If the result is negative, the quotient bit remains 0, and the original value of the remainder is restored by adding the divisor back.
   • At the end of the loop, the quotient and remainder are printed.
2. printBinary Function: This function prints the binary representation of a number.
3. Main Function:
   • Takes the dividend and divisor as input.
   • Calls the restoringDivision function to compute the quotient and remainder.
   • Prints the binary representations of both the dividend and divisor.

Example:

Input:

Output:

Steps:

1. Dividend = 20 (10100 in binary)
2. Divisor = 3 (11 in binary)

The division process:

• After several iterations, the quotient is found to be 6 and the remainder is 2. This means 20 / 3 = 6 with a remainder of 2.

•           Write a program to demonstrate the Division using non-restoring methods

The non-restoring division algorithm is another approach to binary division. Unlike the restoring method, this algorithm doesn’t restore the remainder to its original value if the subtraction results in a negative value. Instead, it directly adds the divisor back in the next iteration if needed.

Here’s a C program to demonstrate division using the non-restoring division method:

Explanation:

1. nonRestoringDivision Function:
   • Similar to the restoring method, but with a key difference: if the remainder is negative (i.e., after subtracting the divisor), we add the divisor back in the next step instead of restoring the previous remainder.
   • This function shifts the remainder and checks if it can subtract the divisor.
   • If it can, it subtracts the divisor and sets the quotient bit to 1. If not, it leaves the quotient bit at 0 and adjusts the remainder.
2. printBinary Function: This function prints the binary representation of a number.
3. Main Function:
   • Takes user input for the dividend and divisor.
   • Calls the non-restoring division function and prints both the quotient and remainder.
   • It also displays the binary form of the input numbers.

Example:

Input:

Output:

Steps:

1. Dividend = 20 (10100 in binary)
2. Divisor = 3 (11 in binary)

The division process yields a quotient of 6 and a remainder of 2.

This program illustrates the non-restoring division algorithm, which avoids restoring the remainder in cases of negative results, making it slightly faster in some implementations.