使用内联汇编计算数字的位数
Count digits of number using inline assembly
如何使用 Delphi 的内联汇编程序获取数字的位数？
例如：
13452 should return 5
1344 should return 4
9721343 should return 7
等等
我的尝试是这样的：
function CalculateLength(Number : integer) : Integer;
begin
asm
PUSH Length(Number)
MOV @Result, EAX
end;
end;
我的做法：
function count_of_digits (n:Integer) : Cardinal; {No problems for `n:Cardinal`}
var cnt : Cardinal;
begin
cnt := 0;
repeat
inc (cnt);
n := n div 10;
until (n=0);
count_of_digits := cnt;
end;
function count_of_digits_asm_signed (n:Integer) : Cardinal;
begin
asm
push ebx { An asm statement must preserve the EDI, ESI, ESP, EBP, and EBX registers }
xor ecx, ecx
mov ebx, 10 { Base 10 (decimal), just change it for another base }
mov eax, n
@L1:
add ecx, 1
cdq { Set EDX for `idiv` }
idiv ebx { Decimal shift right by one decimal digit }
test eax, eax
jne @L1
mov @result, ecx
pop ebx
end;
end;
function count_of_digits_asm_unsigned (n:Cardinal) : Cardinal;
begin
asm
push ebx { An asm statement must preserve the EDI, ESI, ESP, EBP, and EBX registers }
xor ecx, ecx
mov ebx, 10 { Base 10 (decimal), just change it for another base }
mov eax, n
@L1:
add ecx, 1
xor edx, edx { Set EDX for `div` }
div ebx { Decimal shift right by one decimal digit }
test eax, eax
jne @L1
mov @result, ecx
pop ebx
end;
end;
VAR
i: Integer;
c1, c2, c3: Cardinal;
BEGIN
i := 13452;
c1 := count_of_digits (i);
c2 := count_of_digits_asm_signed (i);
c3 := count_of_digits_asm_unsigned (i);
writeln (i:11, c1:3, c2:3, c3:3);
i := 1344;
c1 := count_of_digits (i);
c2 := count_of_digits_asm_signed (i);
c3 := count_of_digits_asm_unsigned (i);
writeln (i:11, c1:3, c2:3, c3:3);
i := 9721343;
c1 := count_of_digits (i);
c2 := count_of_digits_asm_signed (i);
c3 := count_of_digits_asm_unsigned (i);
writeln (i:11, c1:3, c2:3, c3:3);
i := -13452;
c1 := count_of_digits (i);
c2 := count_of_digits_asm_signed (i);
c3 := count_of_digits_asm_unsigned (i);
writeln (i:11, c1:3, c2:3, c3:3);
END.
这是一个避免除法的更快的算法：
function CountDigits(anInt: Cardinal): Cardinal; inline;
var
cmp: Cardinal;
begin
cmp := 10;
Result := 1;
while (Result < 10) and (cmp <= anInt) do
begin
cmp := cmp*10;
Inc(Result);
end;
end;
function CountDigitsAsm(anInt: Cardinal): Cardinal;
asm
mov ecx,$a // cmp := 10;
mov edx, // Result := 1;
jmp @loop2
cmp eax,edx // while cmp <= anInt do
jb @done
@loop1:
add ecx,ecx // cmp := cmp*10;
lea ecx,[ecx+ecx*4]
inc edx // Inc(Result);
@loop2:
cmp edx,[=10=]a // (Result < 10)
jnb @done
cmp eax,ecx
jnb @loop1
@done:
mov eax,edx
end;
begin
WriteLn(CountDigitsAsm(10));
WriteLn(CountDigitsAsm(99));
WriteLn(CountDigitsAsm(999));
WriteLn(CountDigitsAsm(9999));
WriteLn(CountDigitsAsm(99999));
ReadLn;
end.
请注意，pas 版本可以内联，并且可能比 asm 版本更快。
好的，这是一个避免任何乘法的 lut（查找 table）解决方案：
function CountDigitsLUT(anInt: Cardinal): Cardinal; inline;
const
lut: array[1..10] of cardinal =
(9,
99,
999,
9999,
99999,
999999,
9999999,
99999999,
999999999,
$FFFFFFFF);
begin
Result := 1;
while anInt > lut[Result] do
Inc(Result);
end;
还有展开的版本：
function CountDigitsUnrolled(anInt: Cardinal): Cardinal; inline;
begin
if (anInt < 10) then Result := 1 else
if (anInt < 100) then Result := 2 else
if (anInt < 1000) then Result := 3 else
if (anInt < 10000) then Result := 4 else
if (anInt < 100000) then Result := 5 else
if (anInt < 1000000) then Result := 6 else
if (anInt < 10000000) then Result := 7 else
if (anInt < 100000000) then Result := 8 else
if (anInt < 1000000000) then Result := 9 else
Result := 10;
end;
@TLama 的案例贡献：
function CountDigitsCase(Value: Cardinal): Cardinal; inline;
begin
case Value of
0..9: Result := 1;
10..99: Result := 2;
100..999: Result := 3;
1000..9999: Result := 4;
10000..99999: Result := 5;
100000..999999: Result := 6;
1000000..9999999: Result := 7;
10000000..99999999: Result := 8;
100000000..999999999: Result := 9;
else
Result := 10;
end;
end;
为不同的解决方案计时：
Unrolled: 4097 ms
Case: 1444 ms
LUT: 3233 ms
pas: 6199 ms
asm: 6747 ms
测试代码：
sw := TStopWatch.StartNew;
for i := 1 to 1000000000 do
j := CountDigitsXXX(i);
WriteLn(sw.ElapsedMilliseconds,' ',j);
附录
受this answer启发，
这是一个 Delphi 实现，它是一个 O(1) 解决方案：
function OpenBit(AValue: Cardinal): Cardinal; register;
asm // Highest bit set
BSR EAX, EAX
end;
function CountDigitsO1(value: Cardinal): Cardinal; inline;
const
Powers: array[0..9] of Cardinal = (
0,
10,
100,
1000,
10000,
100000,
1000000,
10000000,
100000000,
1000000000);
MaxDigits: array[0..32] of cardinal =
(1, 1, 1, 2, 2, 2, 3, 3, 3, 4, 4, 4, 4, 5, 5, 5,
6, 6, 6, 7, 7, 7, 7, 8, 8, 8, 9, 9, 9, 10, 10, 10, 10);
begin
Result := MaxDigits[OpenBit(value)];
if (value < Powers[Result-1]) then
Dec(Result);
end;
与 CountDigitsCase() 相比，它在寻找给定数字的解决方案时具有更均匀的时间分布。但总体上还是有点慢（在我的机器上）。
Digit Case O1
------------------
1 0.930 2.200 nanoseconds per call
2 0.922 1.689
3 0.944 1.500
4 1.078 1.578
5 1.878 1.522
6 1.200 1.667
7 1.356 1.567
8 1.356 1.522
9 1.502 1.664
10 1.246 1.761
测试代码：
procedure TestXXX(var Distribution: array of Double);
var
sw: TStopWatch;
i,j,k,m: Cardinal;
const
StartIx: array[0..9] of Cardinal = ( 0,10,100,1000,10000,100000,1000000,
10000000,100000000,100000000);
StopIx: array[0..9] of Cardinal = ( 9,99,999,9999,99999,999999,9999999,
99999999,999999999,$FFFFFFFF);
Repeats: array[0..9] of Cardinal = (10000000,1000000,100000,10000,1000,100,10,1,1,1);
begin
for k := 0 to 9 do begin
sw := TStopWatch.StartNew;
for m := 1 to Repeats[k] do
for i := StartIx[k] to StopIx[k] do
j := CountDigitsXXX(i);
Distribution[k] := sw.ElapsedMilliseconds*1000000.0/(1.0*Repeats[k]*(StopIx[k]- StartIx[k] + 1));
WriteLn(sw.ElapsedMilliSeconds,' ',j);
end;
end;
如何使用 Delphi 的内联汇编程序获取数字的位数？
例如：
13452 should return 5
1344 should return 4
9721343 should return 7
等等
我的尝试是这样的：
function CalculateLength(Number : integer) : Integer;
begin
asm
PUSH Length(Number)
MOV @Result, EAX
end;
end;
我的做法：
function count_of_digits (n:Integer) : Cardinal; {No problems for `n:Cardinal`}
var cnt : Cardinal;
begin
cnt := 0;
repeat
inc (cnt);
n := n div 10;
until (n=0);
count_of_digits := cnt;
end;
function count_of_digits_asm_signed (n:Integer) : Cardinal;
begin
asm
push ebx { An asm statement must preserve the EDI, ESI, ESP, EBP, and EBX registers }
xor ecx, ecx
mov ebx, 10 { Base 10 (decimal), just change it for another base }
mov eax, n
@L1:
add ecx, 1
cdq { Set EDX for `idiv` }
idiv ebx { Decimal shift right by one decimal digit }
test eax, eax
jne @L1
mov @result, ecx
pop ebx
end;
end;
function count_of_digits_asm_unsigned (n:Cardinal) : Cardinal;
begin
asm
push ebx { An asm statement must preserve the EDI, ESI, ESP, EBP, and EBX registers }
xor ecx, ecx
mov ebx, 10 { Base 10 (decimal), just change it for another base }
mov eax, n
@L1:
add ecx, 1
xor edx, edx { Set EDX for `div` }
div ebx { Decimal shift right by one decimal digit }
test eax, eax
jne @L1
mov @result, ecx
pop ebx
end;
end;
VAR
i: Integer;
c1, c2, c3: Cardinal;
BEGIN
i := 13452;
c1 := count_of_digits (i);
c2 := count_of_digits_asm_signed (i);
c3 := count_of_digits_asm_unsigned (i);
writeln (i:11, c1:3, c2:3, c3:3);
i := 1344;
c1 := count_of_digits (i);
c2 := count_of_digits_asm_signed (i);
c3 := count_of_digits_asm_unsigned (i);
writeln (i:11, c1:3, c2:3, c3:3);
i := 9721343;
c1 := count_of_digits (i);
c2 := count_of_digits_asm_signed (i);
c3 := count_of_digits_asm_unsigned (i);
writeln (i:11, c1:3, c2:3, c3:3);
i := -13452;
c1 := count_of_digits (i);
c2 := count_of_digits_asm_signed (i);
c3 := count_of_digits_asm_unsigned (i);
writeln (i:11, c1:3, c2:3, c3:3);
END.
这是一个避免除法的更快的算法：
function CountDigits(anInt: Cardinal): Cardinal; inline;
var
cmp: Cardinal;
begin
cmp := 10;
Result := 1;
while (Result < 10) and (cmp <= anInt) do
begin
cmp := cmp*10;
Inc(Result);
end;
end;
function CountDigitsAsm(anInt: Cardinal): Cardinal;
asm
mov ecx,$a // cmp := 10;
mov edx, // Result := 1;
jmp @loop2
cmp eax,edx // while cmp <= anInt do
jb @done
@loop1:
add ecx,ecx // cmp := cmp*10;
lea ecx,[ecx+ecx*4]
inc edx // Inc(Result);
@loop2:
cmp edx,[=10=]a // (Result < 10)
jnb @done
cmp eax,ecx
jnb @loop1
@done:
mov eax,edx
end;
begin
WriteLn(CountDigitsAsm(10));
WriteLn(CountDigitsAsm(99));
WriteLn(CountDigitsAsm(999));
WriteLn(CountDigitsAsm(9999));
WriteLn(CountDigitsAsm(99999));
ReadLn;
end.
请注意，pas 版本可以内联，并且可能比 asm 版本更快。
好的，这是一个避免任何乘法的 lut（查找 table）解决方案：
function CountDigitsLUT(anInt: Cardinal): Cardinal; inline;
const
lut: array[1..10] of cardinal =
(9,
99,
999,
9999,
99999,
999999,
9999999,
99999999,
999999999,
$FFFFFFFF);
begin
Result := 1;
while anInt > lut[Result] do
Inc(Result);
end;
还有展开的版本：
function CountDigitsUnrolled(anInt: Cardinal): Cardinal; inline;
begin
if (anInt < 10) then Result := 1 else
if (anInt < 100) then Result := 2 else
if (anInt < 1000) then Result := 3 else
if (anInt < 10000) then Result := 4 else
if (anInt < 100000) then Result := 5 else
if (anInt < 1000000) then Result := 6 else
if (anInt < 10000000) then Result := 7 else
if (anInt < 100000000) then Result := 8 else
if (anInt < 1000000000) then Result := 9 else
Result := 10;
end;
@TLama 的案例贡献：
function CountDigitsCase(Value: Cardinal): Cardinal; inline;
begin
case Value of
0..9: Result := 1;
10..99: Result := 2;
100..999: Result := 3;
1000..9999: Result := 4;
10000..99999: Result := 5;
100000..999999: Result := 6;
1000000..9999999: Result := 7;
10000000..99999999: Result := 8;
100000000..999999999: Result := 9;
else
Result := 10;
end;
end;
为不同的解决方案计时：
Unrolled: 4097 ms
Case: 1444 ms
LUT: 3233 ms
pas: 6199 ms
asm: 6747 ms
测试代码：
sw := TStopWatch.StartNew;
for i := 1 to 1000000000 do
j := CountDigitsXXX(i);
WriteLn(sw.ElapsedMilliseconds,' ',j);
附录
受this answer启发， 这是一个 Delphi 实现，它是一个 O(1) 解决方案：
function OpenBit(AValue: Cardinal): Cardinal; register;
asm // Highest bit set
BSR EAX, EAX
end;
function CountDigitsO1(value: Cardinal): Cardinal; inline;
const
Powers: array[0..9] of Cardinal = (
0,
10,
100,
1000,
10000,
100000,
1000000,
10000000,
100000000,
1000000000);
MaxDigits: array[0..32] of cardinal =
(1, 1, 1, 2, 2, 2, 3, 3, 3, 4, 4, 4, 4, 5, 5, 5,
6, 6, 6, 7, 7, 7, 7, 8, 8, 8, 9, 9, 9, 10, 10, 10, 10);
begin
Result := MaxDigits[OpenBit(value)];
if (value < Powers[Result-1]) then
Dec(Result);
end;
与 CountDigitsCase() 相比，它在寻找给定数字的解决方案时具有更均匀的时间分布。但总体上还是有点慢（在我的机器上）。
Digit Case O1
------------------
1 0.930 2.200 nanoseconds per call
2 0.922 1.689
3 0.944 1.500
4 1.078 1.578
5 1.878 1.522
6 1.200 1.667
7 1.356 1.567
8 1.356 1.522
9 1.502 1.664
10 1.246 1.761
测试代码：
procedure TestXXX(var Distribution: array of Double);
var
sw: TStopWatch;
i,j,k,m: Cardinal;
const
StartIx: array[0..9] of Cardinal = ( 0,10,100,1000,10000,100000,1000000,
10000000,100000000,100000000);
StopIx: array[0..9] of Cardinal = ( 9,99,999,9999,99999,999999,9999999,
99999999,999999999,$FFFFFFFF);
Repeats: array[0..9] of Cardinal = (10000000,1000000,100000,10000,1000,100,10,1,1,1);
begin
for k := 0 to 9 do begin
sw := TStopWatch.StartNew;
for m := 1 to Repeats[k] do
for i := StartIx[k] to StopIx[k] do
j := CountDigitsXXX(i);
Distribution[k] := sw.ElapsedMilliseconds*1000000.0/(1.0*Repeats[k]*(StopIx[k]- StartIx[k] + 1));
WriteLn(sw.ElapsedMilliSeconds,' ',j);
end;
end;