в предыдущем разделе было показано, что если п кратао d, то

H«d(mod2").

Следовательно, ,iJ = 0,l,2,...,[(2"-l)/t/j(mod 2*) для n = 0,d,2d.....[{2-l)/d\d . Таким

образом, для п, не являющегося кратным d, значение nd , приведенное по модулю 2* к диапазону от О до 2"" -1, должно превышать величину (2*-l)/t/ .

Этот вывод можно использовать для проверки на равенство нулю остатка от деления. Например, чтобы проверить, что число п кратно 25, умножим и на 25 и сравним правые W бит со значением (2"-l)/25 . Использование базового набора RISC-команд дает следующий код:

li M,0xC28F5C29 Загружаем мультипликативное обратное 25

mul q,M,n q = правая половина М*п

li c,0x0A3D70A3 с = floor((2**32-1)/25)

cmpleu t,q,c Сравниваем q и c; переход,

bt t,is mult если n кратно 25

Для того чтобы распространить этот метод на четные делители, представим делитель в следующем виде: rf = do 2*, где do нечетно, а > 1. Тогда, поскольку целое число делится на d тогда и только тогда, когда оно делится на do и 2*, и поскольку пи nd„ имеют одинаковое количество завершающих нулевых битов (d нечетко), проверка того, что п кратно d, состоит в следующем:

q = mod(,J„,2");

q< (2* - l)/rfo и q завершается не менее чем к нулевыми битами,

где под функцией "mod" подразумевается приведение ndg к интервалу 0,2"" -1 .

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

лее теоремы, в которой запись а»к означает компьютерное слово а, циклически сдвинутое вправо на к бит (О < fc < 32).

Теорема ZRU. х<(( их заканчивается к нулевыми битами тогда и только то-гда, когда х:»к<\а/2 .

Доказательство. (Будем считать, что имеем дело с 32-разрядным компьютером.)

Предположим, что х<а их заканчивается к нулевыми битами. Тогда, так как х<а , то */2 < fl/2 . Однако je/2 =*»fc и, таким образом, *s>fc< fl/2 J. Еслих не закан-

чивается к нулевыми битами, то *s>fc не начинается с к нулевых битов, в то время как fl/2 начинается с них, так что *»fc> fl/2 . И наконец, если х>а и д: заканчивается к

нулевыми битами, то целое число, образованное первыми 32-fc битами д: должно превышать число, образованное первыми 32 - fc битами а, так что je/2* >в/2* .

При использовании этой теоремы проверка того, что п кратао d, где nnd - ненулевые беззнаковые целые числа, причем d = d„-2, где do - нечетно, выполняется следующим образом:

«?<-mod(«t/o,2"); qkkUl-l)/d

Здесь мы воспользовались тем, что

{2--l)/d,\/r\ = [{2-l)/(d,.r)\ = l{2-l)/d

Далее в качестве примера приведен код, проверяющий, является ли беззнаковое целое число п кратным 100.

11 M,0xC28F5C29 Мультипликативное обратное 25

mul q,M,n q = правая половина М*п

shrri q,q,2 Циклический сдвиг вправо на два бита

11 c,x028F5C28 с = floor((2**32-1)/100)

cmpleu t,q,c Сравнение q и с, и переход, если

bt t,is mult n кратно 100

Знаковое деление, делитель >2

в случае знакового деления, как бьшо показано в предыдущем разделе, если п кратно dad нечетно, то

J«J(mod2").

-2-ld\4,...-d,0,d,-[{2-l)/d

имеем:

Таким образом, для п = nd= -2""/=],...-1,0,1,-- {i"-\)jd (mod г"). Кроме того, поскольку d взаимно простое с 2, то если п принимает 2 различных значений по модулю 2, тогда nd также принимает 2 различных значений по модулю 2*. Следовательно, п кратно d тогда и только тогда, когда

-2"-Id]< mod(«J,2")< (2"- -\)ld\ ,

где под функцией "mod" подразумевается приведение к интервалу -2"",2""-1 .

Этот способ можно немного упростить, заметив, что, так как d нечетно, а из наших начальных предположений оно положительно и не равно единице, d не является делителем 2"". Таким образом,

"-2-Vt/]="(-2"- + l)/t/] = -[(2«--l)/rf .

Для знаковых чисел проверка того, что п является кратным d, где г/ = • 2*, а d нечетно, вьшолняется следующим образом:

qi = mod(nJo,2");

- (г""<qi< (2"-l)/t/o и g завершается не менее чем fc нулевыми битами. 10.16. ПРОВЕРКА НУЛЕВОГО ОСТАТКА ПРИ ДЕЛЕНИИ НА КОНСТАНТУ 195

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

Теорема ZRS. Если я йО, /ио следующие утверждения эквивалентны:

1) -а<х<а их заканчивается к или большим количеством нулевых битов,

rot и ,

2) abs(jc)s.it<[e/2*

3) x+a»k<\ЪL2

где а представляет собой а с установленными в О правыми к битами (т.е. а = а8с-2Ч

Доказательство. (Будем считать, что имеем дело с 32-разрядным компьютером.) Чтобы убедиться, что утверждение 1 эквивалентно утверждению 2, достаточно заметить, что выражения -a<je<e и abs(x)Se эквивалентны. После этого эквивалентность утверждений 1 и 2 следует из теоремы ZRU.

Чтобы убедиться в эквивалентности утверждений 1 и 3, заметим, что утверждение 1 справедливо и при замене а на а. Тогда, в соответствии с теоремой границ из раздела 4.1, оно, в свою очередь, эквивалентно

х+в2а.

Поскольку х+а заканчивается к нулевыми битами тогда и только тогда, когда к нулевыми битами заканчивается д:, можно применить теорему ZRU, которая и дает требующийся нам результат.

Используя утверждение 3 рассмотренной теоремы, проверку кратности п числу d, где nvid - знаковые целые числа, не меньшие 2, и rf = • 2*, где do нечетно, можно провести следующим образом:

(Поскольку d - константа, а можно вычислить во время компиляции.)

Далее в качестве примера приведен код, проверяющий, является ли знаковое целое число п кратным 100. Обратите внимание, что константа 2а/2* J в любой момент может

быть получена из константы а путем сдвига на it -1 позиций, что позволяет сохранить одну команду либо загрузку из памяти для получения операнда сравнения.

li M,0xC28F5C29

mul q,M,n

li c,0x051EB850

add q,q,c

shrri q,q,2

shri c,c,l

cmpleu t,q,c

bt t,is mult

Загрузка мультипликативного обратного 25 q = правая половина M*n с = floor((2**31 - 1)/25) & -4 Прибавляем с

Циклический сдвиг вправо на 2 позиции Вычисление константы для сравнения Сравнение q и с, и переход, если п кратно 100