Integer.bitCount()理解

叁歲伎倆 2023-05-22 14:26 4阅读 0赞

# 环境说明 #

注意：Java使用补码来表示整数并参与运算。

环境：JDK1.8

# 源码解析 #

/**
     * Returns the number of one-bits in the two's complement binary
     * representation of the specified {@code int} value.  This function is
     * sometimes referred to as the <i>population count</i>.
     * 返回指定值的二进制补码表示形式中1的个数。
     *
     * @param i the value whose bits are to be counted
     * @return the number of one-bits in the two's complement binary
     *     representation of the specified {@code int} value.
     * @since 1.5
     */
    public static int bitCount(int i) {
        // HD, Figure 5-2
        i = i - ((i >>> 1) & 0x55555555); //计算两位中1的个数
        i = (i & 0x33333333) + ((i >>> 2) & 0x33333333);//计算四位中1的个数
        i = (i + (i >>> 4)) & 0x0f0f0f0f;//计算八位中1的数
        i = i + (i >>> 8);//计算十六位中1的个数
        i = i + (i >>> 16);//计算三十二位中1的个数
        return i & 0x3f;//0x3f的二进制{24个0}00111111，表示2^6-1=63。而int的最大长度是32位，所以1的个数最大为32，所以取低6位就够了。
    }

# 主要思路 #

## 思路说明 ##

bitcount的思想，与二路归并排序是类似的。

主要运用了“分治算法”，分治算法就是将一个大的问题划分为n个规模较小而结构相似的子问题。

这些子问题解决的方法都是类似的，解决掉这些小的问题之后，归并子问题的结果，就得到了“大”问题的解。

计算bitCount的思想总体上分两个阶段【依次：每4位、每8位、每16位、每32位】：

1、计算每两位中1的数量，将原来表示数值的二进制数变成每两位表示这两位中“1”数量的二进制数。

2、将这些数量加在一起。

## 源码中用到的十六进制和二进制的关系说明 ##

<table> 
 <tbody> 
  <tr> 
   <td>行数</td> 
   <td>十六进制</td> 
   <td>二进制</td> 
   <td>说明</td> 
  </tr> 
  <tr> 
   <td>第一行</td> 
   <td>0x55555555</td> 
   <td>01010101010101010101010101010101</td> 
   <td>计算两位中的1个数</td> 
  </tr> 
  <tr> 
   <td>第二行</td> 
   <td>0x33333333</td> 
   <td>00110011001100110011001100110011</td> 
   <td>计算四位中的1个数</td> 
  </tr> 
  <tr> 
   <td>第三行</td> 
   <td>0x0f0f0f0f</td> 
   <td>00001111000011110000111100001111</td> 
   <td>计算八位中的1个数</td> 
  </tr> 
  <tr> 
   <td>第四行、第五行</td> 
   <td>&nbsp;</td> 
   <td>&nbsp;</td> 
   <td>只需要关注二进制的后六位就可以了，因为32位int值不可能超过2^6-1（63）个“1”</td> 
  </tr> 
  <tr> 
   <td>第六行</td> 
   <td>&nbsp;</td> 
   <td>&nbsp;</td> 
   <td>最后在return语句中将第四行、第五行代码的垃圾数据过滤掉只保留最后6位，还是为了效率。</td> 
  </tr> 
 </tbody> 
</table>

大家参考上面，可以自己分析一下Long的bitcount。

/**
     * Returns the number of one-bits in the two's complement binary
     * representation of the specified {@code long} value.  This function is
     * sometimes referred to as the <i>population count</i>.
     * 返回指定值的二进制补码表示形式中1的个数。
     *
     * @param i the value whose bits are to be counted
     * @return the number of one-bits in the two's complement binary
     *     representation of the specified {@code long} value.
     * @since 1.5
     */
     public static int bitCount(long i) {
        // HD, Figure 5-14
        i = i - ((i >>> 1) & 0x5555555555555555L);
        i = (i & 0x3333333333333333L) + ((i >>> 2) & 0x3333333333333333L);
        i = (i + (i >>> 4)) & 0x0f0f0f0f0f0f0f0fL;
        i = i + (i >>> 8);
        i = i + (i >>> 16);
        i = i + (i >>> 32);
        return (int)i & 0x7f;
     }

参考资料：  
JDK源码  
备注：  
转载请注明出处：[https://blog.csdn.net/WSYW126/article/details/105591500][https_blog.csdn.net_WSYW126_article_details_105591500]  
作者：WSYW126

[https_blog.csdn.net_WSYW126_article_details_105591500]: https://blog.csdn.net/WSYW126/article/details/105591500