HotashCoder's blog

Is it possible?(Problem related bitwise)
By HotashCoder, history, 19 months ago, In English

a+b=x, a|b=y, a&b=z, a^b=k

If x,y,z,k is given, is it possible to find a-b?

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

Comments Comments (3)
| Write comment?
»
19 months ago, hide # |
← Rev. 2  
Vote: I like it 0 Vote: I do not like it

If we know, that a|b=y and a&b=z, then we can uniquely determine x and k, using this equations (you can read about it here)

a+b = a|b + a&b

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

In case we know y and z, determine:

x=y+z

k=x-2z

So from this point, we can use x and k only to check, if there exists a and b, that satisfy bitwise properties.

Let's assume that we find such a and b, that a|b=y and a&b=z, then notice, if we swap i-th bit of a and b, then x, y, z, k will not change, but a-b can

Example:

a=1100

b=1011

a-b=1

let's swap 3-rd bit:

a=1000

b=1111

a-b=-7

→ Reply
  • »
    »
    19 months ago, hide # ^ |
     
    Vote: I like it 0 Vote: I do not like it

    Thanks for your reply..

    but are you saying that directly getting (a-b) is not possible from the given values?

    → Reply
    • »
      »
      »
      19 months ago, hide # ^ |
       
      Vote: I like it 0 Vote: I do not like it

      Yes, a-b can have $$$2^d$$$ different values, where d is the number of bit positions, where a and b are different, so it isn't possible to get directly a-b, knowing only x, y, z, k

      → Reply