3125. 使得按位与结果为 0 的最大数字 🔒

题目描述

给定一个整数 n，返回 最大的 整数 x 使得 x <= n，并且所有在范围 [x, n] 内的数字的按位 AND 为 0。

示例 1：

输入：n = 7

输出：3

解释：

[6, 7] 的按位 AND 为 6。

[5, 6, 7] 的按位 AND 为 4。

[4, 5, 6, 7] 的按位 AND 为 4。

[3, 4, 5, 6, 7] 的按位 AND 为 0。

示例 2：

输入：n = 9

输出：7

解释：

[7, 8, 9] 的按位 AND 为 0。

示例 3：

输入：n = 17

输出：15

解释：

[15, 16, 17] 的按位 AND 为 0。

提示：

我们可以找到 $n$ 的二进制表示中最高位的 $1$，那么最大的 $x$ 一定小于 $n$ 且该位为 $0$，其他低位均为 $1$，即 $x = 2^{\textit{最高位的位数} - 1} - 1$。这是因为 $x \textit{ and } (x + 1) = 0$ 一定成立。

时间复杂度 $O(\log n)$，空间复杂度 $O(1)$。

Python3JavaC++Go

class Solution:
    def maxNumber(self, n: int) -> int:
        return (1 << (n.bit_length() - 1)) - 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;
    }
};

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