Rely integers lower than A in order that Bitwise AND of B with XOR of A and the quantity is 0

Given two constructive integers A and B, the duty is to search out the variety of integers X such that (A⊕X ) & B = 0 and 0 ≤ X < A the place ⊕ is bitwise XOR and & is bitwise AND operator.

Examples:

Enter: A = 3, B = 5
Output: 1

Clarification: Right here A = 3, B = 5. So we have to discover the variety of X,  
which fulfill 0≤X<3, and (3⊕X)&5=0.
( 011 ⊕ 000 ) & 101 = 011 & 101 = 001 ≠ 0
( 011 ⊕ 001 ) & 101 = 010 & 101 = 000  
( 011 ⊕ 010 ) & 101 = 001 & 101 = 001 ≠ 0
So,  X = 1 solely satisfies the necessities. So the reply is 1.

Enter: A = 8, B = 4
Output: 4

Strategy: The thought to resolve this downside is:

The bitwise and of A⊕X with B must be 0. 

• This implies if a bit is about in B, it is going to be set in X if and solely whether it is set in A. In different phrases, if some little bit of B is about, there may be precisely one selection for such a bit in X.
• After this, we apply a classical approach when counting issues that should be lexicographically smaller than one thing else. Iterate over the positions, and repair the one that’s the first to be strictly much less, then we now have full freedom in all following positions.
  • That’s, iterate bits from 30 right down to 0. Suppose we’re at the moment on the i^th bit. We are going to assume that the bits from 30 to (i+1) of each A and X are equal, and the i^th little bit of X is strictly lower than the i^th little bit of A (that is solely potential when the i-th little bit of A is 1, and the i^th little bit of B is just not 1).
  • Now, bits 0 to i−1 are completely free (apart from the restriction on set bits of B), and every of those have 2 selections. So, if there are c such free bits, add 2^c to the reply.

Comply with the given steps to resolve the issue:

• Iterate from i = 30 to 1.
  • If the i^th bit is both set in B or not set in A, do nothing
• In any other case, depend the variety of bits from 0 to i−1 that aren’t set in B. If this quantity is c, add 2^c to the reply.

Beneath is the implementation of the above strategy.  

Time Complexity: O(logN) 
Auxiliary House: O(1)