-4

I came across this piece of code to compute least common factor of all numbers in an array but could not understand the algorithm used. What is the use of __builtin_popcount here which is used to count the number of set bits?

pair<long long, int> pre[200000];
long long a[25], N;

long long trunc_mul(long long a, long long b)
{
    return a <= INF / b ? a * b : INF;
}
void compute()
{
    int limit = 1 << N;
    limit--;
    for (int i = 1; i <= limit; i++)
    {
        long long lcm = 1;
        pre[i].second = __builtin_popcount(i);
        int k = 1;
        for (int j = N - 1; j >= 0; j--)
        {
            if (k&i)
            {
                lcm = trunc_mul(lcm / __gcd(lcm, a[j]), a[j]);

            }
            k = k << 1;
        }
        pre[i].first = lcm;
    }
    return;
}
4

1 回答 1

0

您提供的剪断代码最多有 25 个数字。对于每个数字子集，它将它们的 LCM 计算为pre[i].first，并将该子集中的数量计算为pre[i].second。子集本身表示为位掩码，因此要计算片段使用的子集中元素的数量__builtin_popcount。它与 LCM 的计算无关。

LCM 是使用相当标准的方法计算的：任何一组数字的 LCM 等于它们的乘积除以它们的 GCD。这正是这个片段所做的，使用内置的 GCD 函数__gcd。

和部分是找出哪些数字属于由位掩码表示的集合k&i。k = k<<1如果您不完全理解它，请尝试i = 0b11010通过在一张纸上或在调试器中运行此循环来查看 if 会发生什么。您会注意到k&i条件在第二次、第四次和第五次迭代时为真，正是i在其二进制表示中具有 1 的位置。

于 2016-03-31T22:07:14.860 回答