You need to enable JavaScript to run this app. 参考Java Long.bitCount位运算实现长整型非零四进制位的无循环计数
优惠活动
大模型
产品
解决方案
定价
更多

参考Java Long.bitCount位运算实现长整型非零四进制位的无循环计数

正确实现方案

核心逻辑调整思路

原方法的核心错误是直接照搬经典汉明重量的移位/掩码参数,没有对齐需求的统计单元:

  • 需求的最小统计单元是2位长度的四进制块,统计目标是块值非0的数量,而非块内1的总个数。
  • 实现的核心拆分两步:
    1. 把每个2位四进制块转换为独立的非零标记:块值非0则标记为1,块值为0则标记为0。这一步完成后,所有非零标记都是分散在独立bit位上的0/1值。
    2. 直接套用经典汉明重量的流水线求和逻辑,统计所有标记位的总数量,即为最终的非零四进制数位计数。

原错误代码的问题点

  • 第一步操作没有做非零标记转换,直接修改移位距离和掩码参数,无法区分块值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

相关产品推荐
方舟 Agent Plan

超全模态模型 × Harness 升级,最新支持 Deepseek-V4.1-Flash、GLM-5.3 系列、Doubao-Seedream-5.0-pro、Kimi-K3 (部分), 限时 9.9 元起

最近更新时间:2026.11.14 02:54:04