Добавление чисел на 64 бита с помощью арифметики на 32 бита

Question

Добавление чисел на 64 бита с помощью арифметики на 32 бита

В T-SQL (SQL Server MS), это работает:

SELECT
  CASE WHEN Field IS NULL THEN 'NULL' ELSE 'NOT NULL' END FieldContent,
  COUNT(*) FieldCount
FROM
  TheTable
GROUP BY
  CASE WHEN Field IS NULL THEN 'NULL' ELSE 'NOT NULL' END

12

64-bit 32-bit

задан Light_handle 30 October 2009 в 22:32

6 ответов

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

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

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

if (c1 < a1)
    c2++;

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

7

ответ дан 2 December 2019 в 03:01

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

c1 = a1 + b1

c2 = a2 + b2

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

6

ответ дан 2 December 2019 в 03:01

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

 42
+39
---

Сначала вы добавляете правый столбец. («Единицы» или «единицы»). 2 + 9 равно 11. 11 "переполнило" вашу однозначную арифметику, поэтому вам нужно "перенести" 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 - это «старшая половина», поэтому в синтаксисе стиля C:

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

где >> - это правый битовый сдвиг, а & - побитовое и.

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