统计字节数组中二进制1的数量

发表于 更新于 分类于

统计字节数组中 1 的数量, 常用的算法有如下几种：

1). 遍历算法

顾名思义， 遍历二进制位中的每一位，如果该位为1，那么数量加1
好处： 方法简单直接
坏处： 效率较低， 例如检测大小100M的字节数组（1MB = 1024KB = 1048576B = 8388608byte)，那么
需要进行大于8亿次的检查

2). 查表算法

针对于遍历算法的一个优化， 一般情况下， 对于一个特定的有限集合来说，集合元素的排列方式是有限的，对于一个有限长度的位数组来说， 他表示的二进制位的排列也是有限的

我们可以针对8位的二进制定制查表2^8,那么针对与100M数据来说，需要查询大约1亿次表
如果我们将8位提升到16位，那么表数量位2^16,(需要几百KB的字节空间), 查表所需次数为五千万次;
如果我们将16位提升到32位，那么表数量位2^32(需要十多个G的空间)，查询表数位两千五百万次

因此这也算是一种空间换时间的方式，但空间的消耗在32位时已到达一个难以忍受的地步；另外由于CPU的缓存限制，创建的表越大，那么CPU缓存所保存的内容占比就越小，从而缓存不明中率提高，也直接影响了算法的性能

3). variable-percision swar

汉明重量 通过利用位移和位运算，可以在常数时间内计算多个字节的汉明重量，并且不需要额外的内存。

1
2
3
4
5
6
7
8
9
10
11
12
public int swar(int i) {
   i = (i & 0x55555555) + ((i >> 1) & 0x555555555; 

   i = (i & 0x33333333) + ((i >> 2) & 0x33333333);

   i = (i & 0x0F0F0F0F) + ((i >> 4) & 0x0F0F0F0F);

   i = (i * 0x01010101) >> 24;

   return i;
}

我们以980480539(0x3A70F21B)作为计算数，

第一步计算，按两位为一组

值 分组
0x3A70F21B 00 11 10 10 01 11 00 00 11 11 00 10 00 01 10 11
0x2560A116 00 10 01 01 01 10 00 00 10 10 00 01 00 01 01 10
汉明重量 0 2 1 1 1 2 0 0 2 2 0 1 0 1 1 2

实际利用的是二进制为相加, ox55 = 0x01010101, i & 0x55555555计算的是偶数位的值，然后i向右移动一位，计算的该奇数位的值，然后相加就是这两位1的个数

第二步按4位一组计算

值 分组
0x2560A116 0010 0101 0110 0000 1010 0001 0001 0110
0x22304113 0010 0010 0011 0000 0100 0001 0001 0011
汉明重量 2 2 3 0 4 1 1 3

第三步按8位一组计算

值 分组
0x22304113 00100010 00110000 01000001 00010011
0x4030504 00000100 00000011 00000101 00000100
汉明重量 4 3 5 4

第四步，与0x0 1010101相乘， 将位和集中到高8位

实际如下：

1
2
3
4
5
6
7
8
                              00000100 00000011 00000101 00000100
                      0000100 00000011 00000101 00000100
            00000100 00000011 00000101 00000100
   00000100 00000011 00000101 00000100
 <--------------------------------------------->
                              00010000 00001100 00001001 00000100

高8位是所有的8位的汉明重量之和，结果位16

可以一次计算32位字节，甚至我们可以在一次循环中调用4次swar，这样就可以一次处理128位字节