好的,您的代码适用于 32 位整数,但让我们弄清楚 16 位的第一步,因为字母表没有 32 个字母。假设您的输入的二进制形式(用空格表示字节边界)是
i = ABCDEFGH IJKLMNOP
i >>> 1 = 0ABCDEFG HIJKLMNO
(i >>> 1) & 0x5555 = 0A0C0E0G 0I0K0M0O
所以第一个赋值中右手边的前两位是(AB - 0A)
。尝试以下组合:
A B AB-0A
0 0 00-00 = 00
1 0 10-01 = 01
0 1 01-00 = 01
1 1 11-01 = 10
因此,该结果的前两位为您提供了输入前两位中的位数。这同样适用于所有其他的两位组。
现在你再次做同样的事情。这次我们将考虑以 4 为底的输入,因此两个位形成下面符号的一个数字,我们可以使用完整的 32 位。
i = ABCD EFGH IJKL MNOP
i & 0x33333333 = 0B0D 0F0H 0J0L 0N0P
i >>> 2 = 0ABC DEFG HIJK LMNO
(i >>> 2) & 0x33333333 = 0A0C 0E0G 0I0K 0M0O
所以结果的前四位是(0A + 0B) = A + B
,对于任何其他四位组也是如此。所以在那一点上,每组四位包含原始输入中这四位的位数。
使用基数 16,下一步是
i = AB CD EF GH
i >>> 4 = 0A BC DE FG
i + (i >>> 4) = A(A+B) (B+C)(C+D) (D+E)(E+F) (F+G)(G+H)
(i + (i >>> 4)) & 0x0f0f0f0f = 0(A+B) 0(C+D) 0(E+F) 0(G+H)
这是有效的,因为每个四位组中的位计数总是小于四,因此添加两个这样的计数可以用四位表示而不会溢出。因此,加法不会从一个 4 位 base-16 数字溢出到另一个数字。此时,每个字节都包含输入的该字节的位数。其他算法可能会使用巧妙的乘法从那里继续,但您引用的代码也适用于后续步骤的加法。
i = A B C D
i >>> 8 = 0 A B C
i2 = i + (i >>> 8) = A (A+B) (B+C) (C+D)
i2 >>> 16 = 0 0 A (A+B)
i3 = i2 + (i2 >>> 1 = A (A+B) (A+B+C) (A+B+C+D)
i3 & 0x3f = 0 0 0 (A+B+C+D)
这再次利用了数字之间没有溢出的事实。