5

我想编写一个函数，它采用 1 到 64 之间的 int，并返回一个适当的“位掩码”，其中 1 位与输入一样多。

我是这样开始的：

/** Computes a bitmaks */
private static long mask(final int bitsPerValue) {
    return (1L << bitsPerValue) - 1L;
}

但意识到它为 64 提供了错误的值：

(1L << 64) - 1L == 1L - 1L == 0

现在我有这个：

/** Computes a bitmaks */
private static long mask(final int bitsPerValue) {
    return (bitsPerValue == 64) ? -1 : ((1L << bitsPerValue) - 1L);
}

比较难看。并且条件可以改变控制流，因此它们比简单的算术运算更昂贵。我可以预先计算掩码并将它们放入静态数组中，但数组访问也比简单的算术运算更昂贵，甚至可能比条件更昂贵。

有没有一种合理的方式来写这个没有条件？这段代码每秒要运行无数次，所以它必须很快。

4

3 回答 3

5

这是一种不带条件的方法：

private static long mask(final int bitsPerValue) {
    return ((1L << bitsPerValue) - (bitsPerValue >> 6)) - 1L;
}

在 Java 中，1L << bitsPerValue 仅使用 的 6 个最低位，bitsPerValue这意味着使用 调用原始函数与使用bitsPerValue=64调用它是相同的bitsPerValue=0。我上面介绍的版本解决了这个问题：当 时bitsPerValue=64，表达式简化为

(1L - 1L) - 1L == -1L

现在，如果您真的要称其为“每秒无数次”，我认为最好的策略是对代码的所有变体进行基准测试，包括带有条件的代码和带有查找表的代码。

于 2012-01-23T11:18:39.923 回答
3

我试过：

long value = 0xffffffffffffffffl >>> (64 - i); // that's ef ef ef... el.

但这似乎给 i = 0 带来了问题。我对 Java 的抱怨再次没有无符号整数。以上在c中工作。鉴于“值”是无符号的，也许上面的方法可以在 Java 7 中使用。

但是，由于您不需要零，因此上述内容对您来说可以正常工作，即值 1 到 64。

于 2012-01-23T11:29:49.183 回答
0

恕我直言，添加要求具有 65 位值是不够的。我只是使用 OR 操作来产生价值，它不应该花费很多。像这样：

private static long mask(final int bitsPerValue) {
  long mask = 1;
  long value = 0;
  for (int i=0; i<bitsPerValue; i++ ) {
    value = value | mask;
    mask = mask << 1;
  }
  return value;
}

我看到您不想使用静态数组，但这将是最快的方式，它只使用 64 * 8 字节的内存。此外，我认为同时实现较小的内存占用和足够好的速度并不容易。因此，以防万一，最快的方法是：

long valarray[] = new long[64];

private static long[] generateValues() {
  long mask = 1;
  long value = 0;
  for (int i=0; i<64; i++ ) {
    value = value | mask;
    mask = mask << 1;

    valarray[i] = value;
  }
  return valarray;
}

private static long[] mask(final int bitsPerValue) {
  return valarray[bitsPerValue-1];
}

另一种可能的方法是将 BigInteger 用于最新的 64 '1' 位大小写。但我认为它不快也不丑。

于 2012-01-23T11:38:50.907 回答