41.7 ДЕЛЕНИЕ НА КОНСТАНТУ




THIS SECTION IS UNDER CONSTRUCTION


Деление на степень 2: X / 2^N = (X >>> N) для знаковых и беззнаковых


Деление через умножение:





идея: X / Y = X * 1/Y Reciprocal = 1/Y ---------------------------------------------- Y 1/Y (decimal) 1/Y (binary) ---------------------------------------------- 1 1.0 1.0 2 0.5 0.1 3 0.(3) 0.(01) 4 0.25 0.01 5 0.2 0.(0011) 6 0.1(6) 0.0(01) 7 0.0142857(142857) 0.(001) 8 0.125 0.001 9 0.(1) 0.(000111) 10 0.1 0.0(0011) ----------------------------------------------- ----------------------------------------------- 1/3 0.(0101) 1/5 0.(0011) 4/6 0.(1010) 4/7 0.(1001 0010 0100) 8/9 0.(1110 0011 1000) 8/10 0.(1100) 8/11 0.(1011 1010 0010 1110 1000) 8/12 0.(1010) 8/13 0.(1001 1101 1000) 1/2 0.1 1/4 0.01 1/8 0.001 ----------------------------------------------- Чтобы 1/Y уместилась в регистр мы умножаем ее на 2^N используем умножение N*N в 2N и берем старшую часть.


Пример: 45h / 10 размер операции байт 1/10 = 0.0(0011) в размере байта: 0.00011001 1/10 * 2^8 ~= 00011001 = 19h +-----------+ | 0100 0101 | 45h * +-----------+ | 0001 1001 | 19h ============================== | 0000 0110 | 1101 1011 | 6DBh +-----------+-----------+ +-----------+ | +------> наш результат: 6h все правильно


Пример: 45h / 3 размер операции байт. 45h = 69 = &b01000101 1/3 = 0.(01) в размере байта: 0.01010101 1/3 * 2^8 ~= 01010101 = 55h +-----------+ | 0100 0101 | 45h * +-----------+ | 0101 0101 | 55h ============================== | 0001 0110 | 1110 1001 | 16E9h +-----------+-----------+ +-----------+ | +------> наш результат: 16h проверка: 16h * 3 = 42h (потому что не уложились) вообще 3,5,7 - специальные случаи почему они специальные случаи: возьмем части которые у нас не уместились в байт: 3 X * 0.(5) = 0.(5) X как минимум чтобы это скоректировать мы можем добавить к X 2 (при Х близких к FF неудобно). +-----------+ | 0100 0111 | 47h * +-----------+ | 0101 0101 | 55h ============================== | 0001 0111 | 1001 0011 | 1793h +-----------+-----------+ +-----------+ | +------> наш результат: 17h 17h * 3 = 45h все нормально другой вариант: 2^8 + 2 X Q = floor( -------- * --- ) 3 2^8 (2^8 + 2) / 3 = 56h +-----------+ | 0100 0111 | 45h * +-----------+ | 0101 0101 | 56h ============================== | 0001 0111 | 0010 1110 | 172Eh +-----------+-----------+ +-----------+ | +------> наш результат: 17h


5 X * 0.3(3) 2^9 + 3 X Q = floor ( --------- * --- ) 5 2^9


7 X * 0.92.. 2^10 + 5 X Q = floor ( ( floor(( --------- - 2^8)*---) + X) / 4 ) 7 2^8


Вычисление остатка

действует для чисел вида k * 2^t a % b = a % (k * 2^t) = a - ((2^N / k * a / 2^N) & -2^t) * k

Index Prev Next