对数间隔快照

When making a series of updates to something, you may wish to also retain a series of snapshots in between updates. For example, you may want to track version history for edits to a document. With limited storage space available, you cannot have a snapshot between every update. You would prefer to have a higher density of recent snapshots and a lower density of long-ago snapshots because it's typically more important to have higher granularity for more recent snapshots.

在对某事物进行一系列更新时，你可能还希望保留更新之间的快照序列。例如，你可能希望跟踪文档编辑的版本历史。由于可用存储空间有限，你无法在每次更新之间都保留一个快照。你更希望最近快照的密度较高，而久远快照的密度较低，因为通常对更近的快照拥有更高的粒度更为重要。

This algorithm is a simple way to keep a set of snapshots logarithmically-spaced back in history. It only ever keeps around roughly 2 log2(n) snapshots for n updates, doesn't require any complex bookkeeping, and runs in O(1) time per update step.

该算法是一种简单的方法，用于在历史记录中以对数间隔保留一组快照。对于 n 次更新，它始终只保留大约 2 log2(n) 个快照，不需要任何复杂的簿记，并且每次更新步骤的运行时间为 O(1)。

The algorithm: After each step, add a new snapshot number n and delete the existing snapshot number n - (firstZeroBit(n) << d) where firstZeroBit(x) returns the value of the least significant zero bit of x. The value d is a customizable shift that determines the density of snapshots. It can be set to any positive integer but has been set to 2 for the visualization below. Here is a possible implementation of firstZeroBit:

算法： 每一步之后，新增一个快照编号 n，并删除已有快照编号 n - (firstZeroBit(n) << d)，其中 firstZeroBit(x) 返回 x 最低位零位对应的值。参数 d 是可自定义的位移，决定快照密度，可设为任意正整数，但在下方可视化中设为 2。以下是 firstZeroBit 的一种可能实现：

function

function

firstZeroBit(x) {

firstZeroBit(x) {

let

let

bit = 1

bit = 1

while

while

(bit && (x & bit) !==

(bit && (x & bit) !==

0

0

) bit <<=

) bit <<=

1

1

return

return

bit }

bit }

Here's a second possible (although less understandable) implementation of firstZeroBit that uses bit tricks and is equivalent to the first:

这是 firstZeroBit 的第二种可能实现（虽然可读性较差），它使用位技巧，与第一种实现等价：

function

function

firstZeroBit(x) {

firstZeroBit(x) {

return

r...