Почему (a | b) эквивалентно a - (a & amp; b) + b?
-
05-07-2019 - |
Вопрос
Я искал способ сделать BITOR () с базой данных Oracle и натолкнулся на предложение просто использовать вместо него BITAND (), заменив BITOR (a, b) на a + b - BITAND (a, b) . р>
Я несколько раз тестировал его вручную и убедился, что он работает для всех двоичных чисел, о которых я только мог подумать, но я не могу придумать быстрое математическое доказательство того, почему это правильно.
Может ли кто-нибудь просветить меня?
Решение
A & amp; B - это набор битов, которые включены как в A, так и в B. A - (A & amp; B) оставляет вам все те биты, которые включены только в A. Добавьте к этому B, и вы получите все биты, которые включены в A или те, которые включены в B.
Простое добавление A и B не будет работать из-за переноса, где оба имеют 1 бит. Удаляя сначала биты, общие для A и B, мы знаем, что (A- (A & amp; 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
Давайте теперь возьмем два числа, которые нарушают наше условие, то есть два числа имеют хотя бы одну единицу в некотором общем бите
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
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 часов простоя, и, наконец, мне удалось опубликовать его, только после этого заметив, что оно был правильно ответил дважды. Лично я предпочитаю ссылаться на таблицу истинности для выполнения побитовых операций, поэтому я оставлю это на тот случай, если это кому-нибудь поможет.