Getting everything ready for you…

Loading courses, problems and your progress. This takes just a moment.

0s

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

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

  1. Division is repeated subtraction — but subtracting b one at a time is too slow when a is 2^31 and b is 1.
  2. 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);
    }
}

Solve Divide Two Integers online · All practice problems