class Solution {
public:
    /**
     * @param dividend the dividend
     * @param divisor the divisor
     * @return the result
     */
    int divide(int dividend, int divisor) {
        // Write your code here
        if (divisor == 0) {
            if (dividend >= 0) {
                return INT_MAX;
            } else {
                return INT_MIN;
            }
        }

        if (dividend == 0) {
            return 0;
        }

        bool isNegative = false;

        if ((dividend > 0 && divisor < 0) || (dividend < 0 && divisor > 0)) {
            isNegative = true;
        }

        long dividendAbs = abs((long)dividend);
        long divisorAbs = abs((long)divisor);
        cout << dividendAbs << endl;
        cout << divisorAbs << endl;
        int result = 0;

        while (dividendAbs >= divisorAbs) {
            int shift = 0;
            while (dividendAbs >= (divisorAbs << shift)) {
                shift++;
                if (shift >= 32) {
                    return 2147483647;
                }
            }
            dividendAbs = dividendAbs - (divisorAbs << (shift-1));
            result = result + (1 << (shift-1));
        }

        if (isNegative) {
            return -result;
        } else {
            return result;
        }
    }
};

C语言里的左移和右移运算

先说左移,左移就是把一个数的所有位都向左移动若干位,在C中用<<运算符.例如:

int i = 1;

i = i << 2; //把i里的值左移2位

也就是说,1的2进制是000...0001(这里1前面0的个数和int的位数有关,32位机器,gcc里有31个0),左移2位之后变成000...0100,也就是10进制的4,所以说左移1位相当于乘以2,那么左移n位就是乘以2的n次方了(有符号数不完全适用,因为左移有可能导致符号变化,下面解释原因)

需要注意的一个问题是int类型最左端的符号位和移位移出去的情况.我们知道,int是有符号的整形数,最左端的1位是符号位,即0正1负,那么移位的时候就会出现溢出,例如:

int i = 0x40000000; //16进制的40000000,为2进制的01000000...0000

i = i << 1;

那么,i在左移1位之后就会变成0x80000000,也就是2进制的100000...0000,符号位被置1,其他位全是0,变成了int类型所能表示的最小值,32位的int这个值是-2147483648,溢出.如果再接着把i左移1位会出现什么情况呢?在C语言中采用了丢弃最高位的处理方法,丢弃了1之后,i的值变成了0.

左移里一个比较特殊的情况是当左移的位数超过该数值类型的最大位数时,编译器会用左移的位数去模类型的最大位数,然后按余数进行移位,如:

int i = 1, j = 0x80000000; //设int为32位

i = i << 33; // 33 % 32 = 1 左移1位,i变成2

j = j << 33; // 33 % 32 = 1 左移1位,j变成0,最高位被丢弃

在用gcc编译这段程序的时候编译器会给出一个warning,说左移位数>=类型长度.那么实际上i,j移动的就是1位,也就是33%32后的余数.在gcc下是这个规则,别的编译器是不是都一样现在还不清楚.

总之左移就是: 丢弃最高位,0补最低位

再说右移,明白了左移的道理,那么右移就比较好理解了.

右移的概念和左移相反,就是往右边挪动若干位,运算符是>>.

右移对符号位的处理和左移不同,对于有符号整数来说,比如int类型,右移会保持符号位不变,例如:

int i = 0x80000000;

i = i >> 1; //i的值不会变成0x40000000,而会变成0xc0000000

就是说,符号位向右移动后,正数的话补0,负数补1,也就是汇编语言中的算术右移.同样当移动的位数超过类型的长度时,会取余数,然后移动余数个位.

总之,在C中,左移是逻辑/算术左移(两者完全相同),右移是算术右移,会保持符号位不变.实际应用中可以根据情况用左/右移做快速的乘/除运算,这样会比循环效率高很多.

例子：

-5>>3=-1

1111 1111 1111 1111 1111 1111 1111 1011

1111 1111 1111 1111 1111 1111 1111 1111

其结果与 Math.floor((double)-5/(2*2*2)) 完全相同。

-5<<3=-40

1111 1111 1111 1111 1111 1111 1111 1011

1111 1111 1111 1111 1111 1111 1101 1000

其结果与 -5*2*2*2 完全相同。

5>>3=0

0000 0000 0000 0000 0000 0000 0000 0101

0000 0000 0000 0000 0000 0000 0000 0000

其结果与 5/(2*2*2) 完全相同。

5<<3=40

0000 0000 0000 0000 0000 0000 0000 0101

0000 0000 0000 0000 0000 0000 0010 1000

其结果与 5*2*2*2 完全相同。

-5>>>3=536870911

1111 1111 1111 1111 1111 1111 1111 1011

0001 1111 1111 1111 1111 1111 1111 1111

无论正数、负数，它们的右移、左移、无符号右移 32 位都是其本身，比如 -5<<32=-5、-5>>32=-5、-5>>>32=-5。

一个有趣的现象是，把 1 左移 31 位再右移 31 位，其结果为 -1。

0000 0000 0000 0000 0000 0000 0000 0001

1000 0000 0000 0000 0000 0000 0000 0000

1111 1111 1111 1111 1111 1111 1111 1111

对于10进制的数字，左移一位就是在末尾加上一个0,数值变大10倍。

同理，对于二进制数字，左移一位是在末尾加上一个0,数值变大2被。

所以 x << 3，x就变大 2^3 倍，就是 8*x

右移同理

一般情况下你要乘或者是除以数字是2的次方的话都可以用的

执行速度快

Even though we are not allowed to use *, / and %, but we can use minus and bit operator. My solution is based on such a fact that any number could be represented as a polynomial form, for example, 5 = 2^2 + 2^0, 78 = 2^5 + 2^3 + 2^2 + 2^1 and so on, any number could be represented as in this form. Now let’s consider the result quotient represented in this form, the good thing for thinking in this way is that, we now can make use of bit operator, a » 1 = a / 2 a«1 = a * 2. We keep multiply the divisor by 2 (divisor «= 1) until it reaches or larger than half the dividend (because if we multiply it by 2 again, it will be larger than the dividend), we then subtract this value from the dividend, and here, suppose this value is divisor * 2^k, then 2^k needs to be added into the final quotient result (remember we represent the quotient in a polynomial form), we keep doing this until the dividend becomes zero. Another good point of this method is that we could find the quotient in log time since we always multiply the divisor by 2 by2, in the log time the divisor will reaches the dividend. The following Java code is accepted by LeetCode OJ to pass this Divide Two Integers problem:

(2) the overflow issue is very annoying in the problem, be careful about things like INT_MAX, INT_MIN

(3) Again! Be very careful on the overflow issues here. The following are some test cases which you might be concerned about (I was incorrectly addressed):

// Input:   -2147483648, -1
// Output:  -2147483648
// Expected: 2147483647
//
// Input:   -2147483648, -1
// Output:  -2147483648
// Expected: 2147483647
//
//
// Input:   2147483647, -2147483648
// Output:  -1
// Expected: 0
//
// Input:   -2147483648, -2147483648
// Output:   0
// Expected: 1

If 50 / 9, here is the process of the solution:

Divide Two Integers

results matching ""

No results matching ""