When submitting a solution in C++, please select either C++14 (GCC 6-32) or C++17 (GCC 7-32) as your compiler. ×

gXa's blog

By gXa, history, 5 years 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

| Write comment?
»
5 years 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).

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

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

    constraints?

»
5 years 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
  • »
    »
    4 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

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