Счётчик Кнута

Счетчик Кнута (англ. Knuth's Counter) — структура данных, представленная избыточной двоичной системой счисления, где добавление единицы к числу выполняется за [math]O(1)[/math].

Неотрицательное целое число [math]N[/math] в избыточной двоичной системе счисления записывается в виде последовательности разрядов [math]d_n d_{n-1} \dotsc d_2 d_1[/math], где [math]n[/math] обозначает количество разрядов в числе, [math]d_i[/math] — [math]i[/math]–й разряд числа [math](1 \le i \le n)[/math], причем [math]d_i \in \{0,1,2\}[/math] и [math]\sum\limits_{i=1}^n d_i \cdot 2^i = N. [/math]

Алгоритм

Оригинальный алгоритм представлен в Clancy, Knuth и состоит из двух правил:

1. Найти младший разряд [math]d_i[/math] равный [math]2[/math] и, если таковой имеется, заменить последовательность [math]d_{i+1}d_i[/math] на [math](d_{i+1}+1)0[/math]
2. Заменить [math]d_1[/math] на [math]d_1+1[/math].

Чтобы достичь необходимой оценки и не выполнять каждый раз поиск для первого правила, можно хранить односвязный список позиций двоек в числе. Тогда чтобы найти младший разряд равный двум нужно просто взять первый элемент списка. Также, непосредственно перед изменением значений разрядов в правилах необходимо выполнять следующее:

1. Если [math]d_{i+1}=1[/math], то заменить первый элемент списка с [math]i[/math] на [math]i+1[/math], иначе удалить его.
2. Если [math]d_1=1[/math], то добавить в начало списка 1.

Проблемой может оказаться появление двух последовательных двоек, при этом перое правило может породить тройку, что недопустимо. Однако если между любой парой двоек всегда будет находится хотя бы один 0, то такой ситуации не возникнет. Покажем, что если это условие с нулем выполняется, то оно выполняется и после инкремента, рассмотрев основные случаи (в обозначениях левой части предполагается что правая двойка самая младшая из всех до инкремента):

• [math]\dotsc 2\dotsc 0\dotsc 12\dotsc [/math] переходит в [math]\dotsc 2\dotsc 0\dotsc 20\dotsc [/math], при этом в младшем разряде может появиться новая 2-ка и между ней следующей будет хотя бы один ноль.
• [math]\dotsc 2\dotsc 0\dotsc 02\dotsc [/math] переходит в [math]\dotsc 2\dotsc 0\dotsc 10\dotsc [/math], ситуация почти аналогична предыдущей.
• [math]\dotsc 202\dotsc [/math] переходит в [math]\dotsc 210\dotsc [/math], также гарантируется наличие нуля при появлении двойки в младшем разряде
• Появление двух двоек, если уже есть ровно одна возможно, тогда [math]\dotsc 12\dotsc 1[/math] переходит в [math]\dotsc 20\dotsc 2[/math], ясно что в этом случае между ними также будет хотя бы один ноль.

В таблице можно увидеть как будет изменятья представление при применении данных правил десять раз к нулю (представления чисел от 0 до 10):

Шаг	Представление	Шаг	Представление
0	0	5	21
1	1	6	102
2	2	7	111
3	11	8	112
4	12	9	121

Обобщение на системы с произвольным основанием

В общем случае подобные счётчики называются [math]b[/math]-ричными избыточными счетчиками (ИС), которые похожи на счетчик Кнута, но основание системы может быть произвольным, то есть [math]d_i \in \{0,1,\dotsc ,b\}[/math] и [math]\sum\limits_{i=1}^n d_i \cdot b^i = N[/math] , где [math]b[/math] — основание. Такие счетчики позволяют прибавить единицу к любому разряду, то есть увеличить число на [math]b^i[/math] за [math]O(1)[/math] Назовем такое представление регулярным, если между дувумя разрядами равными [math]b[/math] есть хотя бы один разряд отличный от [math]b-1[/math]. Операция исправления (fix) разряда [math]d_i=b[/math] в регулярной [math]b[/math]-ричного счетчика [math]d[/math] увеличивает [math]d_{i+1}[/math] на 1 и устанавливает [math]d_i[/math] в 0, образуая новый регулярный счетчик, представляющий то же число, что и [math]d[/math]. Чтобы добавить 1 к разряду [math]d_i[/math] регулярного ИС [math]d[/math], нужно сделать следующее:

1. Если [math]d_i=b[/math], исправить [math]d_i[/math].
2. Если [math]d_i=b-1[/math] и самый младший значащий разряд [math]d_j[/math], такой, что [math]j\gt i[/math] и [math]d_j \ne b-1[/math], равен [math]b[/math] (т.е. [math]d_j=b[/math]), применить операцию исправления к разряду [math]d_j[/math].
3. Добавить 1 к [math]d_i[/math].
4. Если [math]d_i=b[/math], исправить [math]d_i[/math].

Для реализации данной схемы, мы используем односвязный список разрадов от младших к старшим. В дополнение каждый разряд [math]d_i[/math] равный [math]b-1[/math] будет иметь указатель на самый младший разряд [math]d_j[/math], такой, что [math]j\gt i[/math] и [math]d_j \ne b-1[/math], если он равен [math]b[/math], иначе этот указатель будет на произвольный разряд [math]d_j[/math] ([math]j\gt i[/math]). Теперь, во время увеличения разряда [math]d_i[/math] на 1, будем проверять разряд по указателю вперед (п. 2).

Такое представление позволяет увеличиать произвольный разряд за константное время. Обновление указателя вперед происходит следующим образом: когда [math]d_{i+}[/math] становится равен [math]b-1[/math] при исправлении разряда [math]d_{i-1}[/math], устанавливаем указатель вперед разряда [math]d_{i}[/math] на [math]d_{i+1}[/math], если [math]d_{i+1}=b[/math], либо копируем указатель вперед из [math]d_{i+1}[/math] в [math]d_{i}[/math], если [math]d_{i+1}=b-1[/math]. При собственно добавлении единицы к разряду [math]d_i[/math], также необходимо обновлять его указатель вперед аналогичным образом, если этот разряд становится равен [math]b-1[/math].

Литература

• H. Kaplan и R. E. Tarjan. New heap data structures. 1998
• M. J. Clancy и D. E. Knuth. A programming and problem-solving seminar. Technical Report STAN-CS-77-606, Department of Computer Sciencr, Stanford University, Palo Alto, 1977.
• G. S. Brodal. Worst case priority queues. Proc. 7th annual ACM-SIAM Symposium on Discrete Algorithms (SODA 96), страницы 52-58. ACM Press, 1996.
• H. Kaplan и R. E. Tarjan. Purely functional representations of catenable sorted lists. Proceedings of the 28th Annual ACM Symposium of Computing, страницы 202-211. ACM Press, 1996

Смотрите также

• Амортизационный анализ
• Представление целых чисел: прямой код, код со сдвигом, дополнительный код