假设我们有一个二进制计数器，它支持两种操作：将所有位递增和重置为零。如果单个位的修改或检查需要 Theta(1) 时间，那么如何将计数器实现为位数组，以便初始零计数器上的任何递增和复位操作序列都需要 O(n) 时间？
通过聚合分析，并考虑到并非所有位每次都必须翻转的事实，我能够看到只允许递增的计数器需要 O(n) 时间进行 n 次操作。但我坚持如何实现增量重置计数器。据我所知，翻转就是翻转，没有什么能比平常更快地神奇地使 1111 变为 0000。但是，我确实注意到，通过增量操作，我们不会经常遇到超级昂贵的全 1 情况。
我想真正的问题是，实际上是否有一种策略可以使用重置实用程序来实现高效的计数器，或者我只是想证明它会变成一个只有增量操作的计数器？我唯一的提示是“保留指向高位 1 的指针”，这似乎暗示了前者。