Hi All ! Recently I and turzo_sawroop have done some observations on bitwise operations and found these equations and properties that you may find helpful. I want to share them with you in a nutshell. Here is a shortlist of them:
Some properties of bitwise operations:
- a|b = a⊕b + a&b
- a⊕(a&b) = (a|b)⊕b
- b⊕(a&b) = (a|b)⊕a
- (a&b)⊕(a|b) = a⊕b
Addition:
- a+b = a|b + a&b
- a+b = a⊕b + 2(a&b)
Subtraction:
- a-b = (a⊕(a&b))-((a|b)⊕a)
- a-b = ((a|b)⊕b)-((a|b)⊕a)
- a-b = (a⊕(a&b))-(b⊕(a&b))
- a-b = ((a|b)⊕b)-(b⊕(a&b))
Hope you like it. Please let me know if you find any issues. All of these properties are elaborated in this blog here. You can also check it out to learn more!
Third equation is deductible from the second if you apply $$$\oplus a\oplus b$$$ to both sides
it is helpful
This is helpful for solving this problem, https://mirror.codeforces.com/problemset/problem/1556/D Thank you srlabib and turzo_sawroop!!
thanks bro solved C in today's contest using one equation from here
which one did you use?
a + b = a ^ b + 2 (a & b)
the 2nd addition eqn . Making a&b == 0 .
very useful
Are these equations only valid for 2 variables ? Or these can be generalized for any number of variables ?
only 2 variable cant be generalised further
In fact you can replace $$$b = c+d, b = c\oplus d$$$, etc. for any positive integer then use mathematical induction for a generalized formula.
Edit: I found this not working.
My lazy ass never tries to memorize them. I kept coming back here 6–7 times just to look at the equations.
commenting so i can save
Commenting to save