1399. Maximum AND of Two Numbers After One Swap

Given two non-negative integers a and b, each fitting in the given number of bits, you may perform at most one swap: choose a bit position i in a and a bit position j in b (i and j may differ) and exchange the bit of a at position i with the bit of b at position j. Return the maximum possible value of a AND b after at most one such swap.

Input: A JSON object {"a": <integer>, "b": <integer>, "bits": <bit width>}.

Output: Return the maximum achievable value of a AND b.

Examples

Input: {"a":10,"b":5,"bits":4}
Output: 8
Explanation: Swapping a's bit 1 into b's bit 3 yields an AND of 8.

Input: {"a":6,"b":6,"bits":4}
Output: 6
Explanation: The numbers already AND to 6 and no swap improves it.

Constraints

• 1 <= bits <= 20
• 0 <= a, b < 2^bits

Asked by