计算二进制中1的个数-Java____[位运算思维]

需求

实现一个函数,输入一个整数,输出该数二进制表示中1的个数

---

实现方法解析

第一种:
Integer.toBinaryString(n)获得输入整数的二进制数,然后再用String类中的charAt(int i)方法依次取二进制字符串中每个字符与1进行比较,通过累加得到1的个数

---

第二种: 核心(n & (1 << i)) == (1 << i)

例:9的二进制为1001.
1001 & 1(1<<0) == 1(1<<0)

1001 & 10(1<<1) == 0

1001 & 100(1<2) == 0

1001 & 1000(1<<3) == 1000(1<<3)
通过for循环,将1依次向左移,和n相与,当n所在位是1的话,所得的值刚好等于1左移后的值.

---

第三种: 核心((n >> i) & 1) == 1

例:9的二进制为1001.
1001(1001>>0) & 1 == 1

100(1001>>1) & 1 == 0

10(1001>>2) & 1 == 0

1(1001>>3) & 1 == 1
通过for循环,将n依次向右移,和1相与,当所求值等于1,即n所在位是1

---

第四种: 核心n = (n-1) & n¹
被称作快速法.
通过消除最高位的1来计算所消除1的个数即为所求的1的个数.
n-1再和n相与,即可将最高位的1消除,直到等于0,即消除完了所有的1.

例:9的二进制为1001.
1001 - 1 & 1001 = 1000 & 1001 = 1
1 -1 & 1 = 0

---

完整代码演示

import java.util.Scanner;

/**
 * 需求: 实现一个函数,输入一个整数,输出该数二进制表示中1的个数
 * 
 * @author Clearlight
 *
 */
public class BinOneNum {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int num = sc.nextInt();
		binOneNum(num);// 不涉及算法,通过Java中提供的方法
		leftMoveOne(num);// 将1左移
		rightMoveOne(num);// 将n右移
		andNum(num);// 快速法
	}

	public static void binOneNum(int n) {
		String bin = Integer.toBinaryString(n);
		int oneNum = 0;
		for (int i = 0; i < bin.length(); i++) {
			if (bin.charAt(i) == '1') {
				oneNum++;
			}
		}
		System.out.println(bin);
		System.out.println(oneNum);
	}


	public static void leftMoveOne(int n) {
		int count = 0;
		// 比对每一位
		for (int i = 0; i < 32; i++) {
			if ((n & (1 << i)) == (1 << i)) {
				count++;
			}
		}
		System.out.println(count);
	}

	public static void rightMoveOne(int n) {
		int count = 0;
		for (int i = 0; i < 32; i++) {
			if (((n >> i) & 1) == 1) {
				count++;
			}
		}
		System.out.println(count);
	}
	
	public static void andNum(int n) {
		int count = 0;
		while(n!=0) {
			n = (n-1) & n;
			count++;
		}
		System.out.println(count);
	}
}

输出结果:

---

推荐几篇写的不错的关于此问题的文章

快速法详细分析


解答该题方法超全

---

1. 对于判断整数是不是2的整数次方也可以应用这种思想来求解.
   思路:如果整数是2的整数次方,那么这个整数的二进制表示中只有一个1,其余都为0,则可以通过n&(n-1)则为0,若为0,则该数为2的整数次方,否则不是2的整数次方. ↩︎