Problem

Given two integers a and b, compute the product a * b without using the multiplication operator (*). The allowed operations are bitwise shifts, bitwise logical operators, addition and subtraction. Preserve sign semantics for negative inputs and handle zero correctly.

Examples

Example 1

1
2

Input: a = 15, b = 27
Output: 405

Example 2

1
2

Input: a = -5, b = 4
Output: -20
Similar Problems

Solution

Method 0 — Repeated addition (naive)

Intuition

Multiplication is repeated addition: a * b equals adding a to itself |b| times and adjusting sign at the end. This is the simplest approach when only + is available.

Approach

  1. If b == 0 return 0.
  2. Compute abs_a = |a|, abs_b = |b| and neg = (a < 0) ^ (b < 0) for the result sign.
  3. Initialize ans = 0.
  4. Loop i from 1 to abs_b: ans = ans + abs_a.
  5. Return -ans if neg else ans.

Edge cases: when abs_b is large this is slow (O(|b|) iterations).

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11

class Solution {
 public:
  int multiply(int a, int b) {
    bool neg = (a < 0) ^ (b < 0);
    int abs_a = a < 0 ? -a : a;
    int abs_b = b < 0 ? -b : b;
    int ans = 0;
    for (int i = 0; i < abs_b; ++i) ans += abs_a;
    return neg ? -ans : ans;
  }
};
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13

package main

func multiply(a, b int) int {
  neg := (a < 0) != (b < 0)
  if a < 0 { a = -a }
  if b < 0 { b = -b }
  ans := 0
  for i := 0; i < b; i++ {
    ans += a
  }
  if neg { ans = -ans }
  return ans
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10

class Solution {
  public int multiply(int a, int b) {
    boolean neg = (a < 0) ^ (b < 0);
    int absA = Math.abs(a);
    int absB = Math.abs(b);
    int ans = 0;
    for (int i = 0; i < absB; ++i) ans += absA;
    return neg ? -ans : ans;
  }
}
1
2
3
4
5
6
7
8

class Solution:
  def multiply(self, a: int, b: int) -> int:
    neg = (a < 0) ^ (b < 0)
    a, b = abs(a), abs(b)
    ans = 0
    for _ in range(b):
      ans += a
    return -ans if neg else ans

Complexity

  • ⏰ Time complexity: O(|b|), because we perform |b| additions.
  • 🧺 Space complexity: O(1), only constant temporaries are used.

Method 1 — Shift-and-add (Russian peasant / binary decomposition)

Intuition

Multiply by decomposing the multiplier into binary bits. Shift the multiplicand left when the multiplier’s current bit is considered and add it to the result when that bit is 1. Repeatedly halve the multiplier and double the multiplicand — this performs O(log |b|) additions.

Approach

  1. If a == 0 or b == 0 return 0.
  2. Compute neg = (a < 0) ^ (b < 0), and work with abs_a = |a|, abs_b = |b|.
  3. Initialize ans = 0.
  4. While abs_b > 0:
    • If abs_b & 1 is 1 then ans += abs_a.
    • Left shift abs_a (abs_a <<= 1) and right shift abs_b (abs_b >>= 1).
  5. Return -ans if neg else ans.

This uses O(log |b|) iterations; each iteration performs at most one addition and two shifts.

Edge cases: handle INT_MIN/overflow depending on language; use larger types if necessary.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17

class Solution {
 public:
  int multiply(int a, int b) {
    if (a == 0 || b == 0) return 0;
    bool neg = (a < 0) ^ (b < 0);
    unsigned int ua = a < 0 ? -static_cast<unsigned int>(a) : a;
    unsigned int ub = b < 0 ? -static_cast<unsigned int>(b) : b;
    unsigned int ans = 0;
    while (ub) {
      if (ub & 1) ans += ua;
      ua <<= 1;
      ub >>= 1;
    }
    int res = static_cast<int>(ans);
    return neg ? -res : res;
  }
};
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16

package main

func multiply(a, b int) int {
  if a == 0 || b == 0 { return 0 }
  neg := (a < 0) != (b < 0)
  if a < 0 { a = -a }
  if b < 0 { b = -b }
  ans := 0
  for b != 0 {
    if b&1 == 1 { ans += a }
    a <<= 1
    b >>= 1
  }
  if neg { ans = -ans }
  return ans
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15

class Solution {
  public int multiply(int a, int b) {
    if (a == 0 || b == 0) return 0;
    boolean neg = (a < 0) ^ (b < 0);
    int ua = Math.abs(a);
    int ub = Math.abs(b);
    int ans = 0;
    while (ub != 0) {
      if ((ub & 1) != 0) ans += ua;
      ua <<= 1;
      ub >>= 1;
    }
    return neg ? -ans : ans;
  }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13

class Solution:
  def multiply(self, a: int, b: int) -> int:
    if a == 0 or b == 0:
      return 0
    neg = (a < 0) ^ (b < 0)
    a, b = abs(a), abs(b)
    ans = 0
    while b:
      if b & 1:
        ans += a
      a <<= 1
      b >>= 1
    return -ans if neg else ans

Complexity

  • ⏰ Time complexity: O(log |b|), because the loop iterates once per binary digit of b and performs at most one addition per set bit.
  • 🧺 Space complexity: O(1), only a fixed number of temporaries are used.