java源码Integer.bitCount算法解析，分析原理（统计二进制bit位）

Caizhenhao 发布于2019-08-19 10:48 / 2720人阅读

摘要：算法统计整数的二进制表达式中的位为的位数汉明重量普通算法应该是最先想到的算法了，从最低位开始，一位一位地统计是否为，时间复杂度为，为总数。这时中存储了每两位的统计结果，可以进行两两相加，最后求和。

算法：统计整数的二进制表达式中的bit位为1的位数（汉明重量）

普通算法

public int bitCount(int num) {
    int count = 0;
    do {
        if ((num & 1) == 1) {
            count++;
        }
        num>>=1;
    } while (num > 0);
    return count;
}

应该是最先想到的算法了，从最低位开始，一位一位地统计是否为1，时间复杂度为O(n)，n为总bit数。

优化算法

public int countBit2(int num) {
    int count = 0;
    while (num > 0) {
        num = num & (num - 1);
        count++;
    }
    return count;
}

这个算法乍看很懵逼，但是仔细琢磨一下也能发现原理：n-1后，n的最低位的1被消除了，然后与n位与，n变为最低位1置为0后的新整数，如：

0b101100  减一  0b101011 最低位的1消除，0b101100 & 0b101011 = 0b101000

如此循环多少次就有多少个1，时间复杂度也是O(n)，但是这个n表示bit位为1的个数，总体是要比上一个优一点的。
当我们以为这已经是最优的算法了，事实却并非如此

Integer.bitCount

public static int bitCount(int i) {
    // HD, Figure 5-2
    i = i - ((i >>> 1) & 0x55555555);
    i = (i & 0x33333333) + ((i >>> 2) & 0x33333333);
    i = (i + (i >>> 4)) & 0x0f0f0f0f;
    i = i + (i >>> 8);
    i = i + (i >>> 16);
    return i & 0x3f;
}

最后,其实java的Integer类已经提供了一个方法来统计bit位（无符号右移，可以统计负数的），乍看之下，WTF?
原理：想象一下，当一列的1摆在我们人脑的面前，我们会怎么数？一个一个数，第一个的算法的原理。或者两个两个地数？本方法就是如此实现的。如下图：

             二进制                       十进制
 1  0   1  1   1  1   1  1   1  1     10 11 11 11 11
  01     10     10     10     10       1 2  2  2  2
               /            /           /    /
  01       0100           0100         1   4    4
                       /                     /
  01               1000                1      8
                /                          /
          1001                             9
          
              767的二进制中的1的位数计算过程

每两位bit为一组，分别统计有几个1，然后把结果存到这两个bit位上，如：11有2个1，结果为10，10替代11的存储到原位置。然后进行加法计算，把所有的结果加起来。加的过程中呢又可以两两相加，减少计算流程。

两个bit计算1的数量：0b11: 0b01 + 0b01 = 0b10 = 2, 0b10: 0b01 + 0b00 = 0b01 = 1，这样就清楚了。

算法实现如下：

首先整数i抹除左一位：i & 0x55555555，然后错位相加。(i >>> 1) & 0x55555555表示：左位移到右边，再把左位抹除，这样就可以计算两个bit位上1的个数了：0b1011=>0b0001 + 0b0101 = 0b0110左两位有1个1，右两位有2个1。

这时i中存储了每两位的统计结果，可以进行两两相加，最后求和。

过程：

0x55555555  ‭0b01010101010101010101010101010101‬
0x33333333  ‭0b00110011001100110011001100110011‬
0x0f0f0f0f  ‭0b00001111000011110000111100001111‬
0x00ff00ff  0b00000000111111110000000011111111
0x0000ffff  ‭0b00000000000000001111111111111111‬
0x3f        ‭0b00111111‬

0b11 11 11 11 11    (i & 0x55555555) + ((i >>> 1) & 0x55555555)  = 0b0101010101‬ + 0b0101010101 = 0b1010101010
0b10 10 10 10 10    (i & 0x33333333) + ((i >>> 2) & 0x33333333) = 0b1000100010 + 0b00100010 = 0b1001000100
0b10 01 00 01 00    (i & 0x0f0f0f0f) + ((i >>> 4) & 0x0f0f0f0f) = 0b1000000100 + 0b0100 = 0b1000001000
0b10 00 00 10 00    (i & 0x00ff00ff) + ((i >>> 8) & 0x00ff00ff) = 0b1000 + 0b10 = 0b1010
0b00 00 00 10 10    (i & 0x0000ffff) + ((i >>> 16) & 0x0000ffff) = 0b1010 + 0 = 0b1010
dec           10

算法原型：

public static int bitCount(int i) {
    i = (i & 0x55555555) + ((i >>> 1) & 0x55555555);
    i = (i & 0x33333333) + ((i >>> 2) & 0x33333333);
    i = (i & 0x0f0f0f0f) + ((i >>> 4) & 0x0f0f0f0f);
    i = (i & 0x00ff00ff) + ((i >>> 8) & 0x00ff00ff);
    i = (i & 0x0000ffff) + ((i >>> 16) & 0x0000ffff);
    return i;
}

时间复杂度O(1),可以，很ok了！但是写文章都要润色下的，别说算法了，然后优化过后的就是Integer中的实现了。
优化：

第一步：两个bit计算1的数量：0b11: 0b01 + 0b01 = 0b10 = 2, 0b10: 0b00 + 0b01 = 0b01 = 1。研究发现：2=0b11-0b1，1=0b10-0b1,可以减少一次位于计算：i = i - ((i >>> 1) & 0x55555555)

第二步：暂时没有好的优化方法

第三步：实际是计算每个byte中的1的数量，最多8（0b1000）个，占4bit，可以最后进行位与运算消位，减少一次&运算：i = (i + (i >>> 4)) & 0x0f0f0f0f

第四,五步：同上理由，可以最后消位。但是由于int最多32（0b100000）个1，所以这两步可以不消位，最后一步把不需要的bit位抹除就可以了：i & 0x3f

感悟：大道至简，看似复杂的算法，其实现原理却是我们大脑的简单思维逻辑

7    0b111
i = 7 - ((7>>>1) & 0x55555555) = 6 = 0b110
i = (6 & 0x33333333) + ((6 >>> 2) & 0x33333333) = 2 + 1 = 3 = 0b11
i = (3 + (i >>> 4)) & 0x0f0f0f0f = 3 & 0x0f0f0f0f = 3 = 0b11
i = 3 + (3 >>> 8) = 3 = 0b11
i = 3 + (3 >>> 16) = 3 = 0b11
i = 3 & 0x3f = 3

文章版权归作者所有，未经允许请勿转载,若此文章存在违规行为，您可以联系管理员删除。

转载请注明本文地址：https://www.ucloud.cn/yun/76489.html

Java HashMap 源码解析

摘要：所以利用哈希表这种数据结构实现具体类时，需要设计个好的函数，使冲突尽可能的减少其次是需要解决发生冲突后如何处理。源码剖析首先从构造函数开始讲，遵循集合框架的约束，提供了一个参数为空的构造函数与有一个参数且参数类型为的构造函数。本文章首发于个人博客，鉴于sf博客样式具有赏心悦目的美感，遂发表于此，供大家学习、批评。本文还在不断更新中，最新版可移至个人博客。? 继上一篇文章Java集合...

Aklman 2019-08-14 12:26 评论0 收藏0
大厂算法面试之leetcode精讲9.位运算

摘要：空间复杂度方法是否为最大的幂的约数思路最大的的幂为，判断是否是的约数即可。复杂度时间复杂度，一个整数统计二进制的复杂度，最坏的情况下是。大厂算法面试之leetcode精讲9.位运算视频教程（高效学习）:点击学习目录：1.开篇介绍2.时间空间复杂度3.动态规划4.贪心5.二分查找6.深度优先&广度优先7.双指针...

番茄西红柿 2021-11-29 10:50 评论0 收藏2637
Java集合之HashMap源码解析

摘要：之前，其内部是由数组链表来实现的，而对于链表长度超过的链表将转储为红黑树。非线程安全，即任一时刻可以有多个线程同时写，可能会导致数据的不一致。有时两个会定位到相同的位置，表示发生了碰撞。原文地址 HashMap HashMap 是 Map 的一个实现类，它代表的是一种键值对的数据存储形式。大多数情况下可以直接定位到它的值，因而具有很快的访问速度，但遍历顺序却是不确定的。 HashM...

lindroid 2019-08-15 18:12 评论0 收藏0
集合源码学习之路---hashMap(jdk1.8)

摘要：值得位数有的次方，如果直接拿散列值作为下标访问主数组的话，只要算法比较均匀，一般是很难出现碰撞的。但是内存装不下这么大的数组，所以计算数组下标就采取了一种折中的办法，就是将得到的散列值与数组长度做一个与操作。 hashMap简单介绍 hashMap是面试中的高频考点，或许日常工作中我们只需把hashMap给new出来，调用put和get方法就完了。但是hashMap给我们提供了一个绝佳...

kamushin233 2019-08-16 10:56 评论0 收藏0
源码|jdk源码之HashMap分析(一)

摘要：看属性有一个，所以是红黑树的节点。会在链表过长的时候，将其重构成红黑树，这个看后面的代码。如果是红黑树的话，调用红黑树的查找函数来最终找到这个节点。该位置为平衡树。但是这导致链表增长，需要触发链表重构成平衡树的判断逻辑。 hash表是应用最广泛的数据结构，是对键值对数据结构的一种重要实现。它能够将关键字key映射到内存中的某一位置，查询和插入都能达到平均时间复杂度为O(1)的性能。 ...

AndroidTraveler 2019-08-16 12:42 评论0 收藏0