turzo_sawroop's blog

Every Possible Bitwise Equations we could Make
By turzo_sawroop, 3 years ago, In English

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://mirror.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.

  • Vote: I like it
  • +66
  • Vote: I do not like it

Comments Comments (11)
| Write comment?
»
3 years ago, # |
  Vote: I like it +27 Vote: I do not like it

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

Do you mean x = ~a & b?

→ Reply
»
3 years ago, # |
← Rev. 3   Vote: I like it 0 Vote: I do not like it 
a-b=a-(a&b)-x

it basically mean b = (b & x) + (b & ~x)

→ Reply
»
3 years ago, # |
  Vote: I like it +1 Vote: I do not like it

Thank you so much!!

→ Reply
»
3 years ago, # |
  Vote: I like it +2 Vote: I do not like it

Here are some more equations of subtraction using bitwise operators!
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))
→ Reply
»
3 years ago, # |
  Vote: I like it +15 Vote: I do not like it

You can derive most of these by imagining A and B as Venn diagrams.

→ Reply
  • »
    »
    3 years ago, # ^ |
      Vote: I like it +3 Vote: I do not like it

    Your comment is gold! It is because of this comment I started to think in terms of Venn diagrams and these formulas become so obvious with that!

    P.S Consider set A having indices of all bits which equals 1 in binary representation of number A. and the same for set B. It's so obvious that intersection of these set gives bitwise AND and union gives bitwise OR.

    → Reply
»
3 years ago, # |
  Vote: I like it +1 Vote: I do not like it

here is another blog like that, hope that's would be helpful who finding such type topics This

→ Reply
»
3 years ago, # |
  Vote: I like it +2 Vote: I do not like it

This is a really nice reference, thanks! I think you can also find some more info on this in the competitive programmer's handbook chapter 10 (specifically 10.2),but it doesn't have as much information on the different operations than the basics. Thanks again!

→ Reply
  • »
    »
    3 years ago, # ^ |
      Vote: I like it +2 Vote: I do not like it

    Thanks for appreciating our work!!!Codeforces has given us a life of purpose. So, it's just a little contribution from us for the community.

    → Reply
»
3 years ago, # |
  Vote: I like it +1 Vote: I do not like it

missed opportunity to call this The ultimate bitwise equation list xd

→ Reply
»
3 years ago, # |
  Vote: I like it +1 Vote: I do not like it

Wish I had seen this before came yesterday in CodeChef contest link By the way, nice work, helps a lot

→ Reply