python - Python 中基于十六进制的 FizzBu​​zz

Question

我相信你们中的大多数人应该熟悉 FizzBu​​zz 是什么。

对于那些不知道我在这里说什么的人。 FizzBu​​zz 是这样的:

Write a program that prints the numbers from 1 to 100. But for multiples of three print "Fizz" instead of the number and for the multiples of five print "Buzz". For numbers which are multiples of both three and five print "FizzBuzz".

对于你们中的大多数人来说，这可能很容易创建。

虽然在线浏览后，我发现一些帖子要求他们不要使用模数运算符。

我发现这段 python 代码很有趣:

m = [None, "Fizz", "Buzz", "FizzBuzz"]
v = 0x30490610
for i in range(1, 101):
    j = v & 3
    print(m[j] if j else i)
    v = v >> 2 | j << 28

结果:

1
2
Fizz
4
Buzz
Fizz
7
8
Fizz
Buzz
11
Fizz
13
14
FizzBuzz
16
17
Fizz
19
Buzz
Fizz
22
23
Fizz
Buzz
26
Fizz
28
29
FizzBuzz
31
32
Fizz
34
Buzz
Fizz
37
38
Fizz
Buzz
41
Fizz
43
44
FizzBuzz
46
47
Fizz
49
Buzz
Fizz
52
53
Fizz
Buzz
56
Fizz
58
59
FizzBuzz
61
62
Fizz
64
Buzz
Fizz
67
68
Fizz
Buzz
71
Fizz
73
74
FizzBuzz
76
77
Fizz
79
Buzz
Fizz
82
83
Fizz
Buzz
86
Fizz
88
89
FizzBuzz
91
92
Fizz
94
Buzz
Fizz
97
98
Fizz
Buzz

我的问题是它是如何做到的？

我知道“v”变量包含一个十六进制值。

这如何实现创建 FizzBu​​zz？您如何向初学者解释这一点？

Answer 1

首先，我们观察到 FizzBu​​zz 模式是循环的，长度为 15，因为 n % 3 = (n + 15) % 3 , 和 n % 5 = (n + 15) % 5 .

n 是否可以被 3 和/或 5 整除可以用两位信息存储:00 表示两者都不是，01 表示可以被 3 整除，10 表示可以被 5 整除，11 表示可以同时被 3 和 5 整除。

FizzBu​​zz 对于数字 1 到 15 的“答案”如下，从右到左:

11 00 00 01 00 10 01 00 00 01 10 00 01 00 00。

请注意，每三个位对都设置了右位，每五个位对设置了左位。最右边的一对对应数字1，最左边的一对对应数字15。把左位和右位分开可能更清楚:

v5:    1. 0. 0. 0. 0. 1. 0. 0. 0. 0. 1. 0. 0. 0. 0.
v3:    .1 .0 .0 .1 .0 .0 .1 .0 .0 .1 .0 .0 .1 .0 .0
v5|v3: 11 00 00 01 00 10 01 00 00 01 10 00 01 00 00

如果我们将这串位转换为十六进制，我们会从您的代码片段中得到魔法常量 v:0x30490610 .

我们可以提取v的低两位用表达式 j = v & 3 ，因为数字 3 设置了底部的两位，其余未设置。 (这是 Python 的“按位与”运算符。)

我们可以通过移动 v 来围绕 2*15 = 30 位循环向右两位 v >> 2 ，然后在另一端添加两位，(v >> 2) | (j << 28) . (这些是 Python 的左移和右移运算符，它们也以按位方式工作。)

这样，v可以看作是一个包含 2 位元素的“队列”，每个元素对应于接下来要处理的 15 个数字之一的“正确 FizzBu​​zz 答案”。一旦一个元素j从这个队列中弹出，它被推到另一端，所以它在从现在开始的 15 次迭代后再次准备就绪。

最后一件事:语法 print(m[j] if j else i)表示“如果 j 不是伪值，例如 0，则打印 m[j] ；否则，打印 i 。”自 m[1] , m[2]和 m[3]包含与 FizzBu​​zz 答案的 2 位表示对应的正确字符串，以及 j始终在 0 到 3 的范围内，输出是正确的。

作为练习，尝试更改 v至 0x39999999看看你能否解释这种行为。 (提示:十六进制的 9 是二进制的 10 01。)

更新:这是该程序的一个变体。我已经替换了十六进制值 v通过显式队列 q的 react ，和可怕的样子 v = v >> 2 | j << 28已被从前面弹出并向后推，q.append(q.pop(0)) 取代.

q = ['', '', 'Fizz', '', 'Buzz',
     'Fizz', '', '', 'Fizz', 'Buzz',
     '', 'Fizz', '', '', 'FizzBuzz']
for i in range(1, 101):
    print(q[0] or i)
    q.append(q.pop(0))

我们还可以添加一个单独的fizz和 buzz队列:

f = ['', '', 'Fizz']
b = ['', '', '', '', 'Buzz']
for i in range(1, 101):
    print((f[0] + b[0]) or i)
    f.append(f.pop(0))
    b.append(b.pop(0))

自 ''是一个虚假的值(value)，(f[0] + b[0]) or i将打印整数 i每当f[0]和 b[0]是空字符串。