Изменения

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

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

==== Описание операции инкремента ==== Оригинальный метод предложен Кнутом и состоит из двух действий: # Найти младший разряд <tex>d_i</tex> равный <tex>2</tex> и, если таковой имеется, заменить последовательность <tex>(\dotsc d_{i+1}d_i\dotsc)</tex> на <tex>(\dotsc (d_{i+1}+1)0\dotsc)</tex>

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

==== Инвариант с нулем ==== Проблемой может оказаться появление двух последовательных двоек, при этом перое первое правило может породитьтройку. То есть недопустима следующая ситуация :  <tex>(\dotsc 22\dotsc ) \rightarrow overset{Inc} {\longmapsto} (\dotsc 30\dotsc)</tex>. В свою очередь такая ситуация получается из этой : <tex>(\dotsc 212\dotsc ) \rightarrow overset{Inc} {\longmapsto} (\dotsc 220\dotsc)</tex>. 

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

# : Число двоек не изменяется## :: <tex>(\dotsc 2\dotsc 0\dotsc 12\dotsc 0 ) \rightarrow overset{Inc} {\longmapsto} (\dotsc 2\dotsc 0\dotsc 20\dotsc 1)</tex>.## :: <tex>(\dotsc 02\dotsc 1 ) \overset{Inc} {\rightarrow longmapsto} (\dotsc 10\dotsc 2)</tex>.## :: <tex>(\dotsc 2\dotsc 02\dotsc 1 ) \rightarrow overset{Inc} {\longmapsto} (\dotsc 2\dotsc 10\dotsc 2)</tex> (частный случай предыдущего).# :: <tex>(\dotsc 12) \overset{Inc} {\longmapsto} (\dotsc 21)</tex>.: Пропадает одна двойка## :: <tex> (\dotsc 02\dotsc 0 ) \rightarrow overset{Inc} {\longmapsto} (\dotsc 10\dotsc 1)</tex>.## :: <tex> (\dotsc 02 ) \overset{Inc} {\rightarrow longmapsto} (\dotsc 11)</tex>.# : Появление новой двойки## :: <tex>(\dotsc 1 ) \rightarrow overset{Inc} {\longmapsto} (\dotsc 2)</tex> (имеется в виду появление единственной двойки).## :: <tex>(\dotsc 12\dotsc 1 ) \overset{Inc} {\rightarrow longmapsto} (\dotsc 20\dotsc 2)</tex>.## :: <tex>(\dotsc 2\dotsc 0\dotsc 12\dotsc 1 ) \rightarrow overset{Inc} {\longmapsto} (\dotsc 2\dotsc 0\dotsc 20\dotsc 2)</tex> (частный случай предыдущего). Таким образом мы видим, что <tex>0</tex> всегда сохраняется.

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

# Добавить <tex>1 </tex> к <tex>d_i</tex>.

Для реализации данной схемы, мы используем односвязный список разрядов от младших

Теперь, во время увеличения разряда <tex>d_i</tex> на <tex>1, </tex> будем проверять

Такое представление позволяет увеличиать увеличивать произвольный разряд на единицу за константное

* [http://www.cphstl.dk/Paper/Numeral-systems/mfcs-13.pdf* [[Амортизационный анализ]]* [[Представление целых чисел: прямой код, код со сдвигом, дополнительный код]]* [[Список]In-Place Binary Counter]