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

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

发表于: 2012-10-25   作者:功夫小当家   来源:转载   浏览:
摘要: 今天研究了一个有趣的算法,而且还牵连了很多其他知识,这个问题倒是很简单。 问题:求一个数的二进制中1的个数   方法1:   public class YiWei { /* * 函数名:count1() 原理:n和1求&,当n的末位是1时,&结果是1;然后把n右移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类提供的字符串处理方法

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

  • 0

    开心

    开心

  • 0

    板砖

    板砖

  • 0

    感动

    感动

  • 0

    有用

    有用

  • 0

    疑问

    疑问

  • 0

    难过

    难过

  • 0

    无聊

    无聊

  • 0

    震惊

    震惊

版权所有 IT知识库 CopyRight © 2009-2015 IT知识库 IT610.com , All Rights Reserved. 京ICP备09083238号