2

我正在使用 Java，我正在编写一个国际象棋引擎。

我试图在一个字节中找到前 1 位的索引和最后 1 位的索引。

我目前在 Java 中使用 Long.numberOfTrailingZeros() （或类似的东西），并希望模拟该功能，除了字节。

会不会是这样的：

byte b = 0b011000101;
int firstOneBit = bitCount ((b & -b) - 1);

如果是这样，我将如何相对有效地实现 bitCount。我不介意好的解释，请不要只给我代码。

4

4 回答 4

3

使用包含 256 个条目的查找表。创建它：

unsigned int bitcount ( unsigned int i ) {
unsigned int r = 0;
while ( i ) { r+=i&1; i>>=1; } /* bit shift is >>> in java afair */
return r; 
}

这当然不需要很快，因为您最多可以执行 256 次来初始化您的表格。

于 2008-12-18T03:41:29.770 回答
2

正确的答案是大多数处理器都有一些特殊的指令来做这种事情（前导零、尾随零、1 的数量等）。x86 有 bsf/bsr，powerpc 有 clz，等等。希望 Integer.numberOfTrailingZeros 足够聪明来使用这些，但这可能是有机会在 Java 中使用这种特定于平台的函数的唯一方法（如果它甚至使用它们）。

Aggregate Magic Algorithms是另一个有一些解决这类问题的方法的地方，从显而易见的（查找表）到一些相当聪明的 SWAR 方法。但是我怀疑如果Java运行时对后者很聪明，它们都会输给 Integer(x).numberOfTrailingZeros() ；应该可以优化拳击并为 numberOfTrailingZeros 使用特定于平台的技术，如果两者都这样做，那将获胜。

只是为了完整起见，另一个出色的位敲击经典档案是旧的MIT HAKMEM集合（如果您的 PDP-6/10 汇编程序技能生锈，还有一个半现代化的C 版本）。

于 2008-12-18T04:30:10.327 回答
2 
/* Count Leading Zeroes */

static uint8_t clzlut[256] = {
  8,7,6,6,5,5,5,5,
  4,4,4,4,4,4,4,4,
  3,3,3,3,3,3,3,3,
  3,3,3,3,3,3,3,3,
  2,2,2,2,2,2,2,2,
  2,2,2,2,2,2,2,2,
  2,2,2,2,2,2,2,2,
  2,2,2,2,2,2,2,2,
  1,1,1,1,1,1,1,1,
  1,1,1,1,1,1,1,1,
  1,1,1,1,1,1,1,1,
  1,1,1,1,1,1,1,1,
  1,1,1,1,1,1,1,1,
  1,1,1,1,1,1,1,1,
  1,1,1,1,1,1,1,1,
  1,1,1,1,1,1,1,1,
  0,0,0,0,0,0,0,0,
  0,0,0,0,0,0,0,0,
  0,0,0,0,0,0,0,0,
  0,0,0,0,0,0,0,0,
  0,0,0,0,0,0,0,0,
  0,0,0,0,0,0,0,0,
  0,0,0,0,0,0,0,0,
  0,0,0,0,0,0,0,0,
  0,0,0,0,0,0,0,0,
  0,0,0,0,0,0,0,0,
  0,0,0,0,0,0,0,0,
  0,0,0,0,0,0,0,0,
  0,0,0,0,0,0,0,0,
  0,0,0,0,0,0,0,0,
  0,0,0,0,0,0,0,0,
  0,0,0,0,0,0,0,0
};

uint32_t clz(uint32_t val)
{
  uint32_t accum = 0;

  accum += clzlut[val >> 24];
  accum += (accum == 8 ) ? clzlut[(val >> 16) & 0xFF] : 0;
  accum += (accum == 16) ? clzlut[(val >>  8) & 0xFF] : 0;
  accum += (accum == 24) ? clzlut[ val        & 0xFF] : 0;

  return accum;     
}

解释：

这是通过将每个字节排列的前导零的数量存储为查找表来实现的。您使用字节值来查找该值的前导零的计数。由于该示例针对 unsigned int 执行此操作，因此您移动并屏蔽了四个单独的字节，并相应地累积查找。一旦我们找到设置的位，三元语句用于停止累积。累加值为 8、16 或 24 意味着到目前为止没有找到设置位。

此外，一些架构对此有硬件支持（作为指令）。汇编助记符通常称为“CLZ”或“BSR”。它们分别是“Countleading Zeroes”和“Bit Scan Reverse”的缩写。

于 2010-03-01T12:22:40.653 回答
0

如果您认为这Long.numberOfTrailingZeros很快（即 JIT 编译/优化以在可用时使用单个 ASM 指令），那么您为什么不能简单地做这样的事情：

max(8,Long.numberOfTrailingZeros(val))

其中 val 是转换为 Long 的字节值。这也是假设它max()可用并再次优化以使用 asm select 或 max 指令。

理论上，在支持它的机器上，这些操作可以被 JIT 编译成两条汇编指令。

于 2009-02-17T21:18:40.677 回答