Распределены ли побитовые операции над сложением?

Question

Я смотрю на алгоритм, который пытаюсь оптимизировать, и в основном он немного сложный, за которым следуют некоторые дополнения в тесной обратной связи. Если бы я мог использовать дополнение для переноса для сумматоров, это действительно помогло бы мне ускорить процесс, но я не уверен, смогу ли я распределить операции по сложению.

В частности, если я представляю:

  a = sa+ca  (state + carry)
  b = sb+cb

Могу ли я представить (a >>> r) в терминах s и c? Как насчет | б и а & б?

Answer 1

Подумай об этом ...

sa = 1    ca = 1
sb = 1    cb = 1
a = sa + ca = 2
b = sb + cb = 2
(a | b) = 2
(a & b) = 2
(sa | sb) + (ca | cb) = (1 | 1) + (1 | 1) = 1 + 1 = 2 # Coincidence?
(sa & sb) + (ca & cb) = (1 & 1) + (1 & 1) = 1 + 1 = 2 # Coincidence?

Давайте попробуем некоторые другие значения:

sa = 1001   ca = 1   # Binary
sb = 0100   cb = 1
a = sa + ca = 1010
b = sb + cb = 0101
(a | b) = 1111
(a & b) = 0000
(sa | sb) + (ca | cb) = (1001 | 0101) + (1 | 1) = 1101 + 1 = 1110 # Oh dear!
(sa & sb) + (ca & cb) = (1001 & 0101) + (1 & 1) = 0001 + 1 = 2    # Oh dear!

Итак, пример с 4-битным счетчиком, доказательство того, что вы не можете распределить И или ИЛИ по сложению.

А как насчет '>>>' (беззнаковое или логическое смещение вправо). Используя значения последнего примера, и r = 1:

sa = 1001
ca = 0001
sa >>> 1 = 0101
ca >>> 1 = 0000
(sa >>> 1) + (ca >>> 1) = 0101 + 0000 = 0101
(sa + ca) >>> 1 = (1001 + 0001) >>> 1 = 1010 >>> 1 = 0101  # Coincidence?

Посмотрим, совпадение ли это тоже:

sa = 1011
ca = 0001
sa >>> 1 = 0101
ca >>> 1 = 0000
(sa >>> 1) + (ca >>> 1) = 0101 + 0000 = 0101
(sa + ca) >>> 1 = (1011 + 0001) >>> 1 = 1100 >>> 1 = 0110  # Oh dear!

Подтверждение контрпримером еще раз.

Таким образом, логическое смещение вправо также не является распределительным по сложению.

Answer 2

Нет, вы не можете распределить И или ИЛИ по двоичным операторам.

Объяснение

Пусть P будет суждением, где P: (A + B) & C = A & C + B & C

возьмем A = 2, B = 3 => A + B = 5.

Мы должны доказать A & C + B & C! = (A + B) & C

A = 2 = 010

B = 3 = 011

пусть 010 & C = x, где x - некоторое целое число, значение которого является результатом побитового И 010 и C

аналогично 011 & C = y, где y - некоторое целое число, значение которого является результирующим от побитового И 011 и C

, поскольку мы не можем сказать, что P выполняется для всех C во множестве натуральных чисел ({0,1, ...}), следовательно, P ложно.

В этом случае принять C = 2 = 010

x = 010 и 010 = 010 = 2

y = 011 & 010 = 010 = 2

5 & 2 = 101 & 010 = 000 = 0

ясно, x + y! = 0, что означает (A + B) & C! = A & C + B & C.

Следовательно доказано!