How to correctly multiply two long long ints?

Question

I want to multiply long numbers which are given in a 2^32 basis. I already thought of an nice algorithm to do that, but unfortunatly I'm stuck. The situation I'm stuck at, is how I do multiply two long ints and represent it on the 2^32 basis.

#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");
}

Why is ULLONG_MAX the same as ULONG_MAX ? According to http://en.wikipedia.org/wiki/Limits.h#Member_constants it should be 18,446,744,073,709,551,615 I

As you can see from my comments, I want the result of the the multiplikation in the two uint32. The lowerhalf would be 0x1 and the upper half 0xFFFFFFFE. How do I get these values?

(I found this question on SO, but it's not helpful in my situation because the answers given ar similiar to my ideas: http://stackoverflow.com/questions/1856264/multiplying-two-long-long-ints-c)

Edit: My system is Windows XP 32 Bit. I'm using gcc 3.4.2 (mingw-special)

The output I do get while running the code:

4294967295
4294967295
1
4294967295

Edit2:

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

returns

4
8

Edit 3: Thanks to Petesh I was able to find the solution:

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

Answer 1

Not sure why you're getting those results with your (unspecified) compiler but gcc under Ubuntu 10 gives:

4294967295
4294967295
18446744065119617025
18446744073709551615

with those last two being 0xfffffffe00000001 and (2⁶⁴-1) respectively, as you desire.

So maybe consider switching to a more up-to-date compiler. It may be you're using a pre-C99 compiler.

Just out of interest, what does sizeof (unsigned long) and sizeof (unsigned long long) give you on your system. This would go a long way towards explaining your problem.

---

A couple of other things to check since your sizeofs seem to indicate the data types themselves are okay (though these may not fix the problem - they were found with a fairly shallow web search):

• Try using "%I64u" as the format string instead of "%llu". If MinGW is using the MSVCRT libs, that might be required for real 64-bit printf support.
• Make sure you're compiling with -std=c99.

Answer 2

The hint is in the system("pause") - you're on windows? Printing a long long using the Microsoft visual c runtime requires using '%I64u' (that's a capital i).

This is based on SO question http://stackoverflow.com/questions/2844/how-do-you-printf-an-unsigned-long-long-int