Другое 32-битное преобразование в long/__int64, почему?

Я пишу свою маленькую мультиточную библиотеку, и при написании метода вычитания я столкнулся с какой-то странной ошибкой. Вот блок кода, который я написал для вычитания с множественной точностью:

/* 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 — это 32-битное целое число без знака, а a, b — BigInt. Значения хранятся внутри вектора в стиле Big Endian. temp равен __int64, а перенос должен работать как 32-битный без знака.

Допустим, мы вычитаем b из a, a > b (беззнаковое вычитание), но все 32-битные слова в b больше, чем a. Эта процедура производит следующий вывод:

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
...

Но перенос всегда должен быть 0xffffffffff. Каждый раз, когда он равен нулю, результат равен «13131314», что неверно. Теперь давайте изменим перенос с unsigned long на unsigned __int64 и

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

to 

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

Теперь перенос всегда рассчитывается правильно и равен 0xffffffff. Но сдвиг вправо 64-битного значения 2^32 всегда должен давать 32-битный результат.

Мой вопрос: чтобы понять разные результаты, что мне не хватает?

Большое тебе спасибо.


c++ bignum
person Community    schedule 27.11.2009    source источник
comment
Небольшое замечание: вместо нестандартного __int64 можно использовать стандартный long long.   -  person denisenkom    schedule 27.11.2009
comment
long long также не является стандартным в С++. Он определен в C++99 и планируется добавить в C++ в C++0x, но его пока нет.   -  person jalf    schedule 27.11.2009
comment
@Zyrkon: Извините, но ваше описание не имеет смысла. Если мы делаем беззнаковое вычитание и A › B, как вы говорите, все слова в B не могут быть больше, чем все слова в A. Кроме того, в вашем примере ваши поэлементные данные меняются местами в отношении данных массива (A и В поменялись местами). Пожалуйста, наведите порядок, пока мы не начали разбираться во всем этом.   -  person AnT    schedule 27.11.2009
comment
Это должна быть вики сообщества как пример того, как не использовать С++. Что касается вашего вопроса, не смешивайте __int64, long и int. Если вам нужны типы с точно определенной шириной, используйте __int64 соответственно (или лучше uin64_t из внешнего stdint.h, который отсутствует в vc++) и вообще избегайте длинных и даже беззнаковых int.   -  person Gunther Piez    schedule 27.11.2009

Ответы (2)


arrow_upward
3
arrow_downward

Что sizeof(long) в вашей среде? Я подозреваю, что если вы проверите, вы обнаружите, что это 4, то есть ваши unsigned long на самом деле являются 32-битными значениями.

person moonshadow    schedule 27.11.2009
comment
sizeof long по определению равен 4. sizeof int - это тот, который варьируется - person Ruben Bartelink; 27.11.2009
comment
@Рубен: По определению? О каком определении вы говорите? - person AnT; 27.11.2009
comment
Мой компилятор говорит, что sizeof(long) == 8. Вы только что обнаружили замечательную ошибку, которая должна быть скрыта более 10 лет, если учесть, как долго gcc использовался для создания 64-битного программного обеспечения. - person Gunther Piez; 27.11.2009

arrow_upward
0
arrow_downward 

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

Не вводите такие значения жестко. Вам не гарантируется, что unsigned long имеет какой-то конкретный размер (и часто он не будет 64-битным, как вы предполагаете). Так что битовый сдвиг, а также ваше побитовое «и» должны учитывать это. Возможно, вы могли бы заменить 32 чем-то вроде sizeof(unsigned long)*8. И вместо 0xffffffff подойдет ~0L, или, возможно, -1, если вы чувствуете себя смелым. (Это будет работать, пока подписанные целые числа представлены двумя дополнениями, что обычно имеет место, но это не гарантируется стандартом)

person jalf    schedule 27.11.2009