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

Ответ 1

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

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

Ответ 2

Рассмотрим, как вы добавляете два двузначных числа, используя 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", я имею в виду "поднятый до b-й степени": 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? Разделите a на 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 арифметику!

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

Ответ 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.

Ответ 4

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

c1 = a1 + b1

c2 = a2 + b2

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

Ответ 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-разрядные операции.

Ответ 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.

Ответ 7

Вы можете добавить каждую 32-битную часть вручную и позаботиться о переносе вручную.