美文网首页
201. Bitwise AND of Numbers Rang

201. Bitwise AND of Numbers Rang

作者: exialym | 来源:发表于2016-11-16 12:30 被阅读15次

    Given a range [m, n] where 0 <= m <= n <= 2147483647, return the bitwise AND of all numbers in this range, inclusive.
    For example, given the range [5, 7], you should return 4.
    给出两个数字,把两个数字中所有的数相与。
    显然真的求所有数相与是不可能的,我们思考一下:
    对于两个数,如果他们不等,那意味着两个数及其之间一定包含一个偶数。
    一个偶数的末位一定为0。
    两个数如果不等,它之间的所有数的末位的与结果一定为0。
    两个数如果相等,他们与完还是他们自己。
    所以:
    这个问题相当于找到两个数二进制表示时,高位完全相同的那部分,剩下的部分置0。
    比如:
    1010101010001101101001
    1010100101010101010101
    结果就是:
    1010100000000000000000
    这样就好解决了,我们不断把两个数右移,两个数不等时offset 就增,相等时就意味着着找到了相同的高位:

    var rangeBitwiseAnd = function(m, n) {
        var offset = 0; 
        while (m != n) { 
            m >>= 1; 
            n >>= 1; 
            offset++; 
        } 
        return m << offset; 
    };
    

    相关文章

      网友评论

          本文标题:201. Bitwise AND of Numbers Rang

          本文链接:https://www.haomeiwen.com/subject/hxfrpttx.html