高效计算一个字节中所有的1的个数。问题：高效计算一个字节中所有的1的个数思路1：转成字符串再输出思路2：利用位的与计算方案3：查表法附：测试代码

65 阅读 0 评论 43 点赞

我是靠谱客的博主欢喜学姐，最近开发中收集的这篇文章主要介绍高效计算一个字节中所有的1的个数。问题：高效计算一个字节中所有的1的个数思路1：转成字符串再输出思路2：利用位的与计算方案3：查表法附：测试代码，觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

问题：高效计算一个字节中所有的1的个数

思路1：转成字符串再输出

这种方式效果肯定不好，因为字符串效率低，所以不推荐（代码略）

思路2：利用位的与计算

基本方法是对每一位进行与运行，如果是不是0，计数器就加1，这种效率还可以，代码如下：

public static int getOnes(byte b) {
	int count =  (b & 0b00000001) == 0 ? 0 : 1;
	count += (b & 0b00000010) == 0 ? 0 : 1;
	count += (b & 0b00000100) == 0 ? 0 : 1;
	count += (b & 0b00001000) == 0 ? 0 : 1;
	count += (b & 0b00010000) == 0 ? 0 : 1;
	count += (b & 0b00100000) == 0 ? 0 : 1;
	count += (b & 0b01000000) == 0 ? 0 : 1;
	count += (b & 0b10000000) == 0 ? 0 : 1;		
	return count;
}

实际上，代码还可以进一步优化，可以把变量count给省略，代码如下所示：

public static int getOnes(byte b) {
	return ((b & 0b00000001) == 0 ? 0 : 1) + 
			 ((b & 0b00000010) == 0 ? 0 : 1) + 
			 ((b & 0b00000100) == 0 ? 0 : 1) + 
			 ((b & 0b00001000) == 0 ? 0 : 1) + 
			 ((b & 0b00010000) == 0 ? 0 : 1) + 
			 ((b & 0b00100000) == 0 ? 0 : 1) + 
			 ((b & 0b01000000) == 0 ? 0 : 1) + 
			 ((b & 0b10000000) == 0 ? 0 : 1); 
}

实际上以上的代码的最外层括号是可以去掉的，但是了加上更清楚，而且在编辑的时候也会编译器也会去掉。

方案3：查表法

实际上一个字节只有256个值，如果我们建立一个数组，可以直接通过查表法直接找出结果。这是算法设计与分析中的经典的空间换时间的思路，这样的效率是最高的，数组如下所示。在调用的时候需要注意一点，如果直接使用一个字节访问数组，如 byte b = 128; 会报错。因为字节在访问时会被转换成 int 型，而在转换时由于高位的表示问题，当 b 大于127时，会变成负数。所以正确的访问方式是：ones[b&0xff]。

static int[] ones = {
        0, 1, 1, 2, 1, 2, 2, 3, 1, 2, 2, 3, 2, 3, 3, 4, 
        1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5, 
        1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5, 
        2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6, 
        1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5, 
        2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6, 
        2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6, 
        3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7, 
        1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5, 
        2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6, 
        2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6, 
        3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7, 
        2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6, 
        3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7, 
        3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7, 
        4, 5, 5, 6, 5, 6, 6, 7, 5, 6, 6, 7, 6, 7, 7, 8
        };

附：测试代码

	public static void main(String[] args) {
		for (int i = 0; i < 256; i++) {
			bts[i] = getOnes((byte) i);
			System.out.print(bts[i] + ", ");
		}
		System.out.println();
		for (int i = 0; i < 256; i++) {
			System.out.print(ones[i] + ", ");
		}
	}

0, 1, 1, 2, 1, 2, 2, 3, 1, 2, 2, 3, 2, 3, 3, 4, 1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5, 1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5, 2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6, 1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5, 2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6, 2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6, 3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7, 1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5, 2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6, 2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6, 3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7, 2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6, 3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7, 3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7, 4, 5, 5, 6, 5, 6, 6, 7, 5, 6, 6, 7, 6, 7, 7, 8, 
0, 1, 1, 2, 1, 2, 2, 3, 1, 2, 2, 3, 2, 3, 3, 4, 1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5, 1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5, 2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6, 1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5, 2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6, 2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6, 3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7, 1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5, 2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6, 2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6, 3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7, 2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6, 3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7, 3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7, 4, 5, 5, 6, 5, 6, 6, 7, 5, 6, 6, 7, 6, 7, 7, 8,