1

这个问题出现在我老师的一次旧期末考试中。人们如何从逻辑上思考得出答案？

我熟悉位操作运算符以及十六进制和二进制之间的转换。

int whatisthis(int x) {
  x = (0x55555555 & x) + (0x55555555 & (x >>> 1)); 
  x = (0x33333333 & x) + (0x33333333 & (x >>> 2));
  x = (0x0f0f0f0f & x) + (0x0f0f0f0f & (x >>> 4));
  x = (0x00ff00ff & x) + (0x00ff00ff & (x >>> 8));
  x = (0x0000ffff & x) + (0x0000ffff & (x >>> 16));
return x;
}
4

1 回答 1

0

你没有忘记一些左移吗？

x = ((0x55555555 & x) <<< 1) + (0x55555555 & (x >>> 1));
x = ((0x33333333 & x) <<< 2) + (0x33333333 & (x >>> 2));
snip...

这将是位从左到右的反转。
您可以看到位是一起移动而不是一个一个地移动，这导致了 O(log2(nbit)) 的成本
（您在 5 个语句中反转 2^5=32 位）

它可能会帮助您重写二进制常量，以更好地理解它是如何工作的。

如果没有左移，那我帮不了你，因为加法会产生进位，我看不出任何明显的含义......

编辑：好的，有趣，所以这是用于计算设置为 1 的位数（也称为人口计数或 popcount）......这是一个 16 位的吱吱声 Smalltalk 快速测试

| f |
f := [:x |
    | y |
    y := (x bitAnd: 16r5555) + (x >> 1 bitAnd: 16r5555).
    y := (y bitAnd: 16r3333) + (y >> 2 bitAnd: 16r3333).
    y := (y bitAnd: 16r0F0F) + (y >> 4 bitAnd: 16r0F0F).
    y := (y bitAnd: 16r00FF) + (y >> 8 bitAnd: 16r00FF).
    y].
^(0 to: 16rFFFF) detect: [:i | i bitCount ~= (f value: i)] ifNone: [nil]

第一条语句处理每个位对。如果对中没有设置任何位，则生成 00，如果设置了单个位，则生成 01，如果设置了两个位，则生成 10。

00 -> 0+0 -> 00 = 0, no bit set
01 -> 1+0 -> 01 = 1, 1 bit set
10 -> 0+1 -> 01 = 1, 1 bit set
11 -> 1+1 -> 10 = 2, 2 bits set

所以它计算每对中的位数。

第二条语句处理 4 个相邻位的组：

0000 -> 00+00 -> 0000 0+0=0 bits set
0001 -> 01+00 -> 0001 1+0=1 bits set
0010 -> 10+00 -> 0010 2+0=2 bits set
0100 -> 00+01 -> 0001 0+1=1 bits set
0101 -> 01+01 -> 0010 1+1=2 bits set
0110 -> 10+01 -> 0011 2+1=3 bits set
1000 -> 00+10 -> 0010 0+2=2 bits set
1001 -> 01+10 -> 0011 1+2=3 bits set
1010 -> 10+10 -> 0100 2+2=4 bits set

所以，虽然第一步确实用这对中设置的位数替换了每对位，但第二步确实在每对中添加了这个计数......

接下来将处理每组 8 个相邻位，并将两组 4 中的位数相加...

于 2012-12-07T19:13:53.997 回答