Multiply Two Integers Without Multiplication: Russian Peasant, Bit Shifts

Multiply Two Integers Without Using Multiplication: Russian Peasant, Bit Shifts, Recursion

“Multiply two integers without using the * operator” is a classic interview question that tests your fluency with bit manipulation, recursion, and the underlying arithmetic. The naive approach (repeatedly add) gives O(n) where n is one operand. The elegant approach (Russian peasant / shift-and-add) gives O(log n). This guide covers all standard approaches with working code, the bit-trick rationale, and the variations that come up.

Problem Statement

Given two integers a and b, return a * b without using the multiplication operator. Handle:

• Positive, negative, and zero values
• Both operands of equal magnitude or wildly different
• Edge cases: 0 × anything, INT_MIN, large numbers

Examples:

• multiply(3, 5) → 15
• multiply(-3, 5) → -15
• multiply(0, 100) → 0
• multiply(2, 1000000) → 2000000

Approach 1: Repeated Addition (Naive)

Add a to itself b times. Trivial; O(b) time.

def multiply_naive(a: int, b: int) -> int:
    """O(|b|) time."""
    if b < 0:
        return -multiply_naive(a, -b)
    result = 0
    for _ in range(b):
        result += a
    return result

Acceptable as a warm-up for very small operands. For b = 10^6, this is a million additions — too slow. Interviewers expect you to optimize.

Approach 2: Russian Peasant Multiplication (Standard Answer)

Also called “shift-and-add” or “binary multiplication.” Process the binary representation of b: for each bit, double a and add to result if the bit is set.

def multiply_russian(a: int, b: int) -> int:
    """O(log |b|) time using shift-and-add."""
    # Handle signs
    sign = 1
    if a < 0:
        a = -a
        sign = -sign
    if b < 0:
        b = -b
        sign = -sign

    result = 0
    while b > 0:
        if b & 1:        # if lowest bit of b is set
            result += a
        a <<= 1          # double a
        b >>= 1          # halve b (integer division)
    return sign * result


# Tests
print(multiply_russian(3, 5))    # 15
print(multiply_russian(-3, 5))   # -15
print(multiply_russian(0, 100))  # 0
print(multiply_russian(2, 1000000))  # 2000000

Complexity: O(log |b|) time, O(1) space.

Why Russian peasant works

The algorithm follows from a * b = a * (b₀ + 2b₁ + 4b₂ + ...) where bᵢ is the ith bit of b’s binary representation. Distribute: a*b₀ + 2a*b₁ + 4a*b₂ + .... The doubling of a at each step matches the powers of 2; the bit check decides whether to add.

For multiplying 13 × 7:

• b = 7 = 111₂. Bits set at positions 0, 1, 2.
• Step 0: bit 0 set → add a (13). a doubles to 26.
• Step 1: bit 1 set → add a (26 → result becomes 39). a doubles to 52.
• Step 2: bit 2 set → add a (52 → result becomes 91). a doubles to 104.
• b is now 0 → done.

Result: 91. Verify: 13 × 7 = 91. ✓

Approach 3: Recursive Doubling

Same logic, recursive form. Useful when explaining the algorithm visually.

def multiply_recursive(a: int, b: int) -> int:
    """O(log |b|) recursion stack."""
    if b == 0:
        return 0
    if b < 0:
        return -multiply_recursive(a, -b)

    half = multiply_recursive(a, b // 2)
    if b % 2 == 0:
        return half + half
    return half + half + a

O(log n) time and recursion stack space. Some find this version more intuitive; the iterative version is slightly more efficient.

Approach 4: Built-In (For Comparison)

Python’s native * operator uses CPU multiplication for small ints and arbitrary-precision algorithms (Karatsuba, Toom-Cook) for larger ints. For interview purposes, mention this exists but implement one of the manual approaches.

Common Variations

Multiply by a constant in O(1)

Multiplying by a power of 2: just left-shift. Multiplying by 3: (x << 1) + x. Multiplying by 7: (x << 3) - x. These are useful tricks for embedded systems and compiler optimization.

Multiply two large numbers

For numbers larger than fit in machine words, use Karatsuba’s algorithm: O(n^log₂ 3) ≈ O(n^1.585). For very large (cryptographic-scale): Toom-Cook, FFT-based multiplication (Schönhage-Strassen) at O(n log n log log n). Outside scope of standard interviews.

Multiply matrices

(LeetCode #311) Different problem; same fundamental “shift and add” idea applies to matrix exponentiation for fast Fibonacci, etc.

Implement division using only addition / subtraction

Mirror image of multiplication. Use repeated subtraction or shift-and-subtract for O(log n) division.

Common Mistakes

• Not handling negative numbers. Always normalize signs first; handle the result sign separately.
• Integer overflow. In C/C++/Java, multiplying near INT_MAX can overflow. Use long long or BigInteger. In Python, no overflow concerns for arbitrary precision.
• Using * in the implementation. The point of the question is to avoid the multiplication operator. Doubling via a + a or a << 1 is fine; a * 2 is cheating.
• Off-by-one in the bit loop. The loop should continue while b > 0, not while b ≥ 0 (which is infinite).
• Forgetting to halve b in the loop. Without b >>= 1, the loop is infinite. The bit-check pattern requires consuming bits one at a time.

Frequently Asked Questions

See also: Fast Exponentiation • Power of Two Check • Two Sum: Find a Pair in an Array

function multiply(a, b) {
    // Handle zero
    if (a === 0 || b === 0) return 0;

    // Handle negative (make b positive for simplicity)
    let negative = false;
    if (b < 0) {
        b = -b;
        negative = !negative;
    }
    if (a < 0) {
        a = -a;
        negative = !negative;
    }

    let result = 0;
    for (let i = 0; i < b; i++) {
        result += a;
    }

    return negative ? -result : result;
}

console.log(multiply(3, 4));    // 12
console.log(multiply(-3, 4));   // -12
console.log(multiply(-3, -4));  // 12
console.log(multiply(7, 0));    // 0

function multiplyBits(a, b) {
    // Handle zero
    if (a === 0 || b === 0) return 0;

    // Handle negative
    let negative = false;
    if (a < 0) {
        a = -a;
        negative = !negative;
    }
    if (b < 0) {
        b = -b;
        negative = !negative;
    }

    let result = 0;

    // Process each bit of b
    while (b > 0) {
        // If current bit is 1, add current a to result
        if (b & 1) {
            result += a;
        }

        // Double a (left shift)
        a <<= 1;

        // Halve b (right shift)
        b >>= 1;
    }

    return negative ? -result : result;
}

console.log(multiplyBits(3, 5));    // 15
console.log(multiplyBits(17, 8));   // 136
console.log(multiplyBits(-6, 7));   // -42

b = 5 = 101₂
    Bit 0 (1): result += 3 × 2⁰ = 3
    Bit 1 (0): skip
    Bit 2 (1): result += 3 × 2² = 12

Total: 3 + 12 = 15 ✓

Initial: a=3, b=5, result=0

Iteration 1:
  b & 1 = 1 → result += 3 = 3
  a <<= 1 → a = 6
  b >>= 1 → b = 2

Iteration 2:
  b & 1 = 0 → skip
  a <<= 1 → a = 12
  b >>= 1 → b = 1

Iteration 3:
  b & 1 = 1 → result += 12 = 15
  a <<= 1 → a = 24
  b >>= 1 → b = 0

Result: 15 ✓

function multiplyRecursive(a, b) {
    // Base cases
    if (b === 0) return 0;
    if (b === 1) return a;

    // Handle negative
    if (b < 0) return -multiplyRecursive(a, -b);

    // If b is even: a * b = 2 * (a * b/2)
    if (b % 2 === 0) {
        return multiplyRecursive(a + a, Math.floor(b / 2));
    }

    // If b is odd: a * b = a + a * (b-1)
    return a + multiplyRecursive(a, b - 1);
}

console.log(multiplyRecursive(4, 6));   // 24
console.log(multiplyRecursive(7, 9));   // 63

function multiplySafe(a, b) {
    const MAX_INT = 2147483647;

    // Check for potential overflow
    if (a !== 0 && Math.abs(b) > MAX_INT / Math.abs(a)) {
        throw new Error("Overflow detected");
    }

    return multiplyBits(a, b);
}

function divide(dividend, divisor) {
    if (divisor === 0) throw new Error("Division by zero");

    let negative = (dividend < 0) !== (divisor < 0);
    dividend = Math.abs(dividend);
    divisor = Math.abs(divisor);

    let quotient = 0;

    while (dividend >= divisor) {
        dividend -= divisor;
        quotient++;
    }

    return negative ? -quotient : quotient;
}

console.log(divide(10, 3));   // 3
console.log(divide(-10, 3));  // -3