GuilinDev

Lc0029

05 August 2008

29 Divide Two Integers

原题概述

Given two integers 

1

dividend
and 
1

divisor
, divide two integers without using multiplication, division and mod operator.

Return the quotient after dividing 

1

dividend
by 
1

divisor
.

The integer division should truncate toward zero.

Example 1:

1
2

Input: dividend = 10, divisor = 3
Output: 3

Example 2:

1
2

Input: dividend = 7, divisor = -3
Output: -2

Note:

  • Both dividend and divisor will be 32-bit signed integers.
  • The divisor will never be 0.
  • Assume we are dealing with an environment which could only store integers within the 32-bit signed integer range: [−231, 231 − 1]. For the purpose of this problem, assume that your function returns 231 − 1 when the division result overflows.

题意和分析

不让用乘法除法和取余，来实现地板除法，那就只好用位操作了，参考了这里的解法。

代码

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

class Solution {
    public int divide(int dividend, int divisor) {
        boolean isNegative = (dividend < 0 && divisor > 0) || (dividend > 0 && divisor < 0) ? true : false;
        long absDividend = Math.abs((long) dividend);
        long absDivisor = Math.abs((long) divisor);
        long result = 0;
        while (absDividend >= absDivisor) {
            long temp = absDivisor, count = 1;
            while (temp <= absDividend) {
                temp <<= 1;
                count <<= 1;
            }
            result += count >> 1;
            absDividend -= temp >> 1;
        }
        return isNegative ? (int) ~result + 1 : (result > Integer.MAX_VALUE ? Integer.MAX_VALUE : (int) result);
    }
}
This site is open source. Improve this page.