Как это уравнение x + y = x & y + x | y выполняется (при условии, что x, y> 0)?

Question

Недавно я участвовал в конкурсе Code Force. В редакционной части конкурса я увидел одно из прекрасных соотношений между поразрядными операторами: x + y = x & y + x | у. Я еще не знаю доказательств. Я взял несколько чисел, чтобы проверить, верно ли это уравнение. Я был рад узнать доказательства. Я поискал его в Интернете и не нашел никаких значимых ссылок. пожалуйста, помогите мне найти доказательство или хотя бы дайте мне интуицию, стоящую за этим прекрасным уравнением. Заранее спасибо

Answer 1

Итак, всякий раз, когда вы пытаетесь выполнить побитовые вычисления, самым простым способом было бы составить диаграмму для всех ситуаций, особенно когда есть очень мало переменных.

 A | B | A AND B | A OR B |     A + B     | (A AND B) + (A OR B)
---+---+---------+--------+---------------+----------------------
 0 | 0 |    0    |    0   |   0 + 0 = 0   |     0 + 0 = 0
---+---+---------+--------+---------------+----------------------
 0 | 1 |    0    |    1   |   0 + 1 = 1   |     0 + 1 = 1
---+---+---------+--------+---------------+----------------------
 1 | 0 |    0    |    1   |   1 + 0 = 1   |     0 + 1 = 1
---+---+---------+--------+---------------+----------------------
 1 | 1 |    1    |    1   |   1 + 1 = 2   |     1 + 1 = 2

Теперь вы можете чтобы увидеть:

• если A == B, то A + B и A & B + A | B по сути одно и то же.
• если A != B, то A & B + A | B может изменить порядок двух значений, но, конечно, A + B = B + A, поэтому они по сути такие же, как while.

Answer 2

Допустим, вы выполняете a + b.

Обратите внимание, что замена i-го di git (считая от самого правого di git) из a на i-th di git of b не влияет на сумму. Пример: 123 + 456 == 156 + 423. Это работает независимо от выбора базы, поэтому оно работает и для двоичного сложения.

Затем обратите внимание, что переход от a + b к a&b + a|b может быть выполнен путем замены некоторых цифр в пути описано выше (в двоичном формате). Если a[i] == 1 и b[i] == 0, то поменять местами a[i] и b[i]; после этого a становится a&b, а b становится a|b. Таким образом, этот переход не влияет на результат.

Answer 3

для x и y, вы можете разделить биты, сложить их вместе и получить тот же ответ, верно?
пример:

0101 (x) + 0110 (y) == (0100 + 0001) + (0100 + 0010)

сейчас. просмотр ваших логических операторов:
a & b дает вам биты, которые находятся в обоих числах (чтение: счетчик 2)
a | b дает вам биты, которые находятся в либо число (читай: количество ≥1)

так что в основном вы берете биты, которые есть в любом числе, суммируя их вместе:

0111 == 0100 (in x, y) + 0010 (in y) + 0001 (in x)

вы также взяв биты, которые есть в обоих числах (то есть биты, которые вам нужно посчитать дважды), и добавив их к сумме:

0100 == 0100 (in x, y)

так, вы в конечном итоге добавите биты, которые появляются один раз, один раз, и биты, которые появляются дважды, дважды:

0111 (bits that appear once or twice) + 0100 (bits that appear twice)