gXa's blog

By gXa, history, 20 months ago, In English,

There are 3 integers a, b, w.

There are 2 equations –

w+a=b

a (bitwise AND) b = 0;

I was given the value of w and he asked me to calculate the number of pairs (a, b) satisfying the two equations.

 
 
 
 
  • Vote: I like it
  • 0
  • Vote: I do not like it

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

Let i be the left-most set bit in m (0 -based), then for ever a = "111111111..00000", where 1 appears aleast two times, and zero appears i times, then a&b = a&(a + w) = 0

Therefore the number of solutions is (for positive w).

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

    you are right that is why I am asking about constraints.

    constraints?

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

I guess the first equation should look like a + b = w instead of a + w = b.

In case of a + b = w
In case of a + w = b
  • »
    »
    5 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    What if there is a limit for case a + w = b

  • »
    »
    5 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Ya,if it is a+b=w then the solution will narrow down to find (a,b) such that a xor b=w but here the equation w+a=b is kinda bizarre in terms of generality.