Different 32bit-cast into long/__int64, why?

Question

I'm writing my own small multiprecision library, and while writing the method for subtraction, I encountered some weird error. Here is the code block I wrote for for multiprecision subtraction:

/* subtraction */
 for (; p_aReverseIter != a.m_elements.rend(); ++p_aReverseIter, ++p_bReverseIter) 
 {
  temp = static_cast<__int64>(static_cast<__int64>(p_aReverseIter->m_Value) - 
         static_cast<__int64>(p_bReverseIter->m_Value) + 
         (carry));
  --- debug output-  
  p_aReverseIter->m_Value = static_cast<unsigned int>(temp & 0xffffffff); 
  carry = static_cast<unsigned long>(temp >> 32);

 }

p_aReverseIter->m_Value is 32 bit unsigned int, while a,b are BigInt. Values are stored inside a vector in Big Endian style. temp is __int64 and carry should work as 32 bit unsigned long.

Let's say we substract b from a, a > b (unsigned subtraction), but all the 32bit words in b are larger then a. This routine produces following output:

a = 0xfefefefe (10 elem) 0xfefefefe (10 elem) 0xfefefefe (10 elem) 
0xfefefefe (10 elem) 

b = 0x12 (2 elem) 0x12121212 (9 elem) 0x12121212 (9 elem) 0x12121212 
(9 elem) 0x12121212 (9 elem)

a[i]: 12121212 
b[i]: fefefefe 
old carry: 0 
temp = a - b + carry: ffffffff13131314
Value: 13131314 
new carry: ffffffffffffffff

a[i]: 12121212 
b[i]: fefefefe 
old carry: ffffffff 
temp = a - b + carry: 13131313 
Value: 13131313 
new carry: 0

a[i]: 12121212 
b[i]: fefefefe 
old carry: 0 
temp = a - b + carry: ffffffff13131314 
Value: 13131314 
new carry: ffffffffffffffff

a[i]: 12121212 
b[i]: fefefefe 
old carry: ffffffff 
temp = a - b + carry: 13131313 
Value: 13131313 
new carry: 0
...

But the carry should always be 0xfffffffff. Everytime it is zero, the result is '13131314' which is wrong. Now lets change the carry from unsigned long to unsigned __int64 and

carry = static_cast<unsigned long>(temp >> 32);

to

carry = static_cast<unsigned __int64>(temp >> 32);

Now the carry is always calculated correctly and is set to 0xffffffff. But rightshifting a 64bit value of 2^32 should always produce a 32 bit result.

My question is: To understand the different results, what am I missing?

Thank you very much.

Answer 1

What's sizeof(long) in your environment? I suspect if you test you'll find it's 4, i.e. your unsigned long are actually 32-bit values.

Answer 2

  p_aReverseIter->m_Value = static_cast<unsigned int>(temp & 0xffffffff); 
  carry = static_cast<unsigned long>(temp >> 32);

Don't hardcode values like these. You're not guaranteed that an unsigned long is any particular size (and it often won't be 64-bit as you assume). So bit shifting as well as your bitwise 'and' have to take that into account. You could replace the 32 with something like sizeof(unsigned long)*8 perhaps. And instead of 0xffffffff, ~0L would do the trick, or perhaps -1 if you're feeling brave. (It'll work as long as signed ints are represented by two's complement, which is usually the case, but it's not guaranteed by the standard)