python - 求集合 s = {1, 2, ... n } 中 a & b 的最大值小于某个值 k

Question

我正在使用 Python 语言来解决有关 HackerRank 的教程，可在此处获取:https://www.hackerrank.com/challenges/30-bitwise-and

挑战的要点是找到 a & b 的最大值其中 a, b ∈ s , s是这样定义的集合:s = {1, 2, ... n}其中 a < b .另一个条件是 a & b < k其中 2 <= k <= n .

给定的输入是 n和 k .

我设法得到一个 O(n^2)和 O(n)解决方案，但我正在努力想出一个 O(1)解决方案。

例如，下面是一个虚拟 O(n^2)解决方案:

def max_and(n, k):
    if (n < k) or (k < 2):
        raise ValueError()
    else:
        res = (0, 1, 0)
        for a in range(n + 1):
            for b in range(n + 1):
                if a < b:
                    temp = a & b
                    if res[2] < temp < k:
                        res = (a, b, temp)
        return res


for n in range(2, 10):
    print(["(n = {}, k = {}) = ".format(n, k) + str(max_and(n, k)) for k in range(2, n + 1)])

我注意到答案总是 k - 1或 k - 2这对我来说很有意义。

我认为这个想法是 a & b 的最大值约束小于 k并且由于逻辑与运算符不能输出大于 b 的数字。

HackerRank 上的一些人想出了一个 O(1) 的解决方案，但我真的不明白它是如何工作的:

a = k - 1
b = (~a) & -(~a)

if (a | b) > n:
    print (a - 1)
else:
    print (a)

特别是为什么b = (~a) & -(~a)

我的意思是我知道它可以更改为

Answer 1

让j = k - 1 , 让 unset_bit是两个的最低幂 (j & unset_bit) == 0 .

如果(j | unset_bit) <= n , 然后我们选择 a = j和 b = j | unset_bit对于 (a & b) == j 的最优值.

如果(j | unset_bit) > n , 那么不可能选择 a和 b会给我们(a & b) == j .我们根本没有两个数字可以选择所有必要的位集。自偶数 j会给我们 (j | unset_bit) == j+1 <= n , 我们必须有 j奇怪的。然后采摘a = j - 1和 b = j给我们(a & b) == j - 1 , 最高可能值。

---

您在 HackerRank 上看到的代码实现了这个想法。在您找到的代码中，他们的 a是我们的j , 和他们的 b是我们的unset_bit ，通过一些小技巧计算得出。我用过 j和 unset_bit而不是 a和 b因为您已经将这些字母用于其他含义。