<<   比较两个分数的大小  |  首 页  |  结构体中一个成员的偏移量  >>

  • 判断一个整数的二进制位中有多少个1 - [技术相关]2006-10-21

    设整数i的二进制位长为n，1的个数为m：

    1.很直观的一种解法：i依次& 2^0 ~ 2^(n-1), 然后判断每次的结果。依此计1的个数。其时间复杂度为O(n)

    2.循环：对i做逻辑右移，判断右移后是否为0，0则停止。判断 & 1的结果；计数。该方法的时间复杂度介于O(n)～O(m)之间。目前看到的，最好的是3.中所用的方法：

    3.循环： x = x & ( x - 1 ); count++; 直到x为0为止。该方法的时间复杂度是O(m)





    Tags： 算法

    发表于 20:47:35 | 引用 0 | 编辑

评论

  • 解答在这里：http://www.cnblogs.com/dust/archive/2008/05/11/1192639.html

    should () 发表于 2008-05-11 21:27:16   [回复]

  • 博主可以问一下吗？第三种方法的原理是什么呢？不知道为什么这么做是对的，能给我解释一下吗？非常感谢，发到我邮箱可以吗yjdlut@qq.com，谢谢

    yjdlut () 发表于 2008-05-10 18:21:20   [回复]

  • 也是，最大不过64次循环

    should () 发表于 2006-10-24 13:16:20   [回复]

  • 32bit，64bit，没有什么效率好说的，觉得都是O(1)

    嵌入式不懂

    bit1 () 发表于 2006-10-24 10:20:05   [回复]

发表评论