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

Счетчик Кнута (англ. 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 \leqslant i \leqslant n)[/math], причем [math]d_i \in \{0,1,2\}[/math] и [math]\sum\limits_{i=1}^n d_i \cdot 2^i = N. [/math]

Алгоритм

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

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], то добавить в начало списка [math]1[/math].

Проблемой может оказаться появление двух последовательных двоек, при этом перое правило может породить тройку. То есть недопустима следующая ситуация [math]\dotsc 22\dotsc \rightarrow \dotsc 30\dotsc[/math]. В свою очередь такая ситуация получается из этой [math]\dotsc 212\dotsc \rightarrow \dotsc 220\dotsc[/math]. Причем количество единиц между двойками может быть любое, в итоге это приведет к появлению тройки. Однако если между любой парой двоек всегда будет находится хотя бы один [math]0[/math], то такой ситуации не возникнет. Покажем, что что этот инвариант поддерживается после инкремента, рассмотрев возможные ситуации:

1. Число двоек не изменяется
   1. [math]\dotsc 2\dotsc 0\dotsc 12\dotsc 0 \rightarrow \dotsc 2\dotsc 0\dotsc 20\dotsc 1[/math].
   2. [math]\dotsc 02\dotsc 1 \rightarrow \dotsc 10\dotsc 2[/math].
   3. [math]\dotsc 2\dotsc 02\dotsc 1 \rightarrow \dotsc 2\dotsc 10\dotsc 2[/math] (частный случай предыдущего).
   4. [math] \dotsc 12 \rightarrow \dotsc 21[/math].
2. Пропадает одна двойка
   1. [math] \dotsc 02\dotsc 0 \rightarrow \dotsc 10\dotsc 1[/math].
   2. [math] \dotsc 02 \rightarrow \dotsc 11[/math].
3. Появление новой двойки
   1. [math]\dotsc 1 \rightarrow \dotsc 2[/math] (имеется в виду появление единственной двойки).
   2. [math]\dotsc 12\dotsc 1 \rightarrow \dotsc 20\dotsc 2[/math].
   3. [math]\dotsc 2\dotsc 0\dotsc 12\dotsc 1 \rightarrow \dotsc 2\dotsc 0\dotsc 20\dotsc 2[/math] (частный случай предыдущего).

Таким образом мы видим, что 0 всегда сохраняется.

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

Шаг	Представление
0	0
1	1
2	2
3	11
4	12
5	21
6	102
7	111
8	112
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] на [math]1[/math] и устанавливает [math]d_i[/math] в [math]0[/math], образуая новый регулярный счетчик, представляющий то же число, что и [math]d[/math]. Чтобы добавить [math]1[/math] к разряду [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
• http://www.cphstl.dk/Paper/Numeral-systems/mfcs-13.pdf
• Амортизационный анализ
• Представление целых чисел: прямой код, код со сдвигом, дополнительный код
• Список