Spi*_*ire 82 c assembly bit-manipulation multiplication division
如何仅使用位移和加法进行乘法和除法？
And*_*use 70
要在加法和移位方面相乘,你想要用2的幂来分解其中一个数字,如下所示:
21 * 5 = 10101_2 * 101_2 (Initial step)
= 10101_2 * (1 * 2^2 + 0 * 2^1 + 1 * 2^0)
= 10101_2 * 2^2 + 10101_2 * 2^0
= 10101_2 << 2 + 10101_2 << 0 (Decomposed)
= 10101_2 * 4 + 10101_2 * 1
= 10101_2 * 5
= 21 * 5 (Same as initial expression)
(_2指基地2)
如您所见,乘法可以分解为添加和移位,然后再返回.这也是为什么乘法比位移或添加更长的原因 - 它的位数是O(n ^ 2)而不是O(n).真实计算机系统(与理论计算机系统相反)具有有限数量的比特,因此与加法和移位相比,乘法需要恒定的时间倍数.如果我没记错的话,现代处理器,如果管道正确,可以通过处理处理器中ALU(算术单元)的使用而与添加一样快.
Vik*_*pov 42
Andrew Toulouse的答案可以扩展到分部.
在Henry S. Warren的书"Hacker's Delight"(ISBN 9780201914658)中详细考虑了整数常数的除法.
实现除法的第一个想法是在基数2中写出分母的逆值.
例如,
1/3 = (base-2) 0.0101 0101 0101 0101 0101 0101 0101 0101 .....
所以,
a/3 = (a >> 2) + (a >> 4) + (a >> 6) + ... + (a >> 30)
对于32位算术.
通过以明显的方式组合这些术语,我们可以减少操作次数:
b = (a >> 2) + (a >> 4)
b += (b >> 4)
b += (b >> 8)
b += (b >> 16)
有更多令人兴奋的方法来计算除法和余数.
EDIT1:
如果OP意味着任意数的乘法和除法,而不是除以常数,那么这个线程可能是有用的:https://stackoverflow.com/a/12699549/1182653
EDIT2:
除以整数常数的最快方法之一是利用模块化算术和蒙哥马利减少:将整数除以3的最快方法是什么？
IVl*_*lad 22
x << k == x multiplied by 2 to the power of k
x >> k == x divided by 2 to the power of k
您可以使用这些移位来执行任何乘法运算.例如:
x * 14 == x * 16 - x * 2 == (x << 4) - (x << 1)
x * 12 == x * 8 + x * 4 == (x << 3) + (x << 2)
要将数字除以2的非幂,我不知道任何简单的方法,除非你想要实现一些低级逻辑,使用其他二进制操作并使用某种形式的迭代.
Yan*_*min 17
使用移位和加法的整数除法程序可以直接从小学教的十进制普通除法中推导出来。每个商位的选择被简化，因为该位是 0 和 1：如果当前余数大于或等于除数，则部分商的最低有效位为 1。
就像十进制普通除法一样，被除数的数字从最重要到最不重要，一次一位。这可以通过二进制除法中的左移轻松实现。此外，通过将当前商位左移一个位置，然后附加新的商位来收集商位。
在经典安排中，这两个左移组合成一对寄存器的左移。上半部分持有当前余数，下半部分初始持有股息。当被除数位通过左移传送到余数寄存器时，下半部分未使用的最低有效位用于累加商位。
下面是该算法的 x86 汇编语言和 C 实现。移位和加法除法的这种特殊变体有时被称为“非执行”变体，因为不会执行从当前余数中减去除数的操作，除非余数大于或等于除数 (Otto Spaniol, “计算机算术：逻辑与设计。”奇切斯特：Wiley 1981，第 144 页）。在 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
小智 6
我将Python代码翻译为C.给出的示例有一个小缺陷.如果占据了所有32位的被除数值,则转移将失败.我只是在内部使用64位变量来解决这个问题:
int No_divide(int nDivisor, int nDividend, int *nRemainder)
{
int nQuotient = 0;
int nPos = -1;
unsigned long long ullDivisor = nDivisor;
unsigned long long ullDividend = nDividend;
while (ullDivisor < ullDividend)
{
ullDivisor <<= 1;
nPos ++;
}
ullDivisor >>= 1;
while (nPos > -1)
{
if (ullDividend >= ullDivisor)
{
nQuotient += (1 << nPos);
ullDividend -= ullDivisor;
}
ullDivisor >>= 1;
nPos -= 1;
}
*nRemainder = (int) ullDividend;
return nQuotient;
}