Так как б = log,o 1-е, необходимо выбрать с таким, что

c + (log,(,2-c)logjX<l или c(log, д:-1) > (log.o 2)logj д: -1. Это условие выполняется при х= 1 (так как с< 1) и 2. Для больших значений х требуется

(log.o2)log,x-l

lOgjX-l

Наиболее строгое условие накладывается на с при больших х. На 32-битовом компьютере д: < 2" , так что с должно удовлетворять условию

0.30103.32-13

Так как е>0, с<0.30103, из соображений удобства можно выбрать значение с = 9/32 = 0.28125 . Эксперименты показывают, что значения 5/16 и 1/4 действительно ие подходят для нашего приближения с.

Это приводит нас к схеме, показанной в листинге 11.12, в которвй используется заниженная оценка, корректируемая прибавлением 1. Она требует выполнения примерно 11 RISC-команд, среди которых команда вычисления количества ведущих нулевых битов {умножение считается одной командой).

Листинг 11.12. Целочисленный логарифм по основанию 10 из логарифма по основанию 2, метод поиска в таблице

static unsigned table2[10] = { О, 9, 99, 999, 9999,

99999, 999999, 9999999, 99999999, 999999999

у = (9*(31 - nlz(X))) >> 5;

if (X > table2[y+l]) у = у + 1;

return У;

В этой программе можно избежать условньк переходов, но при этом вновь возникнут сложности при больших значениях д: > 2 +10, справиться с которыми можно различными способами. Один из способов состоит в использовании другого множителя, а именно 19/64, и

несколько измененной таблицы. Соответствующая программа показана в листинге 11.13. Она требует вьтолнения примерно 11 RISC-команд, среди которьк команда вычисления количества ведущих нулевых битов (умножение считается одной командой).

Листинг 11.13. Целочисленный логарифм по основанию 10 из логарифма по основанию 2, метод поиска в таблице, без команд ветвления

int iloglO(unsigned х) {

int у;

static unsigned table2[11] = { 0, 9, 99, 999, 9999,

99999, 999999, 9999999, 99999999, 999999999, OxFFFFFFFF

у = (19* (31 - nlz(x))) >> 6; 212 ГЛАВА 11. НЕКОТОРЫЕ ЭЛЕМЕНТАРНЫЕ ФУНКЦИИ

у = у + ((table2[y+l] - х) >> 31); return У;

Другой способ состоит в использовании команды или схи разностью в качестве операндов для обеспечения установки знакового бита при х>2. Таким образом, при использовании этого способа вторая выполнимая строка в листинге 11.12 должна быть заменена следующей:

у = у + ( ((table2 [у+1] - х) х) >> 31);

Этот способ предпочтительнее, если умножение на 19 оказывается существенно сложнее умножения на 9 (реализуемые в виде последовательностей сдвигов и сложений). На 64-разрадном компьютере следует выбрать с, удовлетворяющее условию

0:0103:,28993. 64-1

Таким значением может быть 19/64 = 0.296875 и, как показывают эксперименты, более

грубого приближения не существует. В результате будет получена следующая программа:

unsigned table2[20] = {О, 9, 99, 999, 9999,

9999999999999999999}; у = ( (19* (63 - nlz(X)) >> 6; у = у + ((table2[у+1] - х) >> 63; return У;

Поскольку мы достигли нулевого частного, процесе на этом завершается (при его продолжении все остальные частные и остатки будут равны 0). Таким образом, считывая значения остатков снизу вверх, получаем, что число -3, записанное в системе счисления с основанием -2, равно 1101.

В табл. 12.1 слева показаны десятичные числа, соответствующие каждой из битовых последовательностей от ООСЮ до 1111 в системе счисления с основанием -2, а справа - представление в этой системе счисления десятичных чисел в диапазоне от -15 до +15.

СИСТЕМЫ СЧИСЛЕНИЯ С НЕОБЫЧНЫМИ ОСНОВАНИЯМИ

в этой главе рассматривается несколько необычных позиционных систем счисления. В основном такие системы представляют собой не более чем интересный курьез, не имеющий практического применения. Наше рассмотрение ограничивается целыми числами, однако его легко распространить и на цифры после точки, что обычно (хотя и не всегда) обозначает нецелые числа.

12.1. Основание -2

Использование системы счисления по основанию -2 дает возможность выражать как положительные, так и отрицательные числа без явного указания их знака или, например, указания отрицательного веса старшего значащего бита [40]. При такой записи используются цифры О и 1, как и в случае системы счисления по основанию 2. Таким образом, значение, представленное строкой из нулей и единиц, трактуется как

(а„...а,аа,а,) = а„(-2)" +... + а,(-2) + а,(-2) + а,(-2) + а, .

Из этого определения видно, что процедура поиска представления числа в системе счисления по основанию -2 должна выполнять последовательное деление на -2, записывая получаемые остатки. Используемое деление должно быть таким, которое всегда дает в остатке О или 1 (используемые в записи чисел цифры), т.е. это модульное деление. В качестве примера покажем, как найти представление числа -3 по основанию -2.