Умножение двух 64 битных чисел и получение старших 64 бит

Question

Умножение двух 64 битных чисел и получение старших 64 бит

Илья Горбачев Знаток (339), открыт 5 дней назад

Необходимо умножить два 64 битных числа и сохранить старшие 64 бита полученного 128 битного результата в какую-либо переменную.

Моя реализация на Си:

 #include <stdio.h>

int main()
{
   unsigned long long a,b,c;
   c = a * b >> 64;
   printf("Число: %i", c);

   return 0;
}

Answer 1

#include <stdio.h>

int main()
{
unsigned long long a = 0xFFFFFFFFFFFFFFFF; // Пример значения для a
unsigned long long b = 0xFFFFFFFFFFFFFFFF; // Пример значения для b
unsigned __int128 result = (unsigned __int128)a * (unsigned __int128)b;
unsigned long long high_bits = (unsigned long long)(result >> 64);

printf("Старшие 64 бита: %llu\n", high_bits);

return 0;
}

Answer 2

Молодец. Ты сделал программу, превращающую случайный мусор из стека в тождественный ноль (т.к. 64-битная нижняя часть произведения сдвигается вправо на 64 бита). Но для этого совершенно не нужно умножение, просто печатай 0, и всё.

Если всё же нужно умножение, то:

1) Только для GCC/Clang: преобразуй один из операндов в unsigned __int128 и умножай, примерно как предложила нейросеть выше, только попроще.

 uint64_t a, b;
cin >> a >> b;
cout << uint64_t((unsigned __int128)a * b >> 64) << endl;

Лучше преобразовывать только один операнд, тогда если попадётся тупой компилятор, он всё равно сделает только 2 умножения, а не 3 и не 4, требуемых для полностью 128-битного умножения. Умный компилятор отследит, что числа - изначально 64-битные и обойдётся одним умножением.

2) Только для MSVC: используй intrinsic _umul128, принимающий два 64-битных множителя и указатель на 64-битную переменную для записи старших бит произведения.

 uint64_t a, b, p;
cin >> a >> b;
_umul128(a, b, &p); // младшие биты выбрасываем
cout << p << endl;

3) Полностью универсальное решение - побить оба операнда на 32-битные половинки и сделать 4 умножения (или 3 с оптимизацией Карацубы - см. Википедию) и соотв. количество сдвигов и сложений. Но это, конечно, дольше, чем задействовать встроенные механизмы, т.к. они переводятся компилятором в умножение двойной точности, поддерживаемое практически любым современным процом, а тут нам самим придётся выполнять закат Солнца вручную.

 uint64_t a, b;
cin >> a >> b;
uint64_t ah = a >> 32, al = a & UINT_MAX, bh = b >> 32, bl = b & UINT_MAX;
uint64_t ph = ah * bh, pl = al * bl,
         pm = (ah + al) * (bh + bl) - ph - pl
         p = ph + (pm >> 32) + ((pl >> 32) + (pm & UINT_MAX) >> 32);
cout << p << endl;

Здесь умножаем раздельно две старших и две младших половинки, Карацубой за 1 умножение вычисляем крест-накрест ah * bl + al * bh, а затем его старшие 32 бита суммируем с произведением старших половинок, а от младших вычисляем перенос, если есть.