Почему (a | b) эквивалентно a - (a & amp; b) + b?

Question

Я искал способ сделать BITOR () с базой данных Oracle и натолкнулся на предложение просто использовать вместо него BITAND (), заменив BITOR (a, b) на a + b - BITAND (a, b) .

Я несколько раз тестировал его вручную и убедился, что он работает для всех двоичных чисел, о которых я только мог подумать, но я не могу придумать быстрое математическое доказательство того, почему это правильно.
Может ли кто-нибудь просветить меня?

Answer 1

A & amp; B - это набор битов, которые включены как в A, так и в B. A - (A & amp; B) оставляет вам все те биты, которые включены только в A. Добавьте к этому B, и вы получите все биты, которые включены в A или те, которые включены в B.

Простое добавление A и B не будет работать из-за переноса, где оба имеют 1 бит. Удаляя сначала биты, общие для A и B, мы знаем, что (A- (A & amp; B)) не будет иметь общих бит с B, поэтому их объединение гарантированно не приведет к переносу.

Answer 2

Представьте, что у вас есть два двоичных числа: a и b . И скажем, что эти числа никогда не имеют 1 в одном и том же бите в одно и то же время, т. Е. Если a имеет 1 в каком-то бите, у b всегда будет 0 в соответствующем бите , И в другом направлении, если b имеет 1 в каком-то бите, то a всегда имеет 0 в этом бите. Например,

a = 00100011
b = 11000100

Это будет пример того, как a и b удовлетворяют вышеуказанному условию. В этом случае легко увидеть, что a | b будет точно таким же, как a + b .

a | b = 11100111
a + b = 11100111

Давайте теперь возьмем два числа, которые нарушают наше условие, то есть два числа имеют хотя бы одну единицу в некотором общем бите

a = 00100111
b = 11000100

Является ли a | b то же самое, что и a + b в этом случае? Нет

a | b = 11100111
a + b = 11101011

Почему они разные? Они отличаются, потому что когда мы + бит, который имеет 1 в обоих числах, мы производим так называемый carry : результирующий бит равен 0, а 1 переносится в следующий бит слева: 1 + 1 = 10 . Операция | не имеет переноса, поэтому 1 | 1 снова просто 1.

Это означает, что разница между a | b и a + b происходят тогда и только тогда, когда числа имеют по крайней мере один 1 в общем бите. Когда мы суммируем два числа с 1 в общих битах, эти общие биты добавляются «дважды» и произвести перенос, который разрушает сходство между a | b и a + b .

Теперь посмотрите на a & amp; б . Что означает a & amp; б рассчитать? a & amp; b производит число, которое имеет 1 во всех битах, где и у a , и b есть 1. В нашем последнем примере

a =     00100111
b =     11000100
a & b = 00000100

Как вы видели выше, именно эти биты отличают a + b от a | б . 1 в a & amp; b указывает все позиции, где будет происходить перенос.

Теперь, когда мы делаем a - (a & amp; b) , мы фактически удаляем (вычитаем) все " оскорбляющие " биты из a и только такие биты

a - (a & b) = 00100011

Числа a - (a & amp; b) и b не имеют общих 1 битов, что означает, что если мы добавим a - (a & amp; b ) и b мы не столкнемся с переносом, и, если вы подумаете об этом, мы должны получить тот же результат, как если бы мы только что сделали a | б

a - (a & b) + b = 11100111

Answer 3

A & amp; B = C, где все оставшиеся биты, установленные в C, совпадают с битами, установленными как в A, так и в B.
Либо A-C = D, либо B-C = E устанавливает только эти общие биты в 0. Эффект переноса отсутствует, поскольку 1-1 = 0.
D + B или E + A аналогичны A + B, за исключением того, что, поскольку ранее мы вычитали A & amp; B, не будет переноса из-за очистки всех обычно установленных битов в D или E.

В результате A-A и B + B или B-A и B + A эквивалентны A | B.

Вот таблица истинности, если она все еще сбивает с толку:

 A | B | OR   A | B | &    A | B | -    A | B | + 
---+---+---- ---+---+---  ---+---+---  ---+---+---
 0 | 0 | 0    0 | 0 | 0    0 | 0 | 0    0 | 0 | 0  
 0 | 1 | 1    0 | 1 | 0    0 | 1 | 0-1  0 | 1 | 1
 1 | 0 | 1    1 | 0 | 0    1 | 0 | 1    1 | 0 | 1  
 1 | 1 | 1    1 | 1 | 1    1 | 1 | 0    1 | 1 | 1+1

Обратите внимание на строки переноса в операциях + и -, мы избегаем их, потому что случаи A- (A & amp; B) были битами в A, а B - от 1 до 0 в A, а затем добавление их обратно из B также приводит к другие случаи были 1 в A или B, но не там, где оба имели 0, поэтому таблица истинности OR и таблица истинности A- (A & amp; B) + B идентичны.

Еще один способ взглянуть на глаза - это увидеть, что A + B почти как A | B, за исключением переноса в нижнем ряду. A & amp; B изолирует этот нижний ряд для нас, A-A & B перемещает эти изолированные элементы на две строки в таблице +, и (A-A & B) + B становится эквивалентным A | B.

Хотя вы могли заменить это на A + B- (A & amp; B), я боялся возможного переполнения, но это было неоправданно, кажется:

#include <stdio.h>
int main(){ unsigned int a=0xC0000000, b=0xA0000000;
printf("%x %x %x %x\n",a,   b,       a|b,       a&b);
printf("%x %x %x %x\n",a+b, a-(a&b), a-(a&b)+b, a+b-(a&b)); }

c0000000 a0000000 e0000000 80000000
60000000 40000000 e0000000 e0000000

Редактировать . Итак, я написал это до того, как были получены ответы, после чего на моем домашнем соединении было около 2 часов простоя, и, наконец, мне удалось опубликовать его, только после этого заметив, что оно был правильно ответил дважды. Лично я предпочитаю ссылаться на таблицу истинности для выполнения побитовых операций, поэтому я оставлю это на тот случай, если это кому-нибудь поможет.

Answer 4