请帮我理解位移操作

Question

def different(s):
   x = len(s)
   for i in range(1, 1 << x):
      u.append([s[j] for j in range(x) if (i & (1 << j))])

这个代码会接收一个列表，然后生成不同的组合。

(a,b,c) = ((a,b,c),(a,b),(a,c) ...)

但是这个范围是干嘛的？从1到什么？我不太明白"<<"这个符号。

还有，if (i & (1 << j))这段代码是做什么的？它是在检查i和2的j次方吗？我觉得这没什么意义。

Answer 1

<< 是一个二进制左移运算符。1 << x 可以理解为2的x次方。

Answer 2

range函数会返回一个从零开始，到给定数字减一的数字列表。它还有两种和三种参数的用法（更多信息可以查看文档）：

range(n) == [0, 1, 2, ..., n - 1]

<<是左移运算符，它的作用是把左边的数字乘以2的右边数字次方：

x << n == x * 2**n

因此，上面的range函数（range(1, 1 << x)）会返回[1, 2, 3, ..., 2**x - 1]。

在<<的第二种用法中，左移被用作位掩码。它会把1移动到第j位，并与i进行按位与运算，所以结果只有在i的第j位是1时，才会非零（并且通过if测试）。举个例子：

j = 4
1 << j = 0b1000 (binary notation)

i = 41 = 0b101001
i & (1 << j) = 0b101001
             & 0b001000
             = 0b001000 (non-zero, the if-test passes)

i = 38 = 0b100110
i & (1 << j) = 0b100110
             & 0b001000
             = 0b000000 (zero, the if-test fails)

简单来说，x & (1 << y)只有在x的第y位是1时才会非零。