美文网首页
338 counting bits

338 counting bits

作者: larrymusk | 来源:发表于2017-11-20 22:52 被阅读0次

倒过来想,一个数 * 2 就是把它的二进制全部左移一位,也就是说 1的个数是相等的。

那么我们可以利用这个结论来做。

res[i /2] 然后看看最低位是否为1即可(上面*2一定是偶数,这边比如15和14除以2都是7,但是15时通过7左移一位并且+1得到,14则是直接左移)

所以res[i] = res[i >>1] + (i&1)

int* countBits(int num, int* returnSize) {
    *returnSize = num+1;
    int * array = calloc(*returnSize, sizeof(int));
    
    for(int i=1;i<=num;i++){
        array[i] = array[i>>1] + (i&0x1);
    }

    return array;
}

相关文章

网友评论

      本文标题:338 counting bits

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