求一个数的二进制中1的个数 （n种解法详述）

今天研究了一个有趣的算法，而且还牵连了很多其他知识，这个问题倒是很简单。

问题：求一个数的二进制中1的个数

 

方法1：

 

public class YiWei {

	/*
	 * 函数名：count1() 原理：n和1求&，当n的末位是1时，&结果是1；然后把n右移1位，再判断。 
	 * 缺陷：只适用于正数，当n是负数时错误。
	 * 原因：移位操作的时候，没考虑符号位，会使负数变成正数
	 */
	public int count1(int n) {
		int count = 0; // 计数器
		while (n != 0) {
			if ((n & 1) != 0) {
				count++;
			}
			n = n >> 1;

		}
		return count;
	}
}

 

 

方法2：

 

public class YiWei {
	/*
	 * 函数名:count2() 
	 * 原理：设置一个变量flag = 1，让flag与n求& ，若结果不是0，
	 *       则计数器加1；flag左移1位，再比较
	 * 适用范围：正数，0，负数均可
	 */
	public int count2(int n) { // 这个方法，正数和负数都适用，

		int count = 0;
		int flag = 1;
		int i = 1;
		while (i <= 32) {   //移动32次
			if ((flag & n) != 0) {

				count++;
			}
			flag = flag << 1;
			i++;
		}
		if ((flag & n) > 0) {

			count++;
		}

		//System.out.println(Integer.toBinaryString(n) );
		//System.out.println(Integer.toBinaryString(n).length() ); 
		return count;
	}
}

   

 

方法3：

 

public class YiWei {	
	/*
	 * 函数名：count3() 
	 * 原理：若n最右边的1在第k个位置，那么n-1之后，第k个位置的数由1变0，k之后的由0变1，k之前的不变。
	 *       再把n-1和n求& ，会把该整数最右边的1变为0。因此有多少个1，就循环几次。
	 */
	public int count3(int n) {
		//System.out.println(Integer.toBinaryString(n) );
		//System.out.println(Integer.toBinaryString(n).length() ); 
		int count = 0;
		while (n != 0) {
			count++;
			n = n & (n - 1);
		}
		
		return count;
	}
}

 

 

 

方法4：

 

public class YiWei {
	/*
	 * count4() 使用java提供的方法 
	 * 原理：java提供了Integer到Binary的转换，求出的二进制字符串，存在StringBuilder里，
	 *       然后循环查找是否有0，如果有，则删除，最后的结果为全是1的字符串，求下length即可
	 */
	public int count4(int n) {
		int count;
		StringBuilder s = new StringBuilder(); // 注意用StringBuilder类型，可变字符串。
		s.append(Integer.toBinaryString(n));
		System.out.println(s);
		while (s.indexOf("0") != -1) {// 判断是否有0 存在，若有则删除字符串中所有的0
			s.deleteCharAt(s.indexOf("0"));
		}
		count = s.length();// 此时的字符串s里面存的全是1，求一下length即可知道1的个数
		return count;
	}
}

 

 

 

 这道题牵连到的问题:

  1.正数 ： 原码 = 反码= 补码

  2.负数 ： 反码 = （除符号位）按位取反，补码 = 反码 + 1

  3.0的补码是0，并且唯一

  4.+0的原码 = 0000 0000B

     - 0的原码 = 1000 0000B

  5. 与运算： n & （n-1） 的特点；n & flag 的结果；1&1=1，其他为0

  6. 移位操作：左移（*2） ，右移（/2）

  7.Integer类提供的toBinary方法

  8.StringBuilder类提供的字符串处理方法