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.
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.
| # | User | Rating |
|---|---|---|
| 1 | Benq | 3792 |
| 2 | VivaciousAubergine | 3647 |
| 3 | Kevin114514 | 3603 |
| 4 | jiangly | 3583 |
| 5 | strapple | 3515 |
| 6 | tourist | 3470 |
| 7 | dXqwq | 3436 |
| 8 | Radewoosh | 3415 |
| 9 | Otomachi_Una | 3413 |
| 10 | Um_nik | 3376 |
| # | User | Contrib. |
|---|---|---|
| 1 | Qingyu | 158 |
| 2 | adamant | 152 |
| 3 | Proof_by_QED | 146 |
| 3 | Um_nik | 146 |
| 5 | Dominater069 | 144 |
| 6 | errorgorn | 141 |
| 7 | cry | 139 |
| 8 | YuukiS | 135 |
| 9 | chromate00 | 134 |
| 9 | TheScrasse | 134 |
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).
you are right that is why I am asking about constraints.
constraints?
I guess the first equation should look like a + b = w instead of a + w = b.
In this case answer is equal to 2ones(w) where ones(w) is amount of ones in binary representation of w.
a&b = 0 says that there is no common set bit in a and b. In this case sum operation equals to bitewise-or operation, because there is no digit overflows in our sum.
So now we have these equations:
a&b = 0
a|b = w
As we only use bitwise operations we can solve the problem for each bit independently and then multiply our results for all bits.
If current bit in w is zero, only possible solution is a = 0; b = 0. Answer is 1.
If current bit in w is one, there are two solutions: a = 0; b = 1 and a = 1; b = 0. Answer is 2.
Final answer is 2ones(w)·1zeroes(w) which is equal to 2ones(w).
If w = 0 then we have a = b, and the only possible solution for this is a = b = a&b = 0.
If w is positive we can generate infinte amount of pairs (a, b) that satisfy both equations. Let's onsider w = 13 and look at binary presetation of some correct pairs (a, b). It is easy to see the pattern that generates some of them:
As we have no other limitations answer is ∞ for any positive w.
What if there is a limit for case
a + w = b