二进制

奇偶性

原理说明:

一个整数的二进制最低位(也就是最后一位) 表示这个数是奇数还是偶数
二进制中:
- 如果最后一位是 0 ,说明这个数是偶数
- 如果最后一位是 1 ,说明这个数是奇数

举例:

十进制数	二进制表示	最低位	奇偶性
4	`100`	`0`	偶数
7	`111`	`1`	奇数
10	`1010`	`0`	偶数
15	`1111`	`1`	奇数

数学公式:

parity (n) = n mod 2 = n & 2 = {\begin{cases} 0, & 若 n 为偶数 \\ 1, & 若 n 为奇数 \end{cases}

快速幂

快速幂算法是一种高效计算 $$n^k\mod m$$ 或 $$ n^k $$ 的算法，特别适合用于大整数幂的计算。

前情提要：

我们在计算 $$n^{k}$$ 次时，需要计算 $$ k $$ 次，时间复杂度为 $$O(k)$$，实际上我们可以大大减少这个次数

原理说明：

1.我们以 $$n^{k}=3^{13}$$ 为例，将指数 $$k=13$$ 用二进制表示：

k = 13 = (1101)_{2}

2.重要的来了，我们将原式按二进制每位展开得：

13 = (1101)_{2} = (1000)_{2} + (100)_{2} + (00)_{2} + (1)_{2} = 8 + 4 + 0 + 1

3.注意到 $$13$$ 变成了 $$8 +4+0+1$$ ，也就是 $$1·2^3+1·2^2+0·2^1+1·2^0$$ :

3^{13} = 3^{1 \cdot 2^{3} + 1 \cdot 2^{2} + 0 \cdot 2^{1} + 1 \cdot 2^{0}}

每一项前面的1和0就是对应的二进制位，所以只保留前面是1的项，因为0的项都是0

4.让我们用通用的公式把 $$k$$ 展开成二进制(对应第1步)：

k = (k_{b} k_{b - 1} k_{b - 2} . . . k_{0})_{2} k_{i} \in {0, 1}

5.所以（对应第2步）:

k = (k_{b} k_{b - 1} k_{b - 2} . . . k_{0})_{2} = (k_{b} 0. . .0)_{2} + (k_{b - 1} 0. . .0)_{2} + . . . + (k_{0})_{2} = k_{b} 2^{b} + k_{b - 1} 2^{b - 1} + . . . + k_{0} 2^{0}

6.最终（对应第3步）：

n^{k} = n^{k_{b} 2^{b}} \cdot n^{k_{b - 1} 2^{b - 1}} \cdot . . . \cdot n^{k_{0} 2^{0}}

7.原本需要算 $$k$$ 次，现在只需要算二进制位为1的个数后，再将各项相乘即可，合计约为 $$O(\log k)$$ 次

图解 $$2^{13}$$：

步骤	当前二进制位 $$b_i$$	$$n$$	result 累乘	解释
初始	-	$$n=3$$	$$1$$	初始值
1	$$b_0 = 1$$	$$n=3$$	$$1 \times 3 = 3$$	低位为1，乘上 n
		$$n \leftarrow n^2 = 3^2 = 9$$	-	base 平方
2	$$b_1 = 0$$	$$n = 9$$	$$3$$	当前位为0，不乘
		$$n \leftarrow n^2 = 9^2 = 81$$	-	base 平方
3	$$b_2 = 1$$	$$n = 81$$	$$3 \times 81 = 243$$	乘上 81
		$$n \leftarrow n^2 = 81^2 = 6561$$	-	base 平方
4	$$b_3 = 1$$	$$n = 6561$$	$$3 \times 6561 = 1594323$$	乘上 6561
		-	$$n^k = 1594323$$	计算结束

代码实现：

python

def quick_power(a, b):
    result = 1
    base = a
    exponent = b

    while exponent > 0:
        if exponent & 1:          # 如果当前最低位是1，乘上base
            result *= base
        base *= base              # base平方
        exponent >>= 1            # 指数右移一位（除以2）
    return result

二进制 ​

奇偶性 ​

快速幂 ​

二进制

奇偶性

快速幂