你的位置:首页 > Java教程

[Java教程]求二进制数中1的个数


要求:求二进制数中1的个数

解法1:除、余操作
    最常见的方法:使用相除判断余数的方式来进行分析,若求模2 为1,则证明是1,求模2 为0,证明该二进制位置上面的0;
/** * 计算二进制中1的个数  O(log2V) * @param v 10进制的数字 * @return 二进制中1的个数 */ public static int Count(int v) { int num = 0; while(0 != v) {  if( 1 == v % 2)  {  num++;  }  v= v / 2;  } return num; }

  该算法的时间复杂度为 O(log2n)

 

解法二:使用位操作
        >>:右移运算符,将数往右移动,即去掉地位的数,高位补零。 如:v = v>>1,为,v向右移动一位
        为了代替上面的除操作,这里使用右移一位的方式代替,为了看最低位是否为1,使用“与”操作
/** * 使用位操作计算二进制中1的个数 *@param v 10进制的数字 * @return 二进制中1的个数 */ public static int Count2(int v) { int num = 0; while(0 != v) {  num += v & 0x01;   v = v >> 1;  //v右移一位  } return num; }

   虽然说,原理上,上面两种方式是一样的,但位操作比除、余操作的效率高了很多。但即使使用位操作,时间复杂度认为O(log2N)

解法3:
        基本思想:每次消除一个为1的二进制位
        通过每次让v和(v-1)进行相与即可消除最低位的1
/** * 与上面的类似,时间复杂度为O(M),M为v中1的个数 * @param v * @return */ public static int Count3(int v) { int num = 0; while(0 != v) {  v &= v-1;  num++;  } return num; }

    复杂度降低到了O(M),M为1的个数。

解法四:穷举法
        1、使用switch
        2、初始化数组,数组中的值是下标值的1的位数
这种方式是典型的空间换时间的方法,但是这种空间换时间的算法是不合理,需列举出所有的可能。


 

测试代码

public static void main(String[] args)  {    int num = CountOfOne.Count(11);    System.out.println("二进制中1的个数为:" + num);         num = CountOfOne.Count2(11);    System.out.println("二进制中1的个数为:" + num);        num = CountOfOne.Count3(11);    System.out.println("二进制中1的个数为:" + num);          }

 

 结果:

二进制中1的个数为:3
二进制中1的个数为:3
二进制中1的个数为:3