JDK源码阅读-Integer.bitCount()

思路:将二进制的每一位依次与1作与运算, T=O(n)
,n为二进制位数。

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

        return count;
    } 
复制代码

优化解法

思路:将整数减一后与原数作与运算,达到将原二进制最低位"1"重置为"0"的目的。此时 T=O(n)
,但n为二进制中"1"的个数。

public int countBit(int i) {
        int count = 0;
        while (i > 0) {
            i = i & (i - 1); // 抹除二进制中最低位的1
            count++;
        }
        
        return count;
    }
复制代码

java内置的Integer.bitCount()解法

思路:先每两位一组统计二进制中的"1",然后每四位一组统计"1",接着是8位、16位和32位,最终再与 0x3f
作与运算,输出结果。如下图:

二进制                       十进制
1  0  1  1  0  0  1  1  0  1  1  1    10 11 00 11 01 11
 01    10    00    10    01    10     1  2  0  2  1  2
    / /         / /         / /        / /   / /   / /
    0011        0010        0011        3     2     3
                    /       /           3      /   /
    0011               0101             3        5
        /             /                  /      /
              1000                          8
          
              2871的二进制中的1的位数计算过程
复制代码

算法原型:

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;
}
复制代码

其中16进制数对应二进制为:

16进制 二进制
0x55555555 01010101010101010101010101010101
0x33333333 00110011001100110011001100110011‬
0x0f0f0f0f 00001111000011110000111100001111‬
0x00ff00ff 00000000111111110000000011111111
0x0000ffff 00000000000000001111111111111111
0x3f 00111111‬

优化思路:

  1. 对于第一步:两个bit计算1的数量: 0b11: 0b01 + 0b01 = 0b10 = 2, 0b10: 0b00 + 0b01 = 0b01 = 1
    。研究发现: 2=0b11-0b1,1=0b10-0b1
    ,可以减少一次位于计算: i = i - ((i >>> 1) & 0x55555555)
  2. 对于第二步:无优化
  3. 对于第三步:实际是计算每个byte中的1的数量,最多8(0b1000)个,占4bit,可以最后进行位与运算消位,减少一次&运算: i = (i + (i >>> 4)) & 0x0f0f0f0f
  4. 第四,五步:同上理由,可以最后消位。但是由于int最多32(0b100000)个1,所以这两步可以不消位,最后一步把不需要的bit位抹除就可以了: i & 0x3f

优化原型算法后,就得到java中内置的bitCount()方法:

public static int bitCount(int i) {
        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;
    }
复制代码

原文 

https://juejin.im/post/5c3969b76fb9a049a5712060

本站部分文章源于互联网,本着传播知识、有益学习和研究的目的进行的转载,为网友免费提供。如有著作权人或出版方提出异议,本站将立即删除。如果您对文章转载有任何疑问请告之我们,以便我们及时纠正。

PS:推荐一个微信公众号: askHarries 或者qq群:474807195,里面会分享一些资深架构师录制的视频录像:有Spring,MyBatis,Netty源码分析,高并发、高性能、分布式、微服务架构的原理,JVM性能优化这些成为架构师必备的知识体系。还能领取免费的学习资源,目前受益良多

转载请注明原文出处:Harries Blog™ » JDK源码阅读-Integer.bitCount()

赞 (0)
分享到:更多 ()

评论 0

  • 昵称 (必填)
  • 邮箱 (必填)
  • 网址