求集合 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 where 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 并且因为逻辑 and 运算符不能输出大于 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 因为您已经将这些字母用于其他含义。

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

Find the maximum of a & b in a set s = {1, 2, ... n } lesser than a certain value k

python

algorithm

boolean-logic

bit-manipulation

bitwise-operators