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

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

Ответы на вопрос(6)

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

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

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

if (c1 < a1)
    c2++;

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

 Leo Ufimtsev16 дек. 2015 г., 22:11
Очень элегантно.

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

 Cole Johnson18 янв. 2013 г., 17:02
Почему 64-битная арифметика использует 32-битные числа при использовании расширенных 64-битных регистров?

Если 64-битные числа (а2, a1) и (b2, b1), где х2 старшие 32 бита считаются без знака, а x1 это младшие 32 бита, взятые как беззнаковые, тогда сумма двух чисел приведена ниже.

c1 = a1 + b1

c2 = a2 + b2

if (c1 < a1 || c1 < b1)
   c2 += 1
 Light_handle31 окт. 2009 г., 00:24
Кстати ... Что такое a1, b1, a2 и b2, если нам даны только два 64-битных числа ??
 DigitalRoss31 окт. 2009 г., 01:03
@all, спасибо за комментарии. Я'мы постарались заполнить ответ несколько.
 Keith Randall31 окт. 2009 г., 00:06
Убедитесь, что a1, b1, c1 не подписаны, чтобы сравнение работало корректно.
Решение Вопроса

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

; x86 assembly, Intel syntax
; adds ecx:ebx to edx:eax
add eax, ebx
adc edx, ecx
 BenW31 июл. 2012 г., 20:30
Одно из свойств двухАрифметика дополнения состоит в том, что числа со знаком не требуют специальной обработки. Я могу сказать (в синтаксисе Intel)add eax, 0xFFFFFFFF и влияние наeax будет так же, как если бы я сказал.sub eax, 1
 Cole Johnson03 июл. 2012 г., 03:06
Но как насчет подписанного?

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

/* 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;
}

Фактическое оборудование неДля добавления 16 битов одновременно используется 32 бита, для добавления требуется только один дополнительный бит переноса, и почти весь процессорs имеет флаг состояния переноса, когда операция сложения переполнена, поэтому, если вы используете 32-битный процессор, вы можете добавить 64-битные операнды в две, 32-битные операции.

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

 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

(когда я сказал "а ^ Ь», лайк "10 ^ 1", Я имею в виду "поднял до б 'th power: умножается на себя 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" ISN»Чтобы получить однозначное число, вам нужно вынести 10 из них, превратив его в 1 в десятке.

(4+3)*10+(1)*10+(1)*1
(4+3+1)*10+(1)*1
(8)*10+(1)*1

что 81.

Итак, почему я говорил об этом, а не о вашем вопросе о 64-разрядных числах и 32-разрядной арифметике? Потому что они на самом деле точно такие же!

Цифра колеблется от 0 до 9. A "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)

где >> это правильный сдвиг и & поразрядно и.

Как правило, если вы можете64-битное сложение, "64-битное число " на самом деле будут два 32-битных числа a_1 и a_0. Ты выиграл'не иметь uint64_t, если можешьне делайте арифметику uint64_t!

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

Ваш ответ на вопрос