lcm всех чисел в массиве в C++

Question

Я наткнулся на этот фрагмент кода для вычисления наименьшего общего множителя из всех чисел в массиве, но не смог понять используемый алгоритм. Какая польза от __builtin_popcount здесь, который используется для подсчета количества установленных бит?

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;
}

Answer 1

Предоставленный вами отсканированный код содержит до 25 номеров. Для каждого подмножества чисел он вычисляет их LCM в pre[i].first и количество их в этом подмножестве в pre[i].second, Само подмножество представляется как битовая маска, поэтому для вычисления количества элементов в подмножестве, который использует фрагмент __builtin_popcount, Это не имеет ничего общего с вычислением LCM.

LCM вычисляется с использованием довольно стандартного подхода: LCM любого набора чисел равен их произведению, деленному на их GCD. Это именно то, что делает этот фрагмент, используя встроенную функцию GCD __gcd,

k&i а также k = k<<1 часть состоит в том, чтобы выяснить, какие числа принадлежат множеству, представленному битовой маской. Если вы не до конца понимаете, попробуйте посмотреть, что произойдет, если i = 0b11010, запустив этот цикл на листе бумаги или в отладчике. Вы заметите, что k&i условие будет выполнено на второй, четвертой и пятой итерации, а именно на позициях, в которых i имеет единицы в своем двоичном представлении.