Как правильно умножить два длинных длинных целых числа?

Я хочу умножить длинные числа, которые даны в основе 2 ^ 32. Я уже придумал хороший алгоритм для этого, но, к сожалению, я застрял. Ситуация, в которой я застрял, заключается в том, как я умножаю два длинных целых числа и представляю их на основе 2 ^ 32.

#include <stdio.h>
#include <stdlib.h>
#include <limits.h>
typedef unsigned int uint32;
typedef unsigned long long uint64;
int main(int argc, char* argv[] )
{

  uint64 a = (uint64)ULONG_MAX;
  printf("%llu\n", a);
  uint64 b = (uint64)ULONG_MAX;  
  printf("%llu\n", b);  
  uint64 c = (uint64)(a*b);

  printf("%llu\n", c);  // prints 1. that would be to lower 32 bits of the results. the upper half is 0xFFFFFFFE

  printf("%llu\n", ULLONG_MAX);
  system("pause");
}

Почему ULLONG_MAX совпадает с ULONG_MAX? Согласно http://en.wikipedia.org/wiki/Limits.h#Member_constants должно быть 18 446 744 073 709 551 615 I

Как видно из моих комментариев, мне нужен результат умножения двух uint32. Нижняя половина будет 0x1, а верхняя половина 0xFFFFFFFE. Как получить эти значения?

(Я нашел этот вопрос на SO, но в моей ситуации это бесполезно, потому что ответы, данные мне, похожи на мои идеи: Умножение двух длинных длинных целых чисел C)

Изменить: Моя система — Windows XP 32 Bit. Я использую gcc 3.4.2 (специальный mingw)

Вывод, который я получаю при запуске кода:

4294967295
4294967295
1
4294967295

Изменить2:

  printf("%i\n", sizeof(unsigned long));
  printf("%i\n", sizeof(unsigned long long));

возвращается

4
8

Редактировать 3: благодаря Petesh я смог найти решение:

  printf("%lu\n", c & 0xFFFFFFFF);
  printf("%lu\n", (c >> 32));

c multiplication unsigned-long-long-int
person citronas    schedule 22.08.2010    source источник
comment
Какую реализацию вы используете? Это отлично работает для меня на GCC (32-битная система). Печатает 4294967295, 4294967295, 18446744065119617025, 18446744073709551615, как и ожидалось. Возможно, ваша реализация не поддерживает формат печати %llu, обрабатывает его как %lu, а ваша система использует обратный порядок байтов, поэтому в обоих случаях varargs выбирает менее значимое слово аргумента?   -  person Steve Jessop    schedule 22.08.2010

Ответы (2)


arrow_upward
5
arrow_downward

Подсказка в системе("пауза") - вы на windows? Для печати long long с использованием среды выполнения Microsoft Visual C необходимо использовать «% I64u» (это заглавная буква i).

Это основано на вопросе SO Как вы печатаете unsigned long long int(спецификатор формата для unsigned long long int)?

person Petesh    schedule 22.08.2010
comment
Я ожидал этого, когда увидел, что он использует mingw. - person Petesh; 22.08.2010

arrow_upward
3
arrow_downward

Не уверен, почему вы получаете такие результаты с вашим (неуказанным) компилятором, но gcc под Ubuntu 10 дает:

4294967295
4294967295
18446744065119617025
18446744073709551615

причем последние два равны 0xfffffffe00000001 и (264-1) соответственно, как вам угодно.

Так что, возможно, подумайте о переходе на более современный компилятор. Возможно, вы используете компилятор до C99.

Просто из интереса, что sizeof (unsigned long) и sizeof (unsigned long long) дают вам в вашей системе. Это будет иметь большое значение для объяснения вашей проблемы.

Еще несколько вещей, которые нужно проверить, так как ваши sizeof, кажется, указывают на то, что сами типы данных в порядке (хотя это может не решить проблему — они были найдены с довольно поверхностный веб-поиск):

  • Попробуйте использовать "%I64u" в качестве строки формата вместо "%llu". Если MinGW использует библиотеки MSVCRT, это может потребоваться для реальной 64-битной поддержки printf.
  • Убедитесь, что вы компилируете с -std=c99.
person paxdiablo    schedule 22.08.2010