search

xiedaxia1hao / leetcode_pattern

1 stars 0 forks source link

Bit Manipulation #14

Open xiedaxia1hao opened 3 years ago

xiedaxia1hao commented 3 years ago

Github MarkDown Math Formula Editor:

https://www.codecogs.com/latex/eqneditor.php

xiedaxia1hao commented 3 years ago

两数相除

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

Return the quotient after dividing dividend by divisor.

The integer division should truncate toward zero, which means losing its fractional part. For example, truncate(8.345) = 8 and truncate(-2.7335) = -2.

Note:

Assume we are dealing with an environment that could only store integers within the 32-bit signed integer range: [−2^31, 2^31 − 1]. For this problem, assume that your function returns 2^31 − 1 when the division result overflows.

这题主要考察位运算。

首先我们要知道，all the integer can be represented with the sum of power of 2.

e.g.

从上面两个式子看，我们可以得知我们要求的，其实是括号里面的部分。

比如31/4，我们可以定一个参数名叫shift，使得31 >> shift >= divisor, 这样我们就知道我们找到了当前最大的可以把31除掉的2的power，就可以放到我们的result。

// let a = 31, b = 4
for(int x = 31; x >= 0; x--) {
    if((a >>> x) - b >= 0) {
        a -= b << x;
        res += 1 << x;
    }
}

我们知道当x循环到2的时候，31 >>> 2 = 31 / 2^2 = 7，7 > 4, 这时候我们知道了当把divisor << 2 = 16是不能超过31的最大的数, 所以我们将31减去16，进入下个循环，并把当前的2 ^ 2记入到res。

当a = 15的时候，x = 1的时候，15 >>> 1 = 7, 7 > 4, 这时候divisor << 1 = 8是当前不能超过15的最大的数，所以把当前的15减去8，进入下个循环，并把当前的2 ^ 1记入到res。

当a = 7的时候，x = 0的时候，7 >> 0 = 7，这时候divisor << 0 = 4是当前不能超过7的最大数，所以把当前的7减去4，进入下个循环，并把当前的2 ^ 0记入到res。

当x = 3的时候，哪怕x=0，我们也没有办法找到divisor << x成为当前不超过3的最大数了，因为4已经大于3了，这时候，循环结束。这时候我们就可以直接返回2^2 + 2^1 + 2^0 = 7了。

最后这题有一个edge case，当dividend == Integer.MIN_VALUE以及divisor == -1 时，直接相除会overflow，这个特殊逻辑我们直接在刚开始就判断，注意这里不能

完整代码:

public int divide(int dividend, int divisor) {
     if(dividend == Integer.MIN_VALUE && divisor == -1) {
         return (1 << 31) - 1; //Integer.MAX_VALUE; 不能写成 1 << 31 - 1！！！因为-的优先级大于 <<
     }

    int a = Math.abs(dividend), b = Math.abs(divisor);
    int res = 0;

    for(int x = 31; x >= 0; x--) {
        if((a >>> x) - b >= 0) {
            a -= b << x;
            res += 1 << x;
        }      
    }     
    return (dividend > 0) == (divisor > 0) ? res : -res;
}

Note:

>> is arithmetic shift right, >>> is logical shift right.

In an arithmetic shift, the sign bit is extended to preserve the signedness of the number.

e.g.

-2 represented in 8 bits would be 11111110，

-2 >> 1 = **1**1111110, 因为在arithmetic shift里，第一个字节是代表正负号的，右移会把原先代表负数的1补上。

而-2 >>> 1 = **0**1111110, 因为logical shift不考虑原先数字的正负号，都会用0补全。

image

https://www.youtube.com/watch?v=S9huMzNzR4M