python - 使用 "bitwise or of x and y"解决计数算法

Question

我正在分析 Codility ( Frog_river_one) 中计数练习的解决方案。
我见过的大多数解决方案都是基于循环遍历给定数组的位置和值。我遇到的解决方案之一似乎以不同的方式解决了这个问题。

我知道那里使用了“x 和 y 的按位或”，但是我不明白解决方案的逻辑。特别是 checker=checker| 1<<(A[x]-1) 部分
谁能解释一下？

问题

A small frog wants to get to the other side of a river. The frog is currently located at position 0, and wants to get to position X. Leaves fall from a tree onto the surface of the river. You are given a non-empty zero-indexed array A consisting of N integers representing the falling leaves. A[K] represents the position where one leaf falls at time K, measured in minutes. The goal is to find the earliest time when the frog can jump to the other side of the river. The frog can cross only when leaves appear at every position across the river from 1 to X.

The solution

A= [1,3,1,4,2,3,5,4]

def solution(X, A):
    checker=0
    final_val=pow(2,5)-1
    for x in range(len(A)):
        checker=checker| 1<<(A[x]-1)

        if(checker==final_val):
            return x
    return -1

Answer 1

实际上是方法solution应略微更改为:

def solution(X,A):
    checker = 0
    final_val = pow(2,X) - 1
    for x in range(len(A)):
        checker = checker | 1 << (A[x] - 1)

        if(checker == final_val):
            return x
    return -1

A = [1,3,1,4,2,3,5,4]

print(solution(5,A))

此算法背后的基本思想是确保所有树叶都落在河上，直到并包括位置 X。通过使用叶子位置的按位运算和二进制表示。

为了使这项工作你定义final_val等于2^X -1 .在 X 的情况下是5 , final_val是2^5 - 1 = 31 .

然后您遍历列表 A .

这是最有趣的部分。

checker = checker | 1 << (A[x] - 1)  

你初始化checker等于0 .

那我们把上面的表达式分解一下:

1 << (A[x] - 1)与 2^(A[x] - 1) 相同。此操作将二进制 1 向左移动 A[x] - 1' bits. This operation is done to make sure that the leave exists at position。 [x]`。

然后是 |运算符(OR)。在这种情况下，这是某种 plus运算符，但它不添加重复项。

那么让我们通过给定的示例来说明它是如何工作的。

x = 0: 

1 << A[0] - 1 which is 1 << 1 - 1
                       1 << 0

没有转变。 1 仍然是 1。

checker = 0 | 1

按位|给出 1。

所以 checker现在是 1。这意味着在位置 1 处有一片叶子.

x = 1:

1 << A[1] - 1 which is 1 << 3 - 1
                       1 << 2

所以现在 1 在二进制中变成 100。这意味着在位置 3 处有一片叶子.

然后:

checker = 1 | 100

实际上是001 | 100这给出了 101 .

x = 2:

checker = 101 | 1 << 0
        = 101

注意这里的位置1已经出现，所以它不会改变 checker变量。

x = 3:

checker = 101 | 1 << 3
        = 101 | 1000
        = 0101 | 1000
        = 1101

现在checker是1101 .这意味着在位置 4 处有一片叶子.

x = 4:

checker = 1101 | 1 << 1
        = 1101 | 10
        = 1101 | 0010
        = 1111

这意味着在位置 2 处有一片叶子.

x = 5:            

checker = 1111 | 1 << 4
        = 1111 | 10000
        = 01111 | 10000
        = 11111

这意味着在位置 5 处有一片叶子.

但这是 Frog 需要到达的位置。

这就是为什么有一个比较 checker 的检查条件与 final_val每次迭代。

所以我们看到11111等于final_val (31二进制为11111)算法返回5的位置哪个6 .

请注意，如果某些位置没有出现在 5 之前，例如而不是 2有1 ，那么算法将返回 -1，因为 Frog 无法到达位置 5。 .