# 3125. Maximum Number That Makes Result of Bitwise AND Zero ðŸ”’

## Description

Given an integer n, return the maximum integer x such that x <= n, and the bitwise AND of all the numbers in the range [x, n] is 0.

Example 1:

Input: n = 7

Output: 3

Explanation:

The bitwise AND of [6, 7] is 6.
The bitwise AND of [5, 6, 7] is 4.
The bitwise AND of [4, 5, 6, 7] is 4.
The bitwise AND of [3, 4, 5, 6, 7] is 0.

Example 2:

Input: n = 9

Output: 7

Explanation:

The bitwise AND of [7, 8, 9] is 0.

Example 3:

Input: n = 17

Output: 15

Explanation:

The bitwise AND of [15, 16, 17] is 0.

Constraints:

• 1 <= n <= 1015

## Solutions

### Solution 1: Bit Manipulation

We can find the highest bit of $1$ in the binary representation of $n$. The maximum $x$ must be less than $n$ and this bit is $0$, and all other lower bits are $1$, i.e., $x = 2^{\text{number of the highest bit}} - 1$. This is because $x \text{ and } (x + 1) = 0$ must hold.

The time complexity is $O(\log n)$, and the space complexity is $O(1)$.

• class Solution {
public long maxNumber(long n) {
return (1L << (63 - Long.numberOfLeadingZeros(n))) - 1;
}
}

• class Solution {
public:
long long maxNumber(long long n) {
return (1LL << (63 - __builtin_clzll(n))) - 1;
}
};

• class Solution:
def maxNumber(self, n: int) -> int:
return (1 << (n.bit_length() - 1)) - 1


• func maxNumber(n int64) int64 {
return int64(1<<(bits.Len64(uint64(n))-1)) - 1
}