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

Question

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

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

Answer 1

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

Простое добавление A и B не будет работать из-за переноса, где оба имеют 1 бит. Удаляя сначала биты, общие для A и B, мы знаем, что (A- (A & 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 в обоих числах, мы производим так называемый перенос : результирующий бит равен 0, а 1 переносится в следующий бит слева: 1 + 1 = 10. Операция | не имеет переноса, поэтому 1 | 1 снова просто 1.

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

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

a =     00100111
b =     11000100
a & b = 00000100

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

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

a - (a & b) = 00100011

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

a - (a & b) + b = 11100111

Answer 3

A & B = C, где любые оставшиеся биты, установленные в C, являются битами, установленными как в A, так и в B.
Либо A-C = D, либо B-C = E устанавливает только эти общие биты в 0. Эффект переноса отсутствует, поскольку 1-1 = 0.
D + B или E + A аналогичны A + B, за исключением того, что, поскольку ранее мы вычитали A & 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 & B) были битами в A, а B - от 1 до 0 в A, затем добавление их обратно из B также приводит к другим были случаи, когда был 1 в A или B, но не там, где оба имели 0, поэтому таблица истинности OR и таблица истинности A- (A & B) + B идентичны.

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

Хотя вы могли бы заменить это на A + B- (A & 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