Почему (a | b) эквивалентно a - (a & b) + b?
Я искал способ сделать BITOR() с базой данных Oracle и натолкнулся на предложение просто использовать вместо него BITAND(), заменив BITOR(a,b) на a + b - BITAND(a,b).
Я проверил это вручную несколько раз и убедился, что оно работает для всех двоичных чисел, о которых я мог подумать, но я не могу придумать быстрое математическое доказательство того, почему это правильно.
Может ли кто-нибудь просветить меня?
4 ответа
A & B - это набор битов, которые включены как в A, так и в B. A - (A & B) оставляет вам все те биты, которые включены только в A. Добавьте к этому B, и вы получите все биты, которые на в или те, которые включены в B.
Простое добавление A и B не будет работать из-за переноса, где оба имеют 1 бит. Удаляя сначала биты, общие для A и B, мы знаем, что (A-(A&B)) не будет иметь общих бит с B, поэтому их сложение гарантированно не приведет к переносу.
Представьте, что у вас есть два двоичных числа: 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
Давайте теперь возьмем два числа, которые нарушают наше условие, то есть два числа имеют по крайней мере один 1 в некотором общем бите
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
A&B = C, где любые оставшиеся биты, установленные в C, являются битами, установленными как в A, так и в B.
Либо AC = D, либо BC = E устанавливает только эти общие биты в 0. Эффект переноса отсутствует, поскольку 1-1 = 0.
D + B или E+A аналогичны A + B, за исключением того, что, поскольку ранее мы вычитали A & B, не будет переноса из-за очистки всех обычно установленных битов в D или E.
В итоге получается, что AA&B+B или BA&B+A эквивалентны A|B.
Вот таблица истинности, если она все еще сбивает с толку:
A | Б | ИЛИ А | Б | & A | Б | - А | Б | + --- + --- + ---- --- + --- + --- --- + --- + --- --- + --- + --- 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 выделяет этот нижний ряд для нас, AA & B перемещает эти изолированные элементы на две строки в таблице +, и (AA & 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 часов простоя на моем домашнем соединении, и я наконец-то сумел опубликовать его, заметив только после этого, что на него правильно ответили дважды. Лично я предпочитаю ссылаться на таблицу истинности для работы побитовых операций, поэтому я оставлю это на случай, если это кому-нибудь поможет.
