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

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 | 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 также приводит к другим случаям, когда в A или B была 1, но не там, где оба имели 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

Edit : Итак, я написал это до того, как были ответы, затем было около 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

Is 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