最快的分解2的幂次方法是什么？

Question

我正在编写一些代码，希望能够快速地分解出二的幂。我注意到，当用二进制表示具有二的幂次方的数字时，有一个方便的特点：

27959296 = 0b1101010101010000000000000 = 110101010101 * 10000000000000 = 3413 * 2^13

如果我能将这些零移位，就会留下其他的因子。在查阅了谷歌、stackoverflow和其他一些地方以及使用Wolfram|alpha进行尝试后，我没有找到好的方法可以在不在每次操作时都要迭代除以2/移位的情况下完成此操作。如果我将其转换为字符串，我可能可以使用字符串操作将这些零分离出来。

我尝试使用对数规则来说明：

log base 2(27959296) = log(3413 * 2^13)/log(2) = 13+ log(3413)/log(2)

但我不知道如何区分13和24.73...的差异，后者是通过log(3413)/log(2)计算得出的“简单”答案。

最后有一种方法叫做numberOfTrailingZeros，可以给出一个好的答案，但我不知道它的内部工作原理以及速度有多快。

下面是该方法的SSCCE（从这里找到）：

import java.lang.*;

public class IntegerDemo {

   public static void main(String[] args) {

     int i = 27959296;
     System.out.println("Number = " + i);

     /* returns the string representation of the unsigned integer value 
     represented by the argument in binary (base 2) */
     System.out.println("Binary = " + Integer.toBinaryString(i));

     /* returns the number of zero bits following the lowest-order 
     ("rightmost") one-bit */
     System.out.print("Number of trailing zeros = ");
     System.out.println(Integer.numberOfTrailingZeros(i));  
   }
}

什么是最快的方法？我用位移方式可能走错了路吗？

- AncientSwordRage

---

计算机已经将数字以二进制形式存储，并可以轻松移除零位。我不会尝试除了位移和 numberOfTrailingZeros 之外的其他方法。但是，您有理由认为这是您程序中的瓶颈吗？ - Teepeemm

Answer 1

Integer.numberOfTrailingZeros 是非常快的，而 i >> Integer.numberOfTrailingZeros(i) 很可能是最快的替代方法。

- Louis Wasserman

---

你怎么知道它非常快？ - AncientSwordRage

肯定比将其转换为“字符串”以计算尾随零更好。 - rgettman

因为我已经完成了大量的高性能数学实用程序优化和基准测试？如果我没记错，Integer.numberOfTrailingZeros 可能实际上有一个内在的实现；我想我曾经试过复制/粘贴它的实现并得到了一个更慢的结果。 - Louis Wasserman

一个快速的 Caliper 基准测试得出以下结果：https://microbenchmarks.appspot.com/runs/293b36d3-d010-47c6-90a8-9aa056a2267a#r:scenario.benchmarkSpec.methodName - Louis Wasserman

移位操作比进行任何字符串转换/其他计算更快，因为只涉及一个汇编命令，并且所有CPU都支持移位寄存器（左移相当于乘法，右移相当于除法），而不使用其ALU（算术逻辑单元）进行任何计算。 - Evgheni Crujcov