Implementing Multiplication and Division Using Only Bit Shifting and Addition

Introduction

In computer science, arithmetic operations are typically handled by the Arithmetic Logic Unit (ALU), but understanding their underlying implementation is crucial for code optimization and deep insights into computer architecture. While modern processors efficiently execute multiplication and division, using bit operations directly can offer performance benefits in embedded systems, low-power devices, or specific algorithms. This article examines how to implement integer multiplication and division using only bit left shifts, right shifts, and addition.

Bit-wise Implementation of Multiplication

Multiplication can be achieved by decomposing one operand into sums of powers of two. In binary, each bit represents a power of two, allowing multiplication to be transformed into a sequence of shifts and additions.

Consider computing 21 × 5. First, convert both numbers to binary:

21 = 10101₂
5 = 101₂

The multiplication process decomposes as follows:

21 × 5 = 10101₂ × 101₂
       = 10101₂ × (1×2² + 0×2¹ + 1×2⁰)
       = (10101₂ << 2) + (10101₂ << 0)
       = 1010100₂ + 10101₂
       = 1101001₂ = 105

Here, << denotes left shift, equivalent to multiplication by a power of two. By identifying the bits set to 1 in the multiplier, shifting the multiplicand accordingly, and summing the results, the product is obtained.

General Multiplication Algorithm

The above method generalizes to multiplication of any two integers. The algorithm steps are:

1. Initialize the result to 0.
2. Iterate through each bit of the multiplier:
   • If the current bit is 1, add the shifted multiplicand to the result.
   • Left shift the multiplicand by one, and right shift the multiplier by one.
3. Return the result.

Example implementation in C:

unsigned int multiply(unsigned int a, unsigned int b) {
    unsigned int result = 0;
    while (b > 0) {
        if (b & 1) {
            result += a;
        }
        a <<= 1;
        b >>= 1;
    }
    return result;
}

This algorithm has a time complexity of O(n), where n is the number of bits in the operands. In contrast, hardware multipliers may have higher constant factors, but modern processors often execute multiplication as fast as addition due to pipelining and dedicated circuits.

Bit-wise Implementation of Division

Division can also be implemented using shifts and additions, though it is more complex. For division by constants, binary fraction properties enable approximate calculations.

For example, to compute a / 3, first express 1/3 as a binary fraction:

1/3 ≈ 0.0101010101010101₂

Thus, a / 3 can be approximated as:

a / 3 ≈ (a >> 2) + (a >> 4) + (a >> 6) + ... + (a >> 30)

To reduce operations, terms can be combined:

unsigned int divide_by_3(unsigned int a) {
    unsigned int b = (a >> 2) + (a >> 4);
    b += (b >> 4);
    b += (b >> 8);
    b += (b >> 16);
    return b;
}

For arbitrary division, an iterative method similar to long division can be used. Example C implementation for integer division:

unsigned int divide(unsigned int dividend, unsigned int divisor) {
    if (divisor == 0) {
        // Handle division by zero error
        return 0;
    }
    unsigned int quotient = 0;
    int shift = 0;
    
    // Find the largest shift such that divisor << shift <= dividend
    while ((divisor << shift) <= dividend) {
        shift++;
    }
    shift--;
    
    while (shift >= 0) {
        if (dividend >= (divisor << shift)) {
            dividend -= (divisor << shift);
            quotient |= (1 << shift);
        }
        shift--;
    }
    return quotient;
}

Russian Peasant Multiplication Algorithm

The referenced Russian peasant multiplication algorithm offers another efficient bit-wise approach. For 20 × 13:

Step  Left Column (Double)  Right Column (Halve)
0     20                    13
1     40                    6
2     80                    3
3     160                   1

Then, sum the left column entries where the right column is odd: 160 + 80 + 20 = 260.

C implementation:

unsigned int russian_peasant(unsigned int a, unsigned int b) {
    unsigned int result = 0;
    while (b > 0) {
        if (b & 1) {
            result += a;
        }
        a <<= 1;
        b >>= 1;
    }
    return result;
}

This is essentially the same as the general multiplication algorithm, leveraging binary decomposition.

Performance Analysis and Applications

The performance of bit-wise multiplication and division depends on the number of bits in the operands. At the hardware level, multiplication generally requires more transistors and complex circuitry, potentially making it slower than addition and shifts in high-performance processors. However, modern pipelined architectures can mask this latency through parallel execution.

Bit-wise multiplication is particularly useful in:

• Embedded systems where hardware multipliers are unavailable or power-intensive.
• Cryptographic algorithms involving modular arithmetic with multiplication and division.
• Educational contexts to foundational computer arithmetic principles.

Conclusion

Full multiplication and division operations can be implemented using only bit left shifts, right shifts, and additions. These methods not only reveal the fundamentals of computer arithmetic but also provide performance advantages in specific applications. The algorithms and code examples in this article offer practical guidance for understanding and implementing these operations. For further optimization, readers may refer to classics like "Hacker's Delight," which details division by constants and other bit manipulation techniques.