Добавление 64-битных чисел с использованием 32-битной арифметики
Вопрос
Как добавить два 64-битных числа, используя 32-битную арифметику? Р>
Решение
Сначала добавьте наименее значимые байты, сохраняйте перенос. Добавьте наиболее значимые байты, учитывая перенос из младших битов:
; x86 assembly, Intel syntax
; adds ecx:ebx to edx:eax
add eax, ebx
adc edx, ecx
Другие советы
Подумайте, как добавить два двузначных числа, используя арифметику из 1 цифры.
42
+39
---
Сначала добавьте правый столбец. («Единицы» или «единицы»). 2 + 9 равно 11. 11 "переполнен" Ваша 1-значная арифметика, поэтому вы должны "нести" 10.
1
42
+39
---
1
Теперь вы складываете левые "десятки" колонка, в том числе керри. 1 + 4 + 3 = 8. Р>
1
42
+39
---
81
8 меньше 10, так что нет переноса. Вы сделали.
Что только что произошло? Когда вы говорите, что число "42" (в базе 10) вы действительно имеете в виду
4*10+2
Или, что то же самое,
4*10^1+2*10^0
(когда я говорю «a ^ b», например «10 ^ 1», я имею в виду «a, возведенное в b'th power»: a, умноженное на себя b раз. 10 ^ 0 равно 1. 10 ^ 1 = 10. 10 ^ 2 - 10 * 10 = 100 ...)
Когда вы добавляете " 42 " и "39"; ты говоришь
4*10+2+3*10+9
Что равно
(4+3)*10+(2+9)*1
(4+3)*10+(11)*1
(4+3)*10+(1*10+1)*1
Теперь, начиная с " 11 " недопустимое однозначное число, вам нужно вынести 10 из них, превратив его в 1 в десятке.
(4+3)*10+(1)*10+(1)*1
(4+3+1)*10+(1)*1
(8)*10+(1)*1
который составляет 81.
Итак, почему я говорил об этом, а не о вашем вопросе о 64-разрядных числах и 32-разрядной арифметике? Потому что они на самом деле точно такие же!
Цифра находится в диапазоне от 0 до 9. «32-битное число»; колеблется от 0 до 2 ^ 32-1. (Предполагая, что это без знака.)
Итак, вместо того, чтобы работать в базе 10, давайте работать в базе 2 ^ 32. В базе 2 ^ 32 мы записываем 2 ^ 32 как 10. Если вы напишите 64-битное число в базе 2 ^ 32, это будет
(x)*10+y
где x и y - символы для чисел от 0 до 2 ^ 32-1. Эти символы являются цепочками битов.
Если вы хотите добавить два 64-битных числа, разбейте их в базе 2 ^ 32 следующим образом:
a_1*10+a_0
+b_1*10+b_0
Теперь вы добавляете их в базу 2 ^ 32 точно так же, как вы добавляете их в базу 10 - просто вместо добавления с использованием арифметики с цифрами, которую вы добавляете с помощью 32-битной арифметики!
Как разделить 64-битное число a на два 32-битных числа a_1 и a_0? Разделите на 2 ^ 32. Не с плавающей точкой, а целочисленно - где вы получаете дивиденд и остаток. Дивиденд равен a_1, остаток равен a_0.
К сожалению, для этого требуется 64-битная арифметика. Однако, как правило, a_1 является «наиболее значимой половиной»; так, в синтаксисе стиля C:
a_1=(a >> 32)
a_0=(a & 0xFFFFFFFF)
где > > правильное смещение и & amp; поразрядно и.
Как правило, если вы не можете выполнить 64-разрядное добавление, используйте " 64-разрядное число " на самом деле будут два 32-битных числа a_1 и a_0. У вас не будет uint64_t, если вы не можете выполнять арифметику uint64_t!
Все это предполагает, что вы выполняете арифметику без знака, но здесь легко разобраться со знаками.
Ранее опубликованный код C излишне многословен:
unsigned a1, b1, a2, b2, c1, c2;
c1 = a1 + b1;
c2 = a2 + b2;
if (c1 < a1)
c2++;
«a1» в «if» также можно заменить на «b1». При переполнении c1 будет меньше, чем a1 и b1.
Если 64-битные числа (a 2 , a 1 ) и (b 2 , b 1 ), где x 2 - старшие 32 бита, взятые как неподписанные, а x 1 - младшие 32 бита считаются беззнаковыми, тогда сумма двух чисел приведена ниже. Р>
c1 = a1 + b1
c2 = a2 + b2
if (c1 < a1 || c1 < b1)
c2 += 1
это выглядит примерно так
/* break up the 64bit number into smaller, 16bit chunks */
struct longint {
uint16 word0;
uint16 word1;
uint16 word2;
uint16 word3;
};
uint16 add(longint *result, longint *a, longint *b)
{
/* use an intermediate large enough to hold the result
of adding two 16 bit numbers together. */
uint32 partial;
/* add the chunks together, least significant bit first */
partial = a->word0 + b->word0;
/* extract thie low 16 bits of the sum and store it */
result->word0 = partial & 0x0000FFFF;
/* add the overflow to the next chunk of 16 */
partial = partial >> 16 + a->word1 + b->word1;
/* keep doing this for the remaining bits */
result->word1 = partial & 0x0000FFFF;
partial = partial >> 16 + a->word2 + b->word2;
result->word2 = partial & 0x0000FFFF;
partial = partial >> 16 + a->word3 + b->word3;
result->word3 = partial & 0x0000FFFF;
/* if the result overflowed, return nonzero */
return partial >> 16;
}
Фактическое оборудование не использует 32 бита для добавления 16 битов за раз, для добавления требуется только один дополнительный бит переноса, и почти все ЦП имеют флаг состояния переноса для случая, когда операция добавления была переполнена, так что если вы используется 32-битный процессор, вы можете добавить 64-битные операнды в две 32-битные операции.
Практически у каждого процессора есть бит переноса и операция добавления с переносом, о которой вы заботитесь, только если вы программируете на ассемблере. Если вы используете более высокий язык, компилятор выводит те же самые операции добавления с переносом. Мой AVR-GCC дал мне это при добавлении двух 16-битных чисел - AVR 8-битный - но те же концепции будут применяться для более высоких процессоров. Р>
Учитывая номера находятся в регистрах R1: R2 и R3: R4:
ADD R2,R4 ; first add the two low-bytes, result stored into R2
ADC R1,R3 ; then the two high-bytes and the carry bit, into R1
Результат сохраняется в R1: R2.