位运算之两数相除

leetcode 上第29题两数相除,刚开始的时候我的思路是通过while 循环和加减法来实现,后来在编码实现的时候对于除数和被除数的符号相同时可以得出正确答案,但是符号不同时就会出现错误。在评论区看一些大佬的解题思路让我受益匪浅,其中我认为较好的一种思路是使用位运算,用左移去减,因为整数边界问题比较麻烦,所以改用负数计算。具体代码如下:

public int divide(int dividend, int divisor) {
		// ^ 是异或运算符,相同为0 不同为1
        boolean sign = (dividend > 0) ^ (divisor > 0);
        int result = 0;
        // 将整数全部转化为负数再进行运算
        if(dividend>0) {
            dividend = -dividend;
        }
        if(divisor>0) {
        	divisor = -divisor;
        }
        while(dividend <= divisor) {
            int temp_result = -1;
            int temp_divisor = divisor;
            // // 左移一位相当于乘以二,右移一位相当于除以二
            while(dividend <= (temp_divisor << 1)) {
                if(temp_divisor <= (Integer.MIN_VALUE >> 1))break;
                temp_result = temp_result << 1;
                temp_divisor = temp_divisor << 1;
            }
            dividend = dividend - temp_divisor;
            result += temp_result;
        }
        if(!sign) {
            if(result <= Integer.MIN_VALUE) return Integer.MAX_VALUE;
            result = - result;
        }
        return result;
    }

由于我对java 中位运算符不是很了解,就去查了一下资料,以下是关于java 中^、&、| 和位运算符的含义:

  • ^(异或运算符)
    ^ 是针对二进制的二目运算符。运算规则:两个二进制数值如果在同一位上相同,则结果中该位为0,否则为1,比如1011 ^ 0010 = 1001。

  • |(或运算符)
    | 是针对二进制的二目运算符。运算规则:两个二进制数值如果在同一位上至少有一个1,则结果中该位为1,否则为0,比如1011 | 0010 = 1011。

  • &(与运算符)
    &是是针对二进制的二目运算符。需要注意的是&&是java中判断条件之间表示“和”的标识符,&是一个二目运算符,两个二进制数值如果在同一位上都是1,则结果中该位为1,否则为0,可以认为两个都是true(1),结果也为true(1),比如1011 & 0110 = 0010。

  • 位运算符

    • >>x(常数): 向右移动x位(顶点在哪个方向就往哪个方向移动),如果该数是正数,则高位(最左边)补x个0,如果是负数,则最高位补x个1。*
    • <<x(常数): 向左移动x位(顶点在哪个方向就往哪个方向移动),无论正负数低位(最右边)都补x个0*
    • *<<<: 无该表示方式 **
    • >>>x(常数): 表示无符号右移x位,所谓无符号是与>>x对比,该操作在移动后,无论正负数高位(最左边)都补0。*

简单来说,左移一位相当于乘以x,右移一位相当于除以x.

上一篇:每天AC系列(十三):两数相除


下一篇:5-2