Процедура деления целых чисел, в которой используются сдвиги и сложения, может быть получена прямым способом из десятичного деления на длинные, как преподаются в начальной школе. Выбор каждой факторной цифры упрощается, так как эта цифра равна 0 и 1: если текущий остаток больше или равен делителю, младший значащий бит частичного частного равен 1.
Как и в случае десятичного деления на длинные, цифры дивиденда считаются от самых значительных до наименее значимых, по одной цифре за раз. Это легко сделать с помощью левого сдвига в двоичном делении. Кроме того, частичные биты собираются путем сдвига влево текущих частичных битов на одну позицию, а затем добавления нового частного бита.
В классическом расположении эти два сдвига влево объединяются в сдвиг влево одной пары регистров. Верхняя половина содержит текущий остаток, нижняя половина - дивиденд. Поскольку дивидендные биты передаются в регистр остатка с помощью сдвига влево, неиспользуемые младшие значащие биты младшей половины используются для накопления частных битов.
Ниже представлен язык ассемблера x86 и реализации C этого алгоритма. Этот конкретный вариант деления сдвига и сложения иногда называют вариантом «бездействия», поскольку вычитание делителя из текущего остатка не выполняется, если остаток не больше или равен делителю. В Си нет понятия флага переноса, используемого версией сборки в сдвиге пары регистров слева. Вместо этого он эмулируется, основываясь на наблюдении, что результат сложения по модулю 2 n может быть меньше, что либо добавляется, только если был результат.
#include <stdio.h>
#include <stdlib.h>
#include <stdint.h>
#define USE_ASM 0
#if USE_ASM
uint32_t bitwise_division (uint32_t dividend, uint32_t divisor)
{
uint32_t quot;
__asm {
mov eax, [dividend];// quot = dividend
mov ecx, [divisor]; // divisor
mov edx, 32; // bits_left
mov ebx, 0; // rem
$div_loop:
add eax, eax; // (rem:quot) << 1
adc ebx, ebx; // ...
cmp ebx, ecx; // rem >= divisor ?
jb $quot_bit_is_0; // if (rem < divisor)
$quot_bit_is_1: //
sub ebx, ecx; // rem = rem - divisor
add eax, 1; // quot++
$quot_bit_is_0:
dec edx; // bits_left--
jnz $div_loop; // while (bits_left)
mov [quot], eax; // quot
}
return quot;
}
#else
uint32_t bitwise_division (uint32_t dividend, uint32_t divisor)
{
uint32_t quot, rem, t;
int bits_left = CHAR_BIT * sizeof (uint32_t);
quot = dividend;
rem = 0;
do {
// (rem:quot) << 1
t = quot;
quot = quot + quot;
rem = rem + rem + (quot < t);
if (rem >= divisor) {
rem = rem - divisor;
quot = quot + 1;
}
bits_left--;
} while (bits_left);
return quot;
}
#endif