long 中非零四进制（基数 4）数字的个数？

Question

让我们从简单的开始。假设您想在其二进制表示中找到 long 中有多少个 1。例如，228₁₀ 中有多少个 1？二进制表示为 11100100₂。我们可以使用 Long.bitCount(228); 其中 returns 4.

现在，假设我们将两个位解释为一个四进制数字（最右边的两个位是第一个数字）：

00₂ = 0₄

01₂ = 1₄

10₂ = 2₄

11₂ = 3₄

因此，228₁₀ = 11100100₂ = 3210₄。目标是找到二进制表示中有多少个非零四进制数字。例如，3210₄ 产生 3、121100₄ 产生 4、000032₄ 产生 2，等等

Java 文档中 Long.bitCount(i); 方法的代码由以下内容给出：

public static int bitCount(long i) {
    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;
}

目标是找出二进制表示中有多少非零四进制数字，无需任何类型的循环，也无需使用Strings。我正在尝试操纵代码以使其适用于四元。这是我目前拥有的：

public static int bitCountQuat(long i) {
    i = i - ((i >>> 2) & 0x3333333333333333L);
    i = (i & 0x3333333333333333L) + ((i >>> 4) & 0x0f0f0f0f0f0f0f0fL);
    i = (i + (i >>> 8)) & 0x00ff00ff00ff00ffL;
    i = i + (i >>> 16);
    i = i + (i >>> 32);
    i = i + (i >>> 64);
    return (int) i & 0x7f7f;
 }

更多参考：Efficient Implementation of Hamming Weight.

这是从 0 到 9 的值：

Binary, desired output, current output
0000,   0,  0
0001,   1,  2
0010,   1,  4
0011,   1,  6
0100,   1,  6
0101,   2,  0
0110,   2,  2
0111,   2,  4
1000,   1,  4
1001,   2,  6

Answer 1

首先将所有非零四进制数字转换为 1 ...

i = (i & 0x5555555555555555L) | ((i >>  1) & 0x5555555555555555L));

...然后计算结果中的位数。

计算位数的一种方法是从那里继续

i = (i & 0x3333333333333333L) + ((i >>  2) & 0x3333333333333333L));
i = (i & 0x0f0f0f0f0f0f0f0fL) + ((i >>  4) & 0x0f0f0f0f0f0f0f0fL));
i = (i & 0x00ff00ff00ff00ffL) + ((i >>  8) & 0x00ff00ff00ff00ffL));
i = (i & 0x0000ffff0000ffffL) + ((i >> 16) & 0x0000ffff0000ffffL));
i = (i & 0x00000000ffffffffL) +  (i >> 32);

，这是您引用的维基百科文章中介绍的实施的后续步骤。

或者，您可以使用 Long.bitCount() 的（整个）实现，甚至 Long.bitCount() 本身用于位计数部分。它的变体比（完整的）维基百科版本的操作要少得多，可以用上面的快捷方式版本进行清洗。

long 中非零四进制（基数 4）数字的个数？

The number of non-zero quaternary (base 4) digits in a long?

java

binary

bit-manipulation