12
правок
Изменения
Пунктуация
</tex>
}}
Заметим, что в этой системе представление числе неоднозначно, например представление <tex>212</tex> эквивалентно <tex>1100</tex>.
== Счетчик Кнута ==
==== Описание операции инкремента ====
Оригинальный метод предложен Кнутом, и состоит из двух правилдействий:
# Найти младший разряд <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_1</tex> на <tex>d_1+1</tex>.
Чтобы достичь необходимой оценки и не выполнять каждый раз поиск для первого правила, можно хранить односвязный [[Список|список]] позиций двоек в числе. Тогда , чтобы найти младший разряд равный двум , нужно просто взять первый элемент списка. Также, непосредственно перед изменением значений разрядов в правилах , необходимо выполнять следующееследующие дополнительные действия:
# Если <tex>d_{i+1}=1</tex>, то заменить первый элемент списка с <tex>i</tex> на <tex>i+1</tex>, иначе удалить его.
# Если <tex>d_i=b</tex>, исправить <tex>d_i</tex>.
Для реализации данной схемы, мы используем односвязный список разрядов от младших
к старшим. В дополнение каждый разряд <tex>d_i</tex> равный <tex>b-1</tex>
будет иметь указатель на самый младший разряд <tex>d_j</tex>, такой,
