README.md

comments	difficulty	edit_url	tags
true	中等	https://github.com/doocs/leetcode/edit/main/solution/3100-3199/3125.Maximum%20Number%20That%20Makes%20Result%20of%20Bitwise%20AND%20Zero/README.md	贪心 字符串 排序

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

English Version

题目描述

给定一个整数 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。

 

提示：

• 1 <= n <= 1015

解法

方法一：位运算

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

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

Python3

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

Java

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

C++

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

Go

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