更快地找出一个数字是否以2开头的方法？

Question

在Java中，如果给定的整数是以数字2开头的，而不需要将数字转换成字符串，那么最快的方法是什么？

String.valueOf(number).charAt(0) == '2'

Answer 1

我很想做这样的事情：

  x = Math.abs(x);
  if ( ((int) Math.floor(x / Math.pow(10, Math.floor(Math.log10(x))))) == 2 )
  {
     ... // x equals 2
  }

Answer 2

我将各种解决方案相互对立：

public class FirstDigit
{
  static int digit;
  @GenerateMicroBenchmark public void string() {
    for (int i = 200_000_000; i < 400_000_000; i += 999961)
      digit = Integer.toString(i).charAt(0);
  }
  @GenerateMicroBenchmark public void math() {
    for (int i = 200_000_000; i < 400_000_000; i += 999961) {
      digit = (int) floor(i / pow(10, floor(log10(i))));
    }
  }
  @GenerateMicroBenchmark public void divide() {
    for (int i = 200_000_000; i < 400_000_000; i += 999961) {
      int x = i;
      while (x > 10) x /= 10;
      digit = x;
    }
  }
  @GenerateMicroBenchmark public void brokenDivide() {
    for (int i = 200_000_000; i < 400_000_000; i += 999961) {
      int x = i;
      while (x > 10) x >>= 3;
      digit = x;
    }
  }
  @GenerateMicroBenchmark public void bitTwiddling() {
    for (int i = 200_000_000; i < 400_000_000; i += 999961) {
      digit = i/powersOf10[log10(i)];
    }
  }
  @GenerateMicroBenchmark public boolean avoidDivide() {
    boolean b = true;
    for (int i = 200_000_000; i < 400_000_000; i += 999961) {
      b ^= firstDigitIsTwo(i);
    }
    return b;
  }


  private static final int[] log256 = new int[256];
  static {
    for (int i = 0; i < 256; i++) log256[i] = 1 + log256[i / 2];
    log256[0] = -1;
  }
  private static int powersOf10[] = {1, 10, 100, 1000, 10_000, 100_000,
    1_000_000, 10_000_000, 100_000_000, 1_000_000_000};

  public static int log2(int v) {
    int t, tt;
    return ((tt = v >> 16) != 0)?
        (t = tt >> 8) != 0 ? 24 + log256[t] : 16 + log256[tt]
      : (t = v >> 8) != 0 ? 8 + log256[t] : log256[v];
  }
  public static int log10(int v) {
    int t = (log2(v) + 1) * 1233 >> 12;
    return t - (v < powersOf10[t] ? 1 : 0);
  }

  static final int [] limits = new int[] {
    2_000_000_000, Integer.MAX_VALUE,
    200_000_000, 300_000_000-1,
    20_000_000, 30_000_000-1,
    2_000_000, 3_000_000-1,
    200_000, 300_000-1,
    20_000, 30_000-1,
    2000, 3000-1,
    200, 300-1,
    20, 30-1,
    2, 3-1,
  };
  public static boolean firstDigitIsTwo(int v) {
    for ( int i = 0; i < limits.length; i+= 2) {
      if ( v > limits[i+1] ) return false;
      if ( v >= limits[i] ) return true;
    }
    return false;
  }
}

以及结果：

Benchmark                   Mode Thr    Cnt  Sec         Mean   Mean error    Units
FirstDigit.avoidDivide     thrpt   1      3    5     2324.271       58.145 ops/msec
FirstDigit.bitTwiddling    thrpt   1      3    5      716.453        6.407 ops/msec
FirstDigit.brokenDivide    thrpt   1      3    5      578.259        7.534 ops/msec
o.s.FirstDigit.divide      thrpt   1      3    5      125.509        2.323 ops/msec
o.s.FirstDigit.string      thrpt   1      3    5       78.233        2.030 ops/msec
o.s.FirstDigit.math        thrpt   1      3    5       14.226        0.034 ops/msec

• 数学方法显然是个失败者
• string方法比math方法快六倍
• 最简单的除法算法比这个算法快60%
• OldCurmudgeon的比特旋转算法比除法快六倍
• OldCurmudgeon的特殊casedavoidDivide方法（它直接给出是/否的答案，不像所有其他方法，它实际上决定了第一个数字）比位加法算法快三倍，是无可争议的赢家
• 对于诊断，我还提供了一个brokenDividealgo。它不是除以10，而是除以3，给出了错误的答案。重点是强调divide算法的瓶颈是：brokenDivide比divide快4.6倍，比比特旋转慢0.2倍

请注意，我使用了相当大的数字；相对速度随震级而变化。

Answer 3

如果您想避免将其转换为字符串，您可以继续除以10以找到最有效的数字：

int getMostSignificantDigit(int x)
{
    // Need to handle Integer.MIN_VALUE "specially" as the absolute value can't
    // represented. We can hard-code the fact that it starts with 2 :)
    x = x == Integer.MIN_VALUE ? 2 : Math.abs(x);
    while (x >= 10)
    {
        x = x / 10;
    }
    return x;
}

我不知道这是否会比Husman的log/pow方法更快。