3.2. Округление к ближайшей степени 2

Определим функции flp2(jc) и clp2(jc), которые округляют число х к ближайшей целой степени 2, следующим образом:

х<0,

Пр2{х) = \ О, х = 0, clp2(i:) =

не определена, х<0, О, х = 0,

2"К х>0;

не определена, х < О,

О, х = а

2°""\ х>0.

Значение функции flp2(x) представляет собой наибольшую целую степень 2, не превосходящую значение х, а функции с1р2(х) - наименьшую целую степень 2, не меньшую, чем X. Эти определения имеют смысл и для нецелых х (например, flp2(0.1) = 0,0625). Эти функции удовлетворяют ряду отношений, аналогичных отношениям между функциями floor(x)sLxJ и ceil(x) 2 [х], в частности приведенным ниже.

[xJ = ("х] , только если х - целое Яр2(х) = с1р2(х), только если х - степень 2 или О

lx + nj = [x} + n flp2(2"x) = 2"flp2(x)

rxl = -L-xJ clp2(x) = l/flp2(l/x), xO

При вычислениях используются только целые беззнаковые жачения х, так что обе функции определены для любых возможных значений х. Кроме того, используется требование, чтобы вычисленное значение представляло собой значение по модулю 2 (таким образом, с1р2(х) = О прих>2). Далее представлены значения функций для некоторых значенийх.

функции flp2(x) и с1р2(х) связаны между собой определенными соотношениями, которые позволяют вычислить значения одной функции из значений другой (с учетом указанных ограничений).

flp2(x)=i

1<х<2",

с1р2(х) =

2flp2 flp2(2x-

х-1 1

с1р2 с1р2(,

х+2 + 1

х*0, х<2".

функции округления в большую и меньшую сторону можно достаточно легко вычислить с помощью функции, вычисляющей количество ведущих нулевых битов, как показано ниже. Однако, чтобы эти формулы можно было использовать для х=0 и х>2, команды сдвига на вашем компьютере должны давать О при сдвиге на величины -1, 32 и 63. На многих машинах (например, PowerPC) есть команда "сдвига по модулю 64", которая работает именно так. Отрицательный сдвиг эквивалентен сдвигу в противоположном направлении (т.е. сдвиг влево на-1 - это просто сдвиг вправо на 1).

flp2(x) = l<e(31-nlz(x)) = = l<e(nlz(x)®3l) =

= 0x80000000»nlz(x)

clp2(x) = l<e(32-nlz(i:-l)) =

= 0x800000003>(nlz(x -1) -1)

Округление в меньшую сторону

В листинге 3.1 приведен алгоритм без ветвления, который полезен в случае отсутствия функции, вычисляющей количество ведущих нулевых битов. Алгоритм основан на распространении вправо крайнего слева единичного бита и требует для реализации выполнения 12 команд.

Листинг 3.1. Наибольшая степень 2, ие превосходящая значение х

unsigned f1р2(unsigned х) {

в листинге 3.2 показаны два простых цикла, вычисляющих одну и ту же функцию. Все переменные в приведенных фрагментах представляют собой беззнаковые целые числа. Цикл справа обнуляет крайний справа единичный бит переменной х до тех пор, пока она не становится равной О, после чего возвращается предыдущее значение х.

Листинг 3.2. Округление х в меньшую сторону

у = 0x80000000; do {

While (у > X) у = х;

у = у » 1; X = X & (Х - 1) ;

return У; } while(X != 0);

return у;

При вычислении левого фрагмента требуется 4п1г(лг)+3 команды; цикл справа при хО требует выполнения 4рор(ж) команд, если сравнение с О имеет нулевую стоимость.

Функция pop(jc) возвращает количество единичных битов в х . 3.2. ОКРУГЛЕНИЕ К БЛИЖАЙШЕЙ СТЕПЕНИ 2 59

Округление в большую сторону

Использование распространения старшего бита вправо дает хороший алгоритм для округления к ближайшей большей степени 2. Представленный в листинге 3.3 алгоритм не имеет команд ветвления и вьшолняется за 12 команд.

Листинг 3.3. Наименьшая степень 2, не уступающая значению х

unsigned с1р2(unsigned х) {

X = X - 1;

X = X

X = X

X = X

X = X

X = X

return X + 1;

(X » 1)

(X » 2)

(X » 4)

(X >> 8)

(X » 16) ;

Попытка провести вычисление с использованием цикла работает не так хорошо, как хотелось бы. У = 1;

while (у < х) Беззнаковое сравнение

У = 2*у; return у;

Для х=0 данный алгоритм дает 1, что не совсем то, что требуется; а при х>2 происходит зацикливание. Вычисления требуют выполнения 4и+3 команд, где п - степень 2 возвращаемого кодом числа. Таким образом, этот алгоритм будет работать медленнее алгоритма без ветвления уже при и>3 (т.е. придг>8),

3.3. Проверка пересечения границы степени 2

Предположим, что вся память разделена на блоки, причем размер каждого блока представляет собой степень 2. Нумерация адресов начинается с 0. Блоки могут быть словами, двойными словами, страницами и т.д. Пусть дан некоторый начальный адрес а и длина /. Требуется определить, пересекает ли диапазон адресов от а до а+Z -1, />2, границы блока или нет (величины а и / - целые беззнаковые, полностью размещаемые в регистрах).

Если ;=0 или 1, то, независимо от значения а, пересечения границ блока не будет. Если / превышает размер блока, то, каким бы ни было значение а, произойдет выход за границы блока. Для очень больших значений / (с возможным циклическим возвратом) выход за границы блока может произойти, даже если первый и последний байты диапазона адресов расположены в одном блоке.

Для ЮМ System/370 определить, произойдет ли выход за границы блока, оказывается на удивление просто [7]. Вот как этот метод работает для размера блока, равного 4096 байт (стандартный размер страницы).

о RA-, =А(-40Э6)

ALR RA,RL ВО CROSSES

В первой команде над регистром RA (в котором содержится начальный адрес а) и числом OxFFFFFOOO выполняется команда побитового или. Вторая команда добавляет к