网上没有有效的代码可以抄
只好自己废脑细胞
这算法没啥难点, 就是复杂而已, 符号实现很麻烦
算法是在lua上的, 但是其他需要的地方也可以借鉴
算法是为了:
一个32位有符号数乘另一个32位有符号数减去一个32位有符号数
结果再除于一个32位有符号数
最终输出一个有符号的64位数和32位有符号的模
没有溢出或者精度丢失问题
--- for (a*b+c)/d, input signed 32bit, return signed 64bit quotient and signed 32bit remainder as [low32, high32, remainder]
--- following lua remainder rule
function muldiv (a, b, c, d)
assert(d~=0, "muldiv() divided by 0")
--- a*b
local t0, t1, t2, t3 = bit.rshift(a,16), bit.band(0xffff, a), bit.rshift(b,16), bit.band(0xffff, b)
t0, t1, t2, t3 = t1*t3, t1*t2, t0*t3, t0*t2
t0, t1 = bit.band(0xffff, t0), bit.rshift(t0,16)+t1+bit.band(0xffff, t2)
t0, t3 = t0 + bit.lshift(t1, 16), t3+bit.rshift(t1,16)+bit.rshift(t2,16)
if (a<0) then t3 = t3-b end
if (b<0) then t3 = t3-a end
--- +c
if (c>0) then
if (t0<0) then
t0 = t0+c
if (t0>=0) then t3=t3+1 end
else
t0 = t0+c
end
else
if (t0>=0) then
t0 = t0+c
if (t0<0) then t3=t3-1 end
else
t0 = t0+c
end
end
--- /d
local s1, s2 = false, false
if (d<0) then
d = -d
s1 = true
end
if (t3<0) then
t0 = -t0
t3 = -t3 - 1
s2 = true
end
t2=0
for t1=1,32 do
t2 = bit.lshift(t2, 1) + bit.rshift(t3, 31)
t3 = bit.lshift(t3, 1)
if (t2>=d or t2<0) then
t2 = t2 - d
t3 = t3 + 1
end
end
for t1=1,32 do
t2 = bit.lshift(t2, 1) + bit.rshift(t0, 31)
t0 = bit.lshift(t0, 1)
if (t2>=d or t2<0) then
t2 = t2 - d
t0 = t0 + 1
end
end
if (s1) then
if (s2) then
t2 = -t2
else
t0 = -t0
t3 = -t3 - 1
if (t2~=0) then
t2 = t2 - d
if (t0==0) then
t3 = t3 -1
end
t0 = t0 - 1
end
end
elseif (s2) then
t0 = -t0
t3 = -t3 - 1
if (t2~=0) then
t2 = d - t2
if (t0==0) then
t3 = t3 -1
end
t0 = t0 - 1
end
end
return t0, t3, t2
end