Изменения

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

==== Описание операции инкремента ==== Оригинальный метод предложен Кнутом и состоит из двух действий: # Найти младший разряд <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>d_{i+1}=1</tex>, то заменить первый элемент списка с <tex>i</tex> на <tex>i+1</tex>, иначе удалить его.# Если <tex>d_1=1</tex>, то добавить в начало списка <tex>1</tex>. ==== Инвариант с нулем ==== Проблемой может оказаться появление двух последовательных двоек, при этом первое правило может породитьтройку. То есть недопустима следующая ситуация:  <tex>(\dotsc 22\dotsc) \overset{Inc} {\longmapsto} (\dotsc 30\dotsc)</tex>.

Проблемой может оказаться появление двух последовательных двоек, при этом перое правило может породитьтройку, что недопустимо. Однако если между любой парой двоек всегда будет находится хотя бы один0, то такой ситуации не возникнет. Покажем, что если это условие с нулем выполняется, то оновыполняется и после инкремента, рассмотрев основные случаи(в обозначениях левой части предполагается что правая двойка самая младшая из всех до инкремента):* <mathtex>(\dotsc 2212\dotsc 0) \dotsc 12overset{Inc} {\dotsc </math> переходит в <math>longmapsto} (\dotsc 2220\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)</mathtex>, ясно что в этом случае между ними также будет хотя бы один ноль.

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

{{Определение|id=b_ary_rr|definition=В общем случае подобные счётчики называются подобное представление называется '''<mathtex>b</mathtex>-ричными избыточными счетчикамиричным избыточным представлением''' (''ИС'ИП''', англ. ''b-ary redundant representation''), которые похожи которое похоже на счетчик представление в счетчике Кнута,но основание системы может быть произвольным, то есть <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>Назовем такое представление ''регулярным'', если между дувумя разрядами равными <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>,нужно сделать следующее:# Если <math>d_i=b</math>, исправить <math>d_i</math>.# Если <math>d_i=b-1</math> и самый младший значащий разряд <math>d_j</math>, такой, что <math>j>i</math> и <math>d_j \ne b-1</math>, равен <math>b</math> (т.е. <math>d_j=b</math>), применить операцию исправления к разряду <math>d_j</math>.# Добавить 1 к <math>d_i</math>.# Если <math>d_i=b</math>, исправить <math>d_i</math>.}

{{Определение|id=regular_rr|definition= Назовем представление '''регулярным''' (англ. ''regular''), если между двумя разрядами равными <tex>b</tex> есть хотя бы один разряд отличный от <tex>b-1</tex>.}} {{Определение|id=fixup|definition= Операция '''исправления''' (англ. ''fix'') разряда <tex>d_i=b</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>d_i=b</tex>, исправить <tex>d_i</tex>.# Если <tex>d_i=b-1</tex> и самый младший значащий разряд <tex>d_j</tex>, такой, что <tex>j>i</tex> и <tex>d_j \ne b-1</tex>, равен <tex>b</tex> (т.е. <tex>d_j=b</tex>), применить операцию исправления к разряду <tex>d_j</tex>.# Добавить <tex>1</tex> к <tex>d_i</tex>.# Если <tex>d_i=b</tex>, исправить <tex>d_i</tex>. Для реализации данной схемы, мы используем односвязный список разрадов разрядов от младшихк старшим. В дополнение каждый разряд <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> на <tex>1, </tex> будем проверять

Такое представление позволяет увеличиать увеличивать произвольный разряд на единицу за константноевремя. Обновление указателя вперед происходит следующим образом: когда <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 In-Place Binary Counter]