Расскажите, пожалуйста, в подробностях, как работает этот алгоритм, а также почему. Искал в yandex'е и google, но либо ничего нет, либо не наглядно как-то.
Пусть множимое равно –41=1111111111010111b. Если переписать это число в виде сумм и разностей целых, содержащих только единицы, получим следующее двоичное представление числа –41= 1111111111111111 - 111111 + 11111 - 1111 + 111 Так как 11111b= 2^5—1, то можем записать -41= 10000000000000000 - 1 - 1000000 + 1 + 100000 - 1 - 10000 + 1 + 1000 - 1= 10000000000000000 - 1000000 + 100000 - 10000 + 1000 - 1 Так как у нас 16-разрядное число — пренебрегаем 17-битным значением 2^16, тогда –41= 1111111111010111b= –2^6+2^5–2^4+2^3–2^0. Теперь произведение –41*m можно представить как: –2^6*m+2^5*m –2^4*m +2^3*m – 2^0*m. Произведение числа на 2^n эквивалентно сдвигу числа на n разрядов влево. При использовании алгоритма Бута операции сложения и вычитания требуются только когда во множимом не совпадают значения в соседних разрядах, то есть, имеется переход от 0 к 1 или от 1 к 0.
