当前位置:首页 > 开发 > 编程语言 > 编程 > 正文

求二进制数中1的个数

发表于: 2012-08-21   作者:周凡杨   来源:转载   浏览:
摘要: 解法一: 对于一个正整数如果是偶数,该数的二进制数的最后一位是 0 ,反之若是奇数,则该数的二进制数的最后一位是 1 。因此,可以考虑利用位移、判断奇偶来实现。   public int bitCount(int x){ int count = 0; while(x!=0){ if(x%2!=0){ /

解法一:

对于一个正整数如果是偶数,该数的二进制数的最后一位是 0 ,反之若是奇数,则该数的二进制数的最后一位是 1 。因此,可以考虑利用位移、判断奇偶来实现。

 

   public int bitCount(int x){

       int count = 0;

       while(x!=0){

        if(x%2!=0){  //判断奇偶数

           count++;

        }

         x = x>>>1;

       }

       return count;

    }

 

 

 

解法二:

知道了位移操作同样可以判断奇偶,且效率高于除法操作(“ % ”求余操作最后还是化为除法操作)那就可以用位移来代替上的求余运算。

      因为 x & 1 的结果为 1 0 ,为 1 的时候 count+=1 ,为 0 的时候 count+=0

则:

     If(x&1==1){

         count++;

     }

可简化为: count+ = x&1;

 

  public int bitCount2(int x){

          int count = 0;

          while(x!=0){

              count+ = x&1;

              x = x>>>1;

          }

          return count;

    }
 

 

解法三:

   正整数的二进制数最高位为 0 ,负整数和二进制数最高们为 1 ,则可利用左移、判断正负来实现 1 的个数的计算。

 

 

    public int bitCount3(int x){

          int count = 0;

          while(x!=0){

             if(x<0){

                count++;

             }

             x = x<<1;

          }

          return count;

    }

 

 

   

解法四:

前面的三种解法,运算的次数为二进制数的位数,时间复杂度仍为 O(log2 v) ,然而我们要计算 1 的个数,若让算法的运算次数只与“ 1 ”的个数有关,那复杂度就能进一步降低。

 

思想: x & (x-1) 可以消去 x 二进制数的最后一位 1

 

 

 public int bitCount4( int x )
 {

        int count = 0;

        while ( x != 0 )

        {

          x &= x - 1;

          count++;

        }

        return count;

}

 

 

解法五:

   JAVA JDK 库里 Integer 有个 bitCount 方法,其代码是这样实现的

 

   

 private int pop(int x)
  {

        x = x - ((x >> 1) & 0x55555555);

        x = (x & 0x33333333) + ((x >> 2) & 0x33333333);

        x = (x + (x >> 4)) & 0x0F0F0F0F;

        x = x + (x >> 8);

        x = x + (x >> 16);

        return x & 0x0000003F;

    }
 

==============================================================

 

二分法,两两一组相加,之后四个四个一组相加,接着八个八个,最后就得到各位之和了。

第一行是计算每两位中的 1 的个数 , 并且用该对应的两位来存储这个个数 ,
: 01101100 -> 01011000 , 即先把前者每两位分段 01 10 11 00 , 分别有 1 1 2 0 1, 用两位二进制数表示为 01 01 10 00, 合起来为 01011000.

第二行是计算每四位中的 1 的个数 , 并且用该对应的四位来存储这个个数 .
: 01101100 经过第一行计算后得 01011000 , 然后把 01011000 每四位分段成 0101 1000 , 段内移位相加 : 前段 01+01 =10 , 后段 10+00=10, 分别用四位二进制数表示为 0010 0010, 合起来为 00100010 .
下面的各行以此类推 , 分别计算每 8 ,16 ,32 位中的 1 的个数 .
0x55555555, 0x33333333, 0x0f0f0f0f 写成二进制数的形式就容易明白了 .

 

 

解法六:

   HAKMEM 算法

 

  private int pop2(int x) {

         int n;   

         n = (x >> 1) & 033333333333;   

         x = x - n;  

         n = (n >> 1) & 033333333333;  

         x = x - n;   

         x = (x + (x >> 3)) & 030707070707;  

         x = x%63; 

         return x;  

       }

 

首先是将二进制各位三个一组,求出每组中 1 的个数,然后相邻两组归并,得到六个一组的 1 的个数,最后很巧妙的用除 63 取余得到了结果。

因为 2^6 = 64 ,也就是说  x_0 + x_1 * 64 + x_2 * 64 * 64 = x_0 + x_1 + x_2 (mod 63) ,这里的等号表示同余

 

 

 

参考资料:

1. http://blog.csdn.net/justpub/article/details/2292823

2. http://www.inwap.com/pdp10/hbaker/hakmem/hacks.html#item169

3. http://tekpool.wordpress.com/category/bit-count/

4. gurmeet.net/puzzles/fast-bit-counting-routines/

5. http://www.tekpool.com/node/2675

6. http://hi.baidu.com/rangemq/blog/item/9f918c8f83997eecf11f367b.html

7. http://stackoverflow.com/questions/109023/best-algorithm-to-count-the-number-of-set-bits-in-a-32-bit-integer

8. http://mindprod.com/jgloss/bitcount.html

 

求二进制数中1的个数

  • 0

    开心

    开心

  • 0

    板砖

    板砖

  • 0

    感动

    感动

  • 0

    有用

    有用

  • 0

    疑问

    疑问

  • 0

    难过

    难过

  • 0

    无聊

    无聊

  • 0

    震惊

    震惊

编辑推荐
  <<编程之美>>中有这么个题目:对于一个字节的无符号整形变量,求其二进制表达形式
本文来自:http://www.cnblogs.com/graphics/archive/2010/06/21/1752421.html (下面这个图是原文
题目:对于一个字节的无符号整型变量,求其二进制表示中1的个数。 解法1:位操作法 (这里又细分成2
问题描述 任意给定一个32位无符号整数n,求n的二进制表示中1的个数,比如n = 5(0101)时,返回2,n
问题描述 任意给定一个32位无符号整数n,求n的二进制表示中1的个数,比如n = 5(0101)时,返回2,n
算法-求二进制数中1的个数 问题描述 任意给定一个32位无符号整数n,求n的二进制表示中1的个数,比如
2008-04-15 09:51 14641人阅读 评论(35) 收藏 举报 编程 读书 算法 面试 编译器 活动 《编程之美—
题目: 请实现一个函数,输入一个整数,输出该数二进制表示中1的个数。例如9(1001),有2个1。因此
《编程之美——微软技术面试心得》读书笔记 “求二进制数中1的个数” by ZelluX 由电子工业出版社博
题目描述: 输入一个整数,输出该数二进制表示中1的个数。其中负数用补码表示。 输入: 输入可能包
版权所有 IT知识库 CopyRight © 2009-2015 IT知识库 IT610.com , All Rights Reserved. 京ICP备09083238号