增加无限二进制计数器 [英] increment an infinite binary counter

问题描述

从编码采访摘自：

你将如何实现在0 递增无限二进制计数器（1）的时间复杂度？

How would you implement an infinite binary counter with increment in O(1) time complexity?

我想计算的第一和第二位最右侧的 0 ，但我不知道如何实现这一点。

I thought to calculate the first and second position of the rightmost 0, but I'm not sure how to implement this.

无限计数意味着你可以增加的无数次（比MAX_INT更高）。

"Infinite counter" means you can increment an infinite number of times (greater than MAX_INT).

推荐答案

我尝试：

我们一直在连续聚合 1 或 0 。

we keep an aggregation on consecutive 1 or 0.

意味着111000111为＆lt; 1,0>＆LT; 3,1>＆LT; 3,0>＆LT; 3,1>

meaning 111000111 is <1,0> <3,1> <3,0> <3,1>

我可以重新present这与以下DS：

I can represent this with the following DS:

节点{位：布尔，计数器：长}清单

List of Node { digit : bool, counter: long}

1），如果所述第一体是1的的。事实证明散装0`s的，把第二天0到1。

1) if the first bulk is of 1's. it turns to bulk of 0`s and turn the very next 0 to 1.

现在我们检查，如果我们可以聚合的1的散货。

we now check if we can aggregate bulks of 1's.

2）如果第一大部分是0的，我们做的第一个数字1，看看我们是否可以汇聚为1。

2) if the first bulk is of 0's, we make the first digit 1. and see if we can aggregate 1's.

例如答：

意味着111000111为＆lt; 1,0>＆LT; 3,1>＆LT; 3,0>＆LT; 3,1>

meaning 111000111 is <1,0> <3,1> <3,0> <3,1>

读数：三位 1 位，三 0 位，三 1 数字，有一个 0 数字

reading: three 1 digits, three 0 digits, three 1 digits, one 0 digits

增量（）

＆LT; 1,0>＆LT; 3,1>＆LT; 2,0>＆LT; 1,1>＆LT; 3,0>

<1,0> <3,1> <2,0> <1,1> <3,0>

例如乙：

＆LT; 1,0>＆LT; 3,1>＆LT; 1,0>＆LT; 3,1>

<1,0> <3,1> <1,0> <3,1>

增量（）

＆LT; 1,0>＆LT; 3,1>＆LT; 1,1>＆LT; 3,0>

<1,0> <3,1> <1,1> <3,0>

聚集：

＆LT; 1,0>＆LT; 4,1>＆LT; 3,0>

<1,0> <4,1> <3,0>

总是会有变化的常量号码（最多最右侧的0位）

There will always be const number of changes (up to the right most 0 digit)

和电源设为大宗 1 s的只是toggeling布尔成员。这是不变的。

and turnning bulk of 1s is just toggeling the boolean member. which is constant

这篇关于增加无限二进制计数器的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！