Изменения

'''Счетчик Кнута''' (англ. ''Knuth's Counter'') &mdash; {{---}} структура данных, представленная избыточной двоичной системой счисления, где добавление единицы к числу выполняется за <tex>O(1)</tex>.

Неотрицательное целое число <tex>N</tex> в ''избыточной двоичной системе счисления'' записывается в виде последовательности разрядов <tex>d_n d_{n-1} \dotsc d_2 d_1</tex>, где <tex>n</tex> обозначает количество разрядов в числе, <mathtex>d_i</mathtex> &mdash; {{---}} <tex>i</tex>&ndash;й разряд числа <tex>(1 \le leqslant i \le leqslant n)</tex>, причем <mathtex>d_i \in \{0,1,2\}</mathtex> и <mathtex>\sum\limits_{i=1}^n d_i \cdot 2^i = N.</mathtex>

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

# Если <tex>d_{i+1}=1</tex>, то заменить первый элемент списка с <mathtex>i</mathtex> на <mathtex>i+1</mathtex>, иначе удалить его.# Если <tex>d_1=1</tex>, то добавить в начало списка <tex>1</tex>.

тройку. То есть недопустима следующая ситуация <tex>\dotsc 22\dotsc \rightarrow \dotsc 30\dotsc</tex>.В свою очередь такая ситуация получается из этой <tex>\dotsc 212\dotsc \rightarrow \dotsc 220\dotsc</tex>.Причем количество единиц между двойками может быть любое, что недопустимов итоге это приведет к появлению тройки. Однако если между любой парой двоек всегда будет находится хотя бы один<tex>0</tex>, то такой ситуации не возникнет. Покажем, что если это условие с нулем выполняется, то оночто этот инвариантвыполняется и поддерживается после инкремента, рассмотрев основные случаивозможные ситуации:(в обозначениях левой части предполагается что правая двойка самая младшая из всех до инкремента):# Число двоек не изменяется* ## <mathtex>\dotsc 2\dotsc 0\dotsc 12\dotsc 0 \rightarrow \dotsc 2\dotsc 0\dotsc 20\dotsc 1</mathtex> переходит в .## <mathtex>\dotsc 202\dotsc 01 \rightarrow \dotsc 2010\dotsc 2</mathtex>, при этом в младшем разряде может появиться новая 2-ка и между ней следующей будет хотя бы один ноль.* ## <mathtex>\dotsc 2\dotsc 002\dotsc 1 \rightarrow \dotsc 2\dotsc 0210\dotsc 2</mathtex> переходит в (частный случай предыдущего).# Проподает одна двойка## <mathtex>\dotsc 202\dotsc 0\rightarrow \dotsc 10\dotsc 1</mathtex>, ситуация почти аналогична предыдущей.* ## <mathtex>\dotsc 20202 \rightarrow \dotsc 11</mathtex> переходит в .# Появление новой двойки## <mathtex>\dotsc 2101 \rightarrow \dotsc 2</mathtex>, также гарантируется наличие нуля при появлении (имеется в виду появление единственной двойки в младшем разряде).* Появление двух двоек, если уже есть ровно одна возможно, тогда ## <mathtex>\dotsc 12\dotsc 1\rightarrow \dotsc 20\dotsc 2</mathtex> переходит в .## <mathtex>\dotsc 2\dotsc 0\dotsc 12\dotsc 1 \rightarrow \dotsc 2\dotsc 0\dotsc 20\dotsc 2</mathtex>, ясно что в этом случае между ними также будет хотя бы один ноль(частный случай предыдущего).

Таким образом мы видим, что 0 всегда сохраняется. В таблице можно увидеть как будет изменятья представление при применении данных правил десять раз к нулю (представления чисел от <tex>0 </tex> до 10<tex>9</tex>):

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

# Если <mathtex>d_i=b</mathtex>, исправить <mathtex>d_i</mathtex>.# Если <mathtex>d_i=b-1</mathtex> и самый младший значащий разряд <mathtex>d_j</mathtex>, такой, что <mathtex>j>i</mathtex> и <mathtex>d_j \ne b-1</mathtex>, равен <mathtex>b</mathtex> (т.е. <mathtex>d_j=b</mathtex>), применить операцию исправления к разряду <mathtex>d_j</mathtex>.# Добавить 1 к <mathtex>d_i</mathtex>.# Если <mathtex>d_i=b</mathtex>, исправить <mathtex>d_i</mathtex>.

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

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

== Литература Источники информации ==

 == Смотрите также ==* http://www.cphstl.dk/Paper/Numeral-systems/mfcs-13.pdf