Умножение очень больших шестнадцатеричных чисел и их печать на C

Я хочу умножить 2 очень больших шестнадцатеричных числа и распечатать их, например:

28B2D48D74212E4F x 6734B42C025D5CF7 = 1068547cd3052bbe5688de35695b1239

Поскольку я ожидал, что это будет очень большое число, я использовал тип unsigned long long int:

unsigned long long int x = 0x28B2D48D74212E4F;   
unsigned long long int y = 0x6734B42C025D5CF7; 

и напечатайте умножение следующим образом:

fprintf(stdout, "%llx\n",  x*y);

То, что я получаю, это ровно половина ожидаемого результата:

5688de35695b1239

Почему он обрезает его ровно до половины? Есть ли что-то большее, чем unsigned long long?


person cheshire    schedule 21.12.2019    source источник
comment
Ваш unsigned long long int, очевидно, является 64-битным числом. Проверьте еще раз ULLONG_MAX, вы, вероятно, ошиблись.   -  person Martin Heralecký    schedule 22.12.2019
comment
попытался проверить, превышает ли вывод значение ULLONG_MAX — как вы это сделали? Вывод намного больше, чем максимальный размер unsigned long long в любой системе, о которой я знаю, вы не можете сравнивать с ним, так как он переполняется в арифметике.   -  person UnholySheep    schedule 22.12.2019
comment
Ожидаете ли вы, что unsigned long long будет 128-битным на вашей платформе? Что это будет за платформа?   -  person Steve Friedl    schedule 22.12.2019
comment
Некоторые компиляторы предлагают 128-битный uintmax_t; или что-то вроде __uint128   -  person M.M    schedule 22.12.2019
comment
@SteveFriedl Я ожидаю получить 1068547cd3052bbe5688de35695b1239 в качестве результата   -  person cheshire    schedule 22.12.2019
comment
Хорошо, но какую платформу/компилятор вы используете?   -  person Steve Friedl    schedule 22.12.2019
comment
@SteveFriedl извините, gcc   -  person cheshire    schedule 22.12.2019
comment
Платформа - линукс, виндовс, армв7х, альфа? 32бит, 64бит? Gcc может иметь __uint128 на вашей платформе, вы можете распечатать его как два 64-битных слова.   -  person KamilCuk    schedule 22.12.2019
comment
@KamilCuk линукс, 64 бит. Как бы я напечатал его как два 64-битных слова?   -  person cheshire    schedule 22.12.2019


Ответы (1)


Ответ, который вы ищете, не помещается в 64-битный unsigned long long, который является нормальным размером на 64-битной платформе; любой избыток во время умножения переполняется и отбрасывается.

Более новые версии GCC поддерживают 128-битные целые числа на 64-битных машинах с __int128unsigned __int128), и это работает:

unsigned long long int x = 0x28B2D48D74212E4FULL;
unsigned long long int y = 0x6734B42C025D5CF7ULL;
unsigned __int128 xy = x * (unsigned __int128)y;

Обратите внимание, что вам нужно привести один из x или y к более широкому типу, чтобы умножение выполнялось в 128 битах; в противном случае это повышение до 128 не выполняется до тех пор, пока не будет выполнено (усеченное) 64-битное умножение.

Проблема в том, насколько я могу судить, у printf() нет простого способа сделать это, так что вам придется немного повозиться.

Некоторое разумное обсуждение здесь: как напечатать номер __uint128_t с помощью gcc?

Но это сработало для меня на:

gcc (GCC) 4.8.5 20150623 (Red Hat 4.8.5-39)

#include <stdio.h>

int main()
{
unsigned long long int x = 0x28B2D48D74212E4F;
unsigned long long int y = 0x6734B42C025D5CF7;
unsigned __int128 xy = x * (unsigned __int128)y;

    printf("Result = %016llx%016llx\n",
        (unsigned long long)( xy >> 64),
        (unsigned long long)( xy & 0xFFFFFFFFFFFFFFFFULL));

    return 0;

Приведения внутри printf важны: в противном случае сдвиг/маскирование выполняется в 128-битных скалярах, и эти 128 бит помещаются в стек, но тогда каждый %llx ожидает 64 бита.

Обратите внимание, что все это полностью зависит от базовой платформы и не является переносимым; конечно, есть способ использовать различные #ifdefs и sizeofs, чтобы сделать его более общим, но, вероятно, нет супер крутого способа заставить это работать везде.

person Steve Friedl    schedule 21.12.2019
comment
Примечание. LL в 0xFFFFFFFFFFFFFFFFULL допустимо, но не обязательно. U здесь не необходим как шестнадцатеричная константа, но все же хорошо использовать для беззнаковых констант. - person chux - Reinstate Monica; 22.12.2019
comment
@chux-ReinstateMonica на самом деле вся операция & избыточна, они могли бы просто поставить (unsigned long long)xy. Я бы даже сказал, что это улучшение, так как вы не можете ошибиться в F - person M.M; 22.12.2019
comment
на самом деле я забираю свой последний комментарий, возможно, что unsigned long long тоже 128-битный. Возможно, было бы разумно использовать UINT64_MAX в качестве маски; или используя uint64_t в первую очередь - person M.M; 22.12.2019