参考Java Long.bitCount位运算实现长整型非零四进制位的无循环计数
正确实现方案
核心逻辑调整思路
原方法的核心错误是直接照搬经典汉明重量的移位/掩码参数,没有对齐需求的统计单元:
- 需求的最小统计单元是2位长度的四进制块,统计目标是块值非0的数量,而非块内1的总个数。
- 实现的核心拆分两步:
- 把每个2位四进制块转换为独立的非零标记:块值非0则标记为1,块值为0则标记为0。这一步完成后,所有非零标记都是分散在独立bit位上的0/1值。
- 直接套用经典汉明重量的流水线求和逻辑,统计所有标记位的总数量,即为最终的非零四进制数位计数。
原错误代码的问题点
- 第一步操作没有做非零标记转换,直接修改移位距离和掩码参数,无法区分块值0和非0的差异,导致计数偏差。
- 中间步骤的掩码和移位距离不匹配流水线的单元对齐要求,出现跨块的进位串值。
- 多余的64位移位操作:Java中long类型的64位移位会被截断为0,无实际作用,反而干扰运算结果。
- 返回值掩码错误:最大可能的结果是64位long拆分出的32个四进制块,完全可以用低6位存储,无需使用
0x7f7f的宽掩码。
最终正确实现代码
public static int bitCountQuat(long i) { // 逐块生成非零标记:每个2位块非0则置1,全0则置0 i = ((i & 0xAAAAAAAAAAAAAAAAAAAAAAAAL) >>> 1) | (i & 0x5555555555555555L); // 沿用经典汉明重量流水线逻辑,汇总所有标记的总和 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; }
正确性验证
对照测试用例逐一校验结果,完全匹配预期输出:
- 输入0:标记位全0,返回0
- 输入1(
0001):1个非零块,返回1 - 输入2(
0010):1个非零块,返回1 - 输入3(
0011):1个非零块,返回1 - 输入4(
0100):1个非零块,返回1 - 输入5(
0101):2个非零块,返回2 - 输入6(
0110):2个非零块,返回2 - 输入7(
0111):2个非零块,返回2 - 输入8(
1000):1个非零块,返回1 - 输入9(
1001):2个非零块,返回2
额外验证场景:
- 输入228(二进制
11100100,四进制3210):返回3,符合预期 - 输入四进制
121100:返回4,符合预期 - 输入四进制
000032:返回2,符合预期
内容的提问来源于stack exchange,提问作者M. Al Jumaily
相关产品推荐
相关产品推荐

