Добавление 64-битных чисел с использованием 32-битной арифметики

Question

Как добавить два 64-битных числа, используя 32-битную арифметику ??

Answer 1

Сначала добавьте наименее значимые байты, сохраняйте перенос. Добавьте наиболее значимые байты с учетом переноса из младших битов:

; x86 assembly, Intel syntax
; adds ecx:ebx to edx:eax
add eax, ebx
adc edx, ecx

Answer 2

Рассмотрим, как вы добавляете два двузначных числа, используя однозначную арифметику.

 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 степень»: умножается на 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 является «самой значительной половиной» a, поэтому в синтаксисе стиля C:

a_1=(a >> 32)
a_0=(a & 0xFFFFFFFF)

где >> - правильное битовое смещение, а & - побитовое и.

Как правило, если вы не можете выполнить 64-битное сложение, «64-битное число» фактически будет двумя 32-битными числами a_1 и a_0. У вас не будет uint64_t, если вы не можете выполнять арифметику uint64_t!

Все это предполагает, что вы выполняете арифметику без знака, но отсюда легко разобраться со знаками.

Answer 3

Ранее опубликованный код C неоправданно многословен:

unsigned a1, b1, a2, b2, c1, c2;

c1 = a1 + b1;
c2 = a2 + b2;

if (c1 < a1)
    c2++;

«a1» в «if» также можно заменить на «b1». При переполнении c1 будет меньше, чем a1 и b1.

Answer 4

Если 64-битные числа (a ₂ , a ₁ ) и (b ₂ , b ₁ ), где x ₂ - старшие 32 бита, принятые как без знака, а x ₁ - младшие 32 бита, принятые как без знака, затем Сумма двух чисел приведена ниже.

c1 = a1 + b1

c2 = a2 + b2

if (c1 < a1 || c1 < b1)
   c2 += 1

Answer 5

это выглядит примерно так

/* 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-битные операции.

Answer 6

Практически у каждого процессора есть бит переноса и операция добавления с переносом, о которой вы заботитесь, только если вы программируете на сборке. Если вы используете более высокий язык, компилятор выводит те же самые операции добавления с переносом. Мой 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.