c - 为正整数找到 2 的质因数分解的最有效方法

Question

我正在用 C 编写代码，并希望找出最有效的方法来确定 2 除以一个数字的次数；即 5 = 0, 8 = 3。我的问题是，在这段代码中，我利用按位运算来加速运行时，总体代码是 O(log N) ，我可以做任何计算或分析来优化此代码吗？

int Prime_Factor_Two(int n) {
    int k = 0;
    while(~(n&1) + 2){
        n = n >> 1;
        k +=1;
    }
    return k;
}

Answer 1

好的，你说的最有效的方法是什么？ (几乎)一条汇编指令怎么样？
来自 GCC 文档(也可以在 Clang 中找到):

Built-in Function: int __builtin_ctz (unsigned int x)

Returns the number of trailing 0-bits in x, starting at the least significant bit position. If x is 0, the result is undefined.

unsigned Prime_Factor_Two(unsigned x) {
    return x ? __builtin_ctz(x) : 0;
}

没有函数调用，没有循环，只有一个分支。如果您知道该数字是正数，您甚至可以将其删除并使用 __builtin_ctz(x) . __builtin_ctz()内置:

在 x86 上应该编译为单个汇编指令:TZCNT (如果支持)或 BSF .

在 ARM 上应该编译成两条指令:RBIT + CLZ .

在 PowerPC 上应该编译为 31 - CNTLZ(x & -x) (假设 32 位 unsigned )。

在其他平台上，可能有一些说明。

为了还支持负整数，您可以利用数字的二进制补码保留最低有效零这一事实，只需将类型从 unsigned 更改即可。至 int :

unsigned Prime_Factor_Two(int x) {
    return x ? __builtin_ctz(x) : 0;
}