### gXa's blog

By gXa, history, 20 months ago, ,

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.

• 0

 » 20 months ago, # | ← Rev. 4 →   0 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) = 0Therefore the number of solutions is ∞ (for positive w).
•  » » 20 months ago, # ^ |   0 you are right that is why I am asking about constraints.constraints?
 » 20 months ago, # | ← Rev. 4 →   0 I guess the first equation should look like a + b = w instead of a + w = b. In case of a + b = wIn this case answer is equal to 2 ones(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 = wAs 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 2 ones(w)·1 zeroes(w) which is equal to 2 ones(w). In case of a + w = bIf 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: w | 1101 a | + 11 b | = 10000 w | 1101 a | + 10011 b | = 100000 w | 1101 a | + 110011 b | = 1000000 w | 1101 a | + 1110011 b | = 10000000 w | 1101 a | + 11110011 b | = 100000000 w | 1101 a | + 111110011 b | = 1000000000 As we have no other limitations answer is ∞ for any positive w.
•  » » 5 weeks ago, # ^ |   0 What if there is a limit for case a + w = b
•  » » 5 weeks ago, # ^ |   0 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.