无法理解使用 while 循环求幂

Question

def pow(base, exp):
    result = 1
    while exp:
        if exp & 1:
            result *= base
        exp >>= 1
        base *= base
    return result

1. 为什么我们在exp & 1和exp >>= 1时将while循环分成两部分？

2. 我无法理解为什么我不能在第四行代码中使用 == 代替 &。它会给出错误的输出。

3. 为什么是 exp >>= 1 而不是 exp >= 1？

Answer 1

1. Why we divide the while loop in two part when 'exp & 1' and 'exp >>=1

只有第一个进行分隔，因为有一个 if 块。第二个是在循环的每次迭代中执行的赋值，无论第一个条件是否为真。第一个条件决定我们是否应该在临时结果中添加一些东西。

2. I am not able to understand why I cant use '==' in place '&' in fourth line of code. It will throwing wrong output.

==确实是错误的。 exp & 1 表达式（仅）检查 exp 的最低有效位。它将等同于 exp % 2。当 exp 为奇数时，两个表达式的计算结果为 1，而当 exp 为偶数时，两个表达式的计算结果为 0。

3. why 'exp>>=1' not 'exp>=1'

因为第二个不是赋值，而是比较。第一个是任务。它可以写得更冗长，如 exp = exp >> 1。这会将 exp 的位向右移动一位，相当于 exp = exp // 2.

算法

该算法在那篇维基百科文章中称为 "Exponentiation by squaring", and more precisely, the iterative version of the algorithm. See also the example implementations。

监控算法

您可以添加一些 print 调用以查看变量在算法过程中如何演变。例如，像这样：

def pow(base, exp):
    result = 1
    while exp:
        print("least significant bit of exp is {}".format(exp & 1))
        if exp & 1:
            print("  adapt result: {} * base {} => {}".format(result, base, result*base))
            result *= base
        print("shift exp (binary) {0:5b} => {1:5b}".format(exp, exp >> 1))
        exp >>= 1
        print("square base {} => {}".format(base, base*base))
        base *= base
    print("result {}".format(result))
    return result

result = pow(10, 6)

这输出：

least significant bit of exp is 0
shift exp (binary)   110 =>    11
square base 10 => 100
least significant bit of exp is 1
  adapt result: 1 * base 100 => 100
shift exp (binary)    11 =>     1
square base 100 => 10000
least significant bit of exp is 1
  adapt result: 100 * base 10000 => 1000000
shift exp (binary)     1 =>     0
square base 10000 => 100000000
result 1000000

Answer 2

1。为什么在exp & 1和exp >>= 1时将while循环分成两部分？

分支只发生在前者身上。如果 exp & 1 可以解释为真，则执行 result *= base。 exp & 1 基本上意味着“exp 是奇数吗？”，所以如果 exp 是奇数，就会发生 reult *= base。

2。我无法理解为什么我不能在第四行代码中使用 == 代替 &。它会给出错误的输出。

exp & 1 不是在测试 exp 是否等于 1，而是在 exp 和 1 之间执行 bitwise and。如前所述，这实际上只是检查是否esp 是奇数。

3。为什么是 exp >>= 1 而不是 exp >= 1？

exp >>= 1 是 bit-shifting（与之前相同的 link）exp 向右移动 1，不测试它是否大于或等于 1。