使用位移除以10？
Tho*_*s O 41 math bit low-level integer-division micro-optimization
是否有可能通过使用纯位加法,减法除以10的无符号整数,也许繁衍？使用资源非常有限且速度慢的处理器.
Joh*_*lén 56
以下是Microsoft编译器在使用小积分常量编译除法时所执行的操作.假设一台32位机器(代码可以相应调整):
int32_t div10(int32_t dividend)
{
int64_t invDivisor = 0x1999999A;
return (int32_t) ((invDivisor * dividend) >> 32);
}
这里发生的是我们乘以近似的1/10*2 ^ 32然后移除2 ^ 32.该方法可以适应不同的除数和不同的位宽.
这对ia32架构非常有用,因为它的IMUL指令会将64位产品放入edx:eax中,而edx值将是所需的值.Viz(假设股息在eax中传递,商在eax中返回)
div10 proc
mov edx,1999999Ah ; load 1/10 * 2^32
imul eax ; edx:eax = dividend / 10 * 2 ^32
mov eax,edx ; eax = dividend / 10
ret
endp
即使在具有慢速乘法指令的机器上,这也会比软件鸿沟更快.
- +1,我想强调编译器会在你写"x/10"时自动为你做这个 (12认同)
- 在进行整数除法时,你总是会有数值误差:当你用整数除以28时你得到了什么？答案:2. (3认同)
- 整数除法中没有数值不准确,结果是精确指定的.但是,上述公式仅适用于某些除数.如果你想做无符号算术,即使10是不准确的:`4294967219/10 = 429496721`,但是`4294967219*div >> 32 = 429496722`对于较大的除数,签名版本也是不准确的. (3认同)
rea*_*ime 32
虽然到目前为止给出的答案与实际问题相符,但它们与标题不符.所以这里的解决方案很大程度上受到Hacker's Delight的启发,它实际上只使用了一些位移.
unsigned divu10(unsigned n) {
unsigned q, r;
q = (n >> 1) + (n >> 2);
q = q + (q >> 4);
q = q + (q >> 8);
q = q + (q >> 16);
q = q >> 3;
r = n - (((q << 2) + q) << 1);
return q + (r > 9);
}
我认为这是缺乏多重指令的架构的最佳解决方案.
Alo*_*aus 15
当然,如果你能承受一些精确的损失,你可以.如果你知道输入值的值范围,你可以得到一个位移和一个精确的乘法.一些例子如何划分10,60 ......就像本博客中描述的那样,以最快的方式格式化时间.
temp = (ms * 205) >> 11; // 205/2048 is nearly the same as /10
- 你必须要知道中间值`(ms*205)`可能会溢出. (3认同)
- 如果您做int ms = 205 *（i >> 11）; 如果数字很小，您将得到错误的值。您需要一个测试套件，以确保在给定的值范围内结果正确。 (2认同)
- 这对于ms = 0..1028是准确的 (2认同)
- @ernesto >> 11 是 2048 的除法。当您想除以 10 时，您需要将其除以 2048/10，即 204,8 或 205 作为最接近的整数。 (2认同)
为了稍微扩展阿洛伊斯的答案，我们可以将建议扩展y = (x * 205) >> 11为更多倍数/班次：
y = (ms * 1) >> 3 // first error 8
y = (ms * 2) >> 4 // 8
y = (ms * 4) >> 5 // 8
y = (ms * 7) >> 6 // 19
y = (ms * 13) >> 7 // 69
y = (ms * 26) >> 8 // 69
y = (ms * 52) >> 9 // 69
y = (ms * 103) >> 10 // 179
y = (ms * 205) >> 11 // 1029
y = (ms * 410) >> 12 // 1029
y = (ms * 820) >> 13 // 1029
y = (ms * 1639) >> 14 // 2739
y = (ms * 3277) >> 15 // 16389
y = (ms * 6554) >> 16 // 16389
y = (ms * 13108) >> 17 // 16389
y = (ms * 26215) >> 18 // 43699
y = (ms * 52429) >> 19 // 262149
y = (ms * 104858) >> 20 // 262149
y = (ms * 209716) >> 21 // 262149
y = (ms * 419431) >> 22 // 699059
y = (ms * 838861) >> 23 // 4194309
y = (ms * 1677722) >> 24 // 4194309
y = (ms * 3355444) >> 25 // 4194309
y = (ms * 6710887) >> 26 // 11184819
y = (ms * 13421773) >> 27 // 67108869
每一行都是一个独立的计算，您将在注释中显示的值处看到第一个“错误”/不正确的结果。对于给定的错误值，您通常最好采用最小的移位，因为这将最大限度地减少在计算中存储中间值所需的额外位，例如(x * 13) >> 7“更好”，(x * 52) >> 9因为它需要少两位的开销，而两者都开始在 68 以上给出错误答案。
如果要计算更多这些，可以使用以下（Python）代码：
def mul_from_shift(shift):
mid = 2**shift + 5.
return int(round(mid / 10.))
我做了一个显而易见的事情来计算这个近似值何时开始出错：
def first_err(mul, shift):
i = 1
while True:
y = (i * mul) >> shift
if y != i // 10:
return i
i += 1
（请注意，//用于“整数”除法，即它向零截断/舍入）
错误中“3/1”模式的原因（即 8 次重复 3 次，然后是 9 次）似乎是由于碱基的变化，即log2(10)~3.32。如果我们绘制错误，我们会得到以下信息：
其中相对误差由下式给出： mul_from_shift(shift) / (1<<shift) - 0.1