Practice › Bit Manipulation
Divide Two Integers
Medium · Bit Manipulation · Asked at Meta, Amazon, Microsoft, Bloomberg
Divide a by b without using multiplication, division or the modulo operator, truncating toward zero (so 7 / −2 = −3). If the result is outside the 32-bit signed range [−2^31, 2^31 − 1], print 2^31 − 1 instead.
Input
A single line: a b.
Output
The quotient.
Constraints
- -2^31 ≤ a, b ≤ 2^31 − 1
- b ≠ 0
Work with absolute values in 64 bits. Subtract the largest shifted divisor (b << k) that still fits, add 1 << k to the quotient, and repeat. Apply the sign at the end.
Example 1
Input
10 3
Output
3
Example 2
Input
7 -3
Output
-2
Hints
- Division is repeated subtraction — but subtracting b one at a time is too slow when a is 2^31 and b is 1.
- Subtract the largest b·2^k (that is, b << k) that still fits, adding 2^k to the quotient, and repeat with smaller k.
Approach
Handle the only overflow case first: −2^31 / −1 = 2^31, which must print 2^31 − 1. Work with absolute values in 64-bit. For k from 31 down to 0, if (|b| << k) ≤ remaining, subtract it and add 1 << k to the quotient — like long division in binary. The result is negative when exactly one of a, b is negative; truncation toward zero comes for free because we divide magnitudes.
Complexity: O(32) time · O(1) space
Solution
C++ solution
#include <bits/stdc++.h>
using namespace std;
int main() {
long long a, b;
cin >> a >> b;
if (a == INT_MIN && b == -1) {
cout << INT_MAX << "\n";
return 0;
}
bool neg = (a < 0) != (b < 0);
long long x = llabs(a), y = llabs(b), q = 0;
for (int k = 31; k >= 0; k--)
if ((y << k) <= x) {
x -= y << k;
q += 1LL << k;
}
cout << (neg ? -q : q) << "\n";
return 0;
}Python solution
a, b = map(int, input().split())
if a == -(2**31) and b == -1:
print(2**31 - 1)
else:
neg = (a < 0) != (b < 0)
x, y, q = abs(a), abs(b), 0
for k in range(31, -1, -1):
if (y << k) <= x:
x -= y << k
q += 1 << k
print(-q if neg else q)Java solution
import java.util.*;
public class Main {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
long a = sc.nextLong(), b = sc.nextLong();
if (a == Integer.MIN_VALUE && b == -1) {
System.out.println(Integer.MAX_VALUE);
return;
}
boolean neg = (a < 0) != (b < 0);
long x = Math.abs(a), y = Math.abs(b), q = 0;
for (int k = 31; k >= 0; k--)
if ((y << k) <= x) {
x -= y << k;
q += 1L << k;
}
System.out.println(neg ? -q : q);
}
}