logo标签列表

寻找正整数2的质因数分解最有效的方法

coptimization
4

我正在使用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;
}
1
仅限正数？ - tadman
2
对于 int 类型，只有30个数字是2的正整数次幂，其他42亿个数字都不匹配。你可以很容易地使用 switch 在 O(1) 时间内完成这个操作。 - tadman
2
while(~(n&1) + 2)（三个运算符和一个测试）可以简化为 while((n&1) == 0)（一个运算符和一个测试）。 - Weather Vane
3
如果您可以使用内联汇编，某些 CPU 可以具有内置指令，例如BSF。 您的编译器可能也有内置函数可以调用而无需使用汇编，例如 GCC 中的__builtin_ffs，或者 MSVC 中的_BitScanForward。 - Rup
你可以通过先计算(x & ~(x-1))（这将产生2的幂），然后对结果进行二分查找，在O(log log n)时间内完成。 - n. m.
显示剩余10条评论
4个回答
4

那么最有效的方式是什么？使用（几乎）单个汇编指令怎么样？

根据GCC文档（也适用于Clang）：

内置函数：int __builtin_ctz(unsigned int x)

返回从最低位开始计算的尾随0比特数。 如果x为零，则结果未定义。

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更改为int:
unsigned Prime_Factor_Two(int x) {
    return x ? __builtin_ctz(x) : 0;
}
2
假设只有正数，并且您的系统使用2的补码表示法，您可以首先使用看似奇怪的x = x & -x操作来隔离最低有效位；然后，您可以使用log2(x)函数将其转换为集合位的位置。
下面是一个测试程序：
#include <stdio.h>
#include <math.h>

int main()
{
    int num, ans;
    do {
        printf("Enter a number: ");
        if (scanf("%d", &num) != 1 || num == 0) break;
        ans = (int)(log2(num & -num) + 0.5);
        printf("Answer is: %d\n", ans);
    } while (num > 0);
    return 0;
}

或者，为了避免使用浮点数和数学库，你可以使用位移循环（这也适用于负值和零值）：
int main()
{
    int num, ans;
    do {
        printf("Enter a number: ");
        if (scanf("%d", &num) != 1) break;
        num &= -num;
        for (ans = 0; num > 1; ans++) num >>= 1;
        printf("Answer is: %d\n", ans);
    } while (num > 0);
    return 0;
}

编辑: 当然，上述两种方法都是牵强附会且不必要的；一个简单的循环加上一个移位的单比特掩码就可以完成任务——除了值为零，因为它无论如何都可以被2整除（没有余数）无限次：

#include <stdio.h>

int main()
{
    int num, ans, bit;
    do {
        printf("Enter a number: ");
        if (scanf("%d", &num) != 1 || num == 0) break;
        for (ans = 0, bit = 1; !(num & bit); ans++) bit <<= 1;
        printf("Answer is: %d\n", ans);
    } while (1);
    return 0;
}
利用您的第二段代码（位移循环），您是否知道它是否比我发布的代码更有效，还是取决于编译器？是的，所有输入都将是正整数，并且编译器使用2的补码，这就是为什么在while循环中有 ~(n&1) + 2，这会生成0表示奇数（不再除以2），并且对于偶数则为1（继续）。感谢您迄今为止的帮助！ - ChemeComp
@ChemeComp 看编辑！我认为第三个解决方案比你的显着简单，但我不确定它会更快（如果有的话）。 - Adrian Mole
2
一种有趣的方法是使用二分查找最不重要的1位。甚至可以将其编码为明确无分支，尽管下面的示例并没有完全这样做。然而，这种方法需要您知道参数类型中值位的数量。
示例：
/*
 * Returns the number of factors of 2 in the prime factorization of the argument, or
 * returns -1 if the argument is 0.
 */
int factor_of_two_count(uint64_t in) {
    int result = -1;
    uint64_t bottom;
    
    bottom = (in & 0xffffffffu);
    in = bottom ? bottom : (in >> 32);
    result += !bottom * 32;

    bottom = (in & 0xffffu);
    in = bottom ? bottom : (in >> 16);
    result += !bottom * 16;

    bottom = (in & 0xffu);
    in = bottom ? bottom : (in >> 8);
    result += !bottom * 8;

    bottom = (in & 0xfu);
    in = bottom ? bottom : (in >> 4);
    result += !bottom * 4;

    bottom = (in & 0x3u);
    in = bottom ? bottom : (in >> 2);
    result += !bottom * 2;

    bottom = (in & 0x1u);
    result += !bottom;

    return result;
}

然而，对于比特位循环，它在随机数据上的表现可能会优于其他方式。这大致相当于六次通过这样的循环，而少于2%的所有随机64位输入需要那么多次。只有在分支预测问题严重影响比特位循环或输入的分布偏向于具有许多因子2的输入时，这才有可能成为获胜者。
0
有没有什么计算或分析的方法可以优化这段代码？
请参见使用模数除法和查找计算右侧连续零位数。
unsigned int v;  // find the number of trailing zeros in v
int r;           // put the result in r
static const int Mod37BitPosition[] = // map a bit value mod 37 to its position
{
  32, 0, 1, 26, 2, 23, 27, 0, 3, 16, 24, 30, 28, 11, 0, 13, 4,
  7, 17, 0, 25, 22, 31, 15, 29, 10, 12, 6, 0, 21, 14, 9, 5,
  20, 8, 19, 18
};
r = Mod37BitPosition[(-v & v) % 37];

作者解释：

上面的代码找到了在右侧末尾的零的数量，所以二进制0100会产生2。它利用了前32位位置值与37互质的事实，因此对37进行模数除法可以得到从0到36的唯一数字。这些数字可以使用一个小查找表映射到零的数量。它只使用了4个操作，但索引到表中并执行模数除法可能使其不适用于某些情况。

网页内容由stack overflow 提供, 点击上面的
可以查看英文原文，
原文链接