turzo_sawroop's blog

By turzo_sawroop, history, 3 months 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://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

»
3 months 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?

  • »
    »
    3 months ago, # ^ |
    Rev. 6   Vote: I like it 0 Vote: I do not like it

    Suppose I want to subtract a from b :

    a : 11110001100

    b : 00010110000

    Here only in the 5th and 6th indexes from right has 0 for a and 1 for b.So we find :

    x : 00000110000

    Edit :

    So yes x = (bitwise not of a) & b,I just found it.Thanks for your observation.I will update my blog

»
3 months 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)

  • »
    »
    3 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    You can even turn it into : b=x+(a&b) My purpose to bring a-b in equation is that somewhere in my head I also have plans of setting an interactive problem

»
3 months ago, # |
  Vote: I like it +1 Vote: I do not like it

Thank you so much!!

»
3 months 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))
»
3 months 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.

»
3 months 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

»
3 months 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!

  • »
    »
    3 months 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.

»
3 months ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

we can write a|b =(a^b)^(a&b) because a^b handles all those bits where in a and b are not same .And when both the bits are 1 a&b will handle .And when both are 0 it is implicitly handled. From this we can get all those stuff like a^(a|b)=b^(a&b) and b^(a|b)=a^(a&b) ,etc.