转载

别人家的面试题：统计“1”的个数

小胡子哥@Barret李靖给我推荐了一个写算法刷题的地方 leetcode.com ，没有 ACM 那么难，但题目很有趣。而且据说这些题目都来源于一些公司的面试题。好吧，解解别人公司的面试题其实很好玩，既能整理思路锻炼能力，又不用担心漏题 ╮(╯▽╰)╭。

长话短说，让我们来看一道题：

统计“1”的个数

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

例如：

当 num = 5 时，返回值为 [0,1,1,2,1,2]。

/**  * @param {number} num  * @return {number[]}  */ var countBits = function(num) {     //在此处实现代码 };

解题思路

这道题咋一看还挺简单的，无非是：

实现一个方法 countBit ，对任意非负整数 n，计算它的二进制数中“1”的个数
循环 i 从 0 到 num，求 countBit(i) ，将值放在数组中返回。

JavaScript中，计算 countBit 可以取巧：

function countBit(n){     return n.toString(2).replace(/0/g,"").length; }

上面的代码里，我们直接对 n 用 toString(2) 转成二进制表示的字符串，然后去掉其中的0，剩下的就是“1”的个数。

然后，我们写一下完整的程序：

版本1

function countBit(n){   return n.toString(2).replace(/0/g,"").length; }  function countBits(nums){   var ret = [];   for(var i = 0; i <= nums; i++){     ret.push(countBit(i));   }    return ret; }

上面这种写法十分讨巧，好处是 countBit 利用 JavaScript 语言特性实现得十分简洁，坏处是如果将来要将它改写成其他语言的版本，就有可能懵B了，它不是很通用，而且它的性能还取决于 Number.prototype.toString(2) 和 String.prototype.replace 的实现。

所以为了追求更好的写法，我们有必要考虑一下 countBit 的通用实现法。

我们说，求一个整数的二进制表示中 “1” 的个数，最普通的当然是一个 O(logN) 的方法：

function countBit(n){     var ret = 0;     while(n > 0){         ret += n & 1;         n >>= 1;     }     return ret; }

所以我们有了版本2

这么实现也很简洁不是吗？但是这么实现是否最优？建议此处思考10秒钟再往下看。

更快的 countBit

上一个版本的 countBit 的时间复杂度已经是 O(logN) 了，难道还可以更快吗？当然是可以的，我们不需要去判断每一位是不是“1”，也能知道 n 的二进制中有几个“1”。

有一个诀窍，是基于以下一个定律：

对于任意 n， n ≥ 1，有如下等式成立：

countBit(n & (n - 1)) === countBit(n) - 1

这个很容易理解，大家只要想一下，对于任意 n，n - 1 的二进制数表示正好是 n 的二进制数的最末一个“1”退位，因此 n & n - 1 正好将 n 的最末一位“1”消去，例如：

6的二进制数是 110， 5 = 6 - 1 的二进制数是 101， 6 & 5 的二进制数是 110 & 101 == 100
88的二进制数是 1011000， 87 = 88 - 1 的二进制数是 1010111， 88 & 87 的二进制数是 1011000 & 1010111 == 1010000

于是，我们有了一个更快的算法：

版本3

function countBit(n){     var ret = 0;     while(n > 0){         ret++;         n &= n - 1;     }     return ret; }  function countBits(nums){   var ret = [];   for(var i = 0; i <= nums; i++){     ret.push(countBit(i));   }    return ret; }

上面的 countBit(88) 只循环 3 次，而“版本2”的 countBit(88) 却需要循环 7 次。

优化到了这个程度，是不是一切都结束了呢？从算法上来说似乎已经是极致了？真的吗？再给大家 30 秒时间思考一下，然后再往下看。

countBits 的时间复杂度

考虑 countBits ，上面的算法：

“版本1” 的时间复杂度是 O(N*M)，M 取决于 Number.prototype.toString 和 String.prototype.replace 的复杂度。
“版本2” 的时间复杂度是 O(N*logN)
“版本3” 的时间复杂度是 O(N*M)，M 是 N 的二进制数中的“1”的个数，介于 1 ~ logN 之间。

上面三个版本的 countBits 的时间复杂度都大于 O(N)。那么有没有时间复杂度 O(N) 的算法呢？

实际上，“版本3”已经为我们提示了答案，答案就在上面的那个定律里，我把那个等式再写一遍：

countBit(n & (n - 1)) === countBit(n) - 1

也就是说，如果我们知道了 countBit(n & (n - 1)) ，那么我们也就知道了 countBit(n) ！

而我们知道 countBit(0) 的值是 0，于是，我们可以很简单的递推：

版本4

function countBits(nums){     var ret = [0];     for(var i = 1; i <= nums; i++){         ret.push(ret[i & i - 1] + 1);     }     return ret; }

原来就这么简单，你想到了吗 ╮(╯▽╰)╭

以上就是所有的内容，简单的题目思考起来很有意思吧？程序员就应该追求完美的算法，不是吗？

这是 leetcode 算法面试题系列的第一期，下一期我们讨论另外一道题，这道题也很有趣： 判断一个非负整数是否是 4 的整数次方 ，别告诉我你用循环，想想更巧妙的办法吧~

原文 https://www.h5jun.com/post/counting-bits.html

正文到此结束

所属分类：编程技术

本文标签： 快的 java HTML 程序员时间代码 JavaScript ACE https http ip 统计
版权声明： 本文为互联网转载文章，出处已在文章中说明(部分除外)。如果侵权，请联系本站长删除，谢谢。
本文海报： 生成海报一生成海报二

其他链接

关于本站

本站定位：个人技术类博客

本站作用：写博客、记日志、闲聊扯淡鼓捣技术。

问题交流

别人家的面试题：统计“1”的个数

统计“1”的个数

例如：

解题思路

更快的 countBit

countBits 的时间复杂度

热门推荐

相关文章

说给你听

本文目录

随机标签

书籍教程

近期评论

网站信息

其他链接

关于本站

问题交流