无需多次Popcount的置位比特位索引求和汇编实现问询

我需要实现置位比特位的索引求和功能。现有实现通过多次调用__popcnt64完成，但希望完全移除Popcount的使用，仅用汇编基础指令（算术/逻辑操作、条件移动/设置/跳转）实现，且不能使用AVX-512。该需求针对无硬件Popcount的架构，比如RISC-V或Nehalem之前的x86平台。

现有参考实现 #

// 计算置位比特位的索引和（OEIS A073642）
int A073642(uint64_t n)
{
    return __popcnt64(n & 0xAAAAAAAAAAAAAAAA) +
          (__popcnt64(n & 0xCCCCCCCCCCCCCCCC) << 1) +
          (__popcnt64(n & 0xF0F0F0F0F0F0F0F0) << 2) +
          (__popcnt64(n & 0xFF00FF00FF00FF00) << 3) +
          (__popcnt64(n & 0xFFFF0000FFFF0000) << 4) +
          (__popcnt64(n & 0xFFFFFFFF00000000) << 5);
}

替代实现：分治法（无Popcount依赖） #

我们可以用二进制分治思路，逐步累加每一组比特位的索引贡献，全程仅用逻辑与、移位、加法、乘法等基础指令：

int A073642(uint64_t n)
{
    uint64_t sum = 0;
    uint64_t mask;

    // 提取第0位（偶数位）的贡献
    mask = 0x5555555555555555;
    sum += (n & mask);

    // 提取第1位（奇数位）的贡献，移位后等价于乘以1
    mask = 0xAAAAAAAAAAAAAAAA;
    sum += ((n & mask) >> 1);

    // 提取第2-3位中高位的贡献，乘以2
    mask = 0x3333333333333333;
    sum += ((n >> 2) & mask) * 2;

    // 提取第4-7位中高位的贡献，乘以4
    mask = 0x0F0F0F0F0F0F0F0F;
    sum += ((n >> 4) & mask) * 4;

    // 提取第8-15位中高位的贡献，乘以8
    mask = 0x00FF00FF00FF00FF;
    sum += ((n >> 8) & mask) * 8;

    // 提取第16-31位中高位的贡献，乘以16
    mask = 0x0000FFFF0000FFFF;
    sum += ((n >> 16) & mask) * 16;

    // 提取第32-63位的贡献，乘以32
    sum += ((n >> 32) & 0xFFFFFFFF) * 32;

    return (int)sum;
}

实现原理 #

每个置位比特位的索引值可以拆分为多个2的幂次之和，我们通过分阶段处理不同比特组：

• 将64位划分为2位、4位、8位等大小的组，每组内的高位比特对应固定的索引增量倍数
• 用掩码提取对应组的比特，移位后乘以倍数，累加所有组的贡献得到最终总和

兼容性说明 #

该实现仅依赖通用基础指令，完全支持无硬件Popcount的架构：

• RISC-V全版本
• Nehalem之前的x86处理器（如Core 2 Duo）
• 其他无特殊指令集支持的通用CPU

内容的提问来源于stack exchange，提问作者user21777985