How does this equation x + y = x & y + x | y hold true ( assuming x, y > 0)?

user_13163286 0
Viewed 172

I've recently participated in a code forces contest. In the editorial section of the contest, I got to see one of the beautiful relations between bitwise operators which is x + y = x & y + x | y. I don't know the proof yet. I took a few numbers to see if this equation was true. I got excited to know the proof. I looked it up online and couldn't find any meaningful references. please help me find the proof or at least give me the intuition behind this beautiful equation. Thanks in advance

bitset bit c++
3 Answers

Let's say you're doing a + b.

Notice that swapping i-th digit (counting from the rightmost digit) of a with i-th digit of b doesn't affect the sum. Example: 123 + 456 == 156 + 423. This works regardless of the choice of the base, so it works for binary addition too.

Next, notice that the transition from a + b to a&b + a|b can be done by swapping some of the digits in the way described above (in binary). If a[i] == 1 and b[i] == 0, then swap a[i] and b[i]; after that, a becomes a&b and b becomes a|b. Thus this transition doesn't affect the result.

user_27520750

So, whenever you are trying to figure out bitwise calculations, the easiest way would be make a chart for all situation, especially when there are only so little variables.

 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

Now you might be able to see:

  • if A == B, then A + B and A & B + A | B are essentially the same.
  • if A != B, then A & B + A | B might change the order of the two value, but of course, A+B=B+A, so they are essentially the same as while.
user_128616390

for x and y, you can take apart the bits, add them together, and get the same answer right?
example:

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

now. reviewing your logical operators:
a & b gives you the bits that are in both numbers (read: count of 2)
a | b gives you the bits that are in either number (read: count of ≥1)

so basically, you're taking the bits that are in either number, summing them together: 

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

you're also taking the bits that are in both numbers (i.e. the bits that you need to count twice), and adding that to the sum:

0100 == 0100 (in x, y)

so, you end up adding the bits that appear once, once, and the bits that appear twice, twice:

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