05月27, 2016

别人家的面试题:统计“1”的个数(续)

原文:https://cooxa.com/post/count_bits.html

问题描述

给定一个非负整数 num,对于任意 i0 ≤ i ≤ num,计算 i 的二进制数中 1 的个数,将这些结果返回为一个数组。

解决方法

月影 写了一篇博客讨论这个问题的解法,总共给出了四种解法(参考 奇舞团博客月影的博客 ),算法复杂度从O(N*M)到O(N),非常巧妙,特别是总结出的等式: c( n & (n - 1) ) === c(n) - 1(其中 ccountBit 函数)。

早上在地铁上看到这个问题后,也思考了一下。

第一种想法是 直接统计二进制中 1 的个数,这个方法大部分同学都能想到,但是具体实现还是需要一定技巧(推荐月影的第二种方法);

第二种想法是 分奇偶考虑:

  1. n 为奇数时,n 的二进制中 1 的个数是等于 n-1 (偶数)的二进制中 1 的个数加 1,因为 n 就比 n-1多了最后一位 1
  2. n 为偶数时,n 通过不停的除以 2 (或者不停右移)可以得到一个没有质因数 2 的奇数 k,且 k < n的,并且 c(n) == c(k),比如 n=12,那么k == 3 == 12>>1>>1c(12) == c(1100) == 2 == c(3)
  3. 已知 n < 2 时,c(n) == n,通过归纳法是可以求出所有 0 ≤ i ≤ num1的个数;

代码如下:

// 分奇偶考虑
function even2odd(n) {
    while( n > 0 && !(n&1) && (n >>= 1) ) ;
    return n;
}
function countBits(n) {
    var ret = [];
    for(var i=0; i<=n; i++) {
        if( i < 2 ) {
            ret[i] = i;
        } else if( i&1 ) {
            ret[i] = ret[i-1] + 1;
        } else {
            ret[i] = ret[even2odd(i)];
        }
    }    
    return ret;
}

第三种想法是 分离最高位的 1

任何 n的二进制有 mbit 位,那么n 的二进制可以表示为1bbbbb的个数为 m-1),那么c(n) == 1 + c( n - Math.pow(2, m-1) ),就是 n 的二进制中 1 的位数为 n 的二进制数后面 m-1 位二进制数构成整数的二进制中 1 的位数加 1

已知 n<2 时,c(n) == n,通过归纳法是可以求出所有 0 ≤ i ≤ num1的个数;

代码实现如下:

function countBits(n) {
    var bit = 1, ret = [];
    for(var i=0; i<=n; i++) {
        if( i < 2 ) {
            ret[i] = i;
        } else if( i == (bit << 1) ) {
            ret[i] = 1;
            bit <<= 1;
        } else {
            // 刚开始的这里用的i-bit 月影 提示可以用异或运算 ^_^
            ret[i] = ret[i^bit] + 1;
        }
    }    
    return ret;
}

总结:
第二种方法的时间复杂度为O(N*M),M 是 N 的二进制数位数;
第三种方法的时间复杂度为O(N);

不知道有没有O(1)的算法去掉二进制后面连续的0?如果可以,那么第二种方法的时间复杂度也可以降到O(N) ^>_<^。

最后贴出 n = 500 的结果,可以看一下返回结果的规律(第三种想法就是在找结果的规律时想到的):

0,1,1,2,1,2,2,3,1,2,2,3,2,3,3,4,1,2,2,3,2,3,3,4,2,3,3,4,3,4,4,5,1,2,2,3,2,3,3,4,2,3,3,4,3,4,4,5,2,3,3,4,3,4,4,5,3,4,4,5,4,5,5,6,1,2,2,3,2,3,3,4,2,3,3,4,3,4,4,5,2,3,3,4,3,4,4,5,3,4,4,5,4,5,5,6,2,3,3,4,3,4,4,5,3,4,4,5,4,5,5,6,3,4,4,5,4,5,5,6,4,5,5,6,5,6,6,7,1,2,2,3,2,3,3,4,2,3,3,4,3,4,4,5,2,3,3,4,3,4,4,5,3,4,4,5,4,5,5,6,2,3,3,4,3,4,4,5,3,4,4,5,4,5,5,6,3,4,4,5,4,5,5,6,4,5,5,6,5,6,6,7,2,3,3,4,3,4,4,5,3,4,4,5,4,5,5,6,3,4,4,5,4,5,5,6,4,5,5,6,5,6,6,7,3,4,4,5,4,5,5,6,4,5,5,6,5,6,6,7,4,5,5,6,5,6,6,7,5,6,6,7,6,7,7,8,1,2,2,3,2,3,3,4,2,3,3,4,3,4,4,5,2,3,3,4,3,4,4,5,3,4,4,5,4,5,5,6,2,3,3,4,3,4,4,5,3,4,4,5,4,5,5,6,3,4,4,5,4,5,5,6,4,5,5,6,5,6,6,7,2,3,3,4,3,4,4,5,3,4,4,5,4,5,5,6,3,4,4,5,4,5,5,6,4,5,5,6,5,6,6,7,3,4,4,5,4,5,5,6,4,5,5,6,5,6,6,7,4,5,5,6,5,6,6,7,5,6,6,7,6,7,7,8,2,3,3,4,3,4,4,5,3,4,4,5,4,5,5,6,3,4,4,5,4,5,5,6,4,5,5,6,5,6,6,7,3,4,4,5,4,5,5,6,4,5,5,6,5,6,6,7,4,5,5,6,5,6,6,7,5,6,6,7,6,7,7,8,3,4,4,5,4,5,5,6,4,5,5,6,5,6,6,7,4,5,5,6,5,6,6,7,5,6,6,7,6,7,7,8,4,5,5,6,5,6,6,7,5,6,6,7,6,7,7,8,5,6,6,7,6

本文链接:https://75team.com/post/count_bits.html

-- EOF --

Comments

评论加载中...

注:如果长时间无法加载,请针对 disq.us | disquscdn.com | disqus.com 启用代理。