Please subscribe to the official Codeforces channel in Telegram via the link https://t.me/codeforces_official. ×

Every Possible Bitwise Equations we could Make

Revision en11, by turzo_sawroop, 2021-09-02 08:10:17

After recently concluded hacker cup qualification round I thought I would take a little rest from problem solving.But as I have some geniuses like srlabib around me I couldn't resist myself from thinking about some Bitwise Equations!!!

Most of the part is done by srlabib and I also contributed some from my side ( Especially the last one ) :

  • a+b = a|b + a&b

Now this is a very basic thing.This was a very crucial part in the last contests's problem D ( Take a Guess ).But how did we get this? Suppose we have two binary numbers 1010 and 0101, there is no chance of any carry in binary addition.In that case we can write :

a+b =a|b

But when we have carry, suppose we have : 1101(a) and 0101(b) then a & b works as the carry which we add further and the equation turns into :

a+b=a|b + a&b

Now I will talk about the sum-xor property :

  • a+b=a⊕b+2(a&b)

Well where does it come from?

It comes from the first equation that I described.But now let's break a & b here and bring xor into action:

We can express a | b as a⊕b + a&b which brings the equation :

a+b=a⊕b+2(a&b)

Now the last one : It is a special one for me because I derived it with my own hands, that is :

  • a-b=a-(a&b)-x

Now what is x?

x is a number which I created by turning the bits on in positions where a has bit 0 and b has bit 1

Now how did I get this equation?Here is how :

Imagine two binary numbers : a : 11010 b : 01110

we can write b as : 01010(a &b) + 00100(x) which leads us to the equation :

a-b=a-(a&b)-x

UPD : x is basically (bitwise not of a) & b

UPD : srlabib has come up with two more equations :

  • a^(a&b) = (a|b)^b
  • b^(a&b) = (a|b)^a

UPD :

Here are some more equations of subtraction using bitwise operators by srlabib!

As :

a-b = a-(a&b)-x

Here a-(a&b) and (a⊕(a&b)) are actually the same!

and x = (a|b)⊕a

So now it is clear that

  • a-b = (a⊕(a&b)) — ((a|b)⊕a)

Now

a⊕(a&b) = (a|b)⊕b

b⊕(a&b) = (a|b)⊕a

Using these two properties we can build four equations!

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))

UPD : Equations are given in a nutshell here : https://codeforces.com/blog/entry/94470

Hope you like it.If you guys have any observations please tell me.I will add it.And I and srlabib will be discussing more in the upcoming days about bits and I will keep adding those in this blog.

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en11 English turzo_sawroop 2021-09-02 08:10:17 92
en10 English turzo_sawroop 2021-09-01 20:24:19 4 Tiny change: '(a|b)⊕a)\nNow\na⊕(' -> '(a|b)⊕a)\n\nNow\na⊕('
en9 English turzo_sawroop 2021-09-01 19:57:14 510
en8 English turzo_sawroop 2021-09-01 12:35:36 121
en7 English turzo_sawroop 2021-09-01 00:31:09 4 Tiny change: '**UPD** : x is basica' -> '**UPD** : **x** is basica'
en6 English turzo_sawroop 2021-09-01 00:24:51 51
en5 English turzo_sawroop 2021-09-01 00:04:06 1 Tiny change: 'bits on in. positions' -> 'bits on in positions'
en4 English turzo_sawroop 2021-08-31 23:57:54 5 Tiny change: 'ep adding it in this b' -> 'ep adding those in this b'
en3 English turzo_sawroop 2021-08-31 23:55:22 8 Tiny change: 'ontests's D ( Take ' -> 'ontests's problem D ( Take '
en2 English turzo_sawroop 2021-08-31 23:54:54 6 Tiny change: 'ntests's Div-2 D ( Take ' -> 'ntests's D ( Take '
en1 English turzo_sawroop 2021-08-31 23:43:57 1902 Initial revision (published)