CODEWITHSUNDEEP
algorithm
user3840069
user3840069

Reputation: 765

Maximum AND of two numbers

Given two numbers A and B what can be the maximum number that can be formed by AND operation of any two numbers x and y between A and B it means A ≤ x < y ≤ B.

Example : A=1 and B=3 then answer is 2.

I can't go for brute as both A and B can go upto 10^18

Upvotes: 1

Views: 124

Answers (2)

Ilmari Karonen
Ilmari Karonen

Reputation: 50338

To expand on Pascal Cuoq's excellent answer, if we allow A < 0 and assume two's complement arithmetic (which is what essentially all modern computers use for signed integers), then we again have several cases:

  • If A < 0 ≤ B, then we may choose x = -1 and y = B, in which case x & y = B.

  • If A < B < 0, then everything works just like for positive numbers: if B is odd, or if A = B-1, then the optimal choice is x = B-1, y = B; otherwise it is x = B-2, y = B-1.

(The reason it works out exactly the same way is because two's complement signed arithmetic is essentially identical to unsigned binary arithmetic, except that we interpret numbers with their highest bit set as negative. Thus, the only really new case is the one where the range from A to B "wraps around" from -1 to 0.)

Summing up these results, we have that, for A ≤ x < y ≤ B, with any given (possibly signed two's complement) A and B, the maximum of x & y is:

  • If A < 0 ≤ B, then x = -1 and y = B yield x & y = B.

  • Otherwise, if B is odd, x = B-1 and y = B yield x & y = B-1.

  • Otherwise, if B > A+1, then x = B-2 and y = B-1 yield x & y = B-2.

  • If none of the above hold, the only remaining case is B = A+1 (with B even); in this case, the only possible choice is x = A, y = B; whatever x & y equals in this case, it is trivially the maximum.

Upvotes: 1

Pascal Cuoq
Pascal Cuoq

Reputation: 80305

Note: this answer assumes A ≥ 0, which is fair considering the question is not tied to a particular language or integer representation that would give meaning to bit operations on negative integers.

If B is odd, the maximum x & y is B-1, obtained by picking y = B and x = B-1.

If B is even and A is low enough to allow to pick y = B-1 and x = B-2, then the maximum is B-2, for this choice of x and y. Otherwise, there is only one choice, B & (B-1), whatever that evaluate to.

Upvotes: 3

Related Questions