Java：将BigInteger除以3

Question

我需要一种将BigInteger（1000字节）除以3的快速方法。因为移位无法正常工作，所以我必须使用divideAndReminder（）。有更好/更快的选择吗？我经常使用它，因此jit会对其进行优化。

public byte[] div3(BigInteger big) {
  final List<Byte> al = new ArrayList();
  final BigInteger three = BigInteger.valueOf(3);

  while(!big.equals(BigInteger.Zero)){
    final BigInteger[] bigg = big.divideAndReminder(three);
    al.add(bigg[1].byteValueExact());
    big = bigg[0];
  }
  return toByteArray(al);
}

可以通过换挡更快地完成此操作吗？

Answer 1

虽然1000字节似乎无法证明达到极限（Schönhage基数转换），但一种方法是将BigInteger分解为易于处理的部分-3 ^ 20或3 ^ 40外观候选，然后转换为3从那里。

Answer 2

无符号除以3可乘以0xAA ... AA + 1，右移n + 1，其中n是乘法器中的位数，而n是8（或4）的倍数。

技巧是将乘数构造为n =股息的长度，四舍五入到8的倍数。我想这就是private exactDivideBy3()的作用。 [我猜乘数的构造从最大可能的0xAA ... AA开始，并向右移和或。]

当然，如果您假设BigInteger一次增加64位，则可以将n舍入为64的倍数。