`
功夫小当家
  • 浏览: 182931 次
  • 性别: Icon_minigender_1
  • 来自: 北京
社区版块
存档分类
最新评论

求一个数的二进制中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类提供的字符串处理方法

分享到:
评论

相关推荐

Global site tag (gtag.js) - Google Analytics