在现代 x86-64 上计算 64 位整数的整数 Log10 的最快方法是什么？

Question

标题；我发现了大量 32 位示例，但没有完整的 64 位示例。使用 this post 作为指南，我想出了以下 Log10 的实现，但我不完全确定翻译是否准确或有效...

编辑： 据推测，this Clang example 在没有最后两条指令的情况下处理 MAX_VALUE 情况，但是，如果删除，我得到的结果是 20 而不是预期的 19.

...
mov rcx, 0FFFFFFFFFFFFFFFFh               ; put the integer to be tested into rcx

lea r10, qword ptr powersOfTen            ; put pointer to powersOfTen array into r10
lea r9, qword ptr maxDigits               ; put pointer to maxDigits array into r9
bsr rax, rcx                              ; put log2 of rcx into rax
cmovz rax, rcx                            ; if rcx is zero, put zero into rax
mov al, byte ptr [(r9 + rax)]             ; index into maxDigits array using rax; put the result into al
cmp rcx, qword ptr [(r10 + (rax * 8))]    ; index into powersOfTen array using (rax * 8); compare rcx with the result
sbb al, 0h                                ; if the previous operation resulted in a carry, subtract 1 from al
add rcx, 1h                               ; add one to rcx
sbb al, 0h                                ; if the previous operation resulted in a carry, subtract 1 from al
...

align 2

maxDigits:
    byte 00h
    byte 00h
    byte 00h
    byte 01h
    byte 01h
    byte 01h
    byte 02h
    byte 02h
    byte 02h
    byte 03h
    byte 03h
    byte 03h
    byte 03h
    byte 04h
    byte 04h
    byte 04h
    byte 05h
    byte 05h
    byte 05h
    byte 06h
    byte 06h
    byte 06h
    byte 06h
    byte 07h
    byte 07h
    byte 07h
    byte 08h
    byte 08h
    byte 08h
    byte 09h
    byte 09h
    byte 09h
    byte 09h
    byte 0Ah
    byte 0Ah
    byte 0Ah
    byte 0Bh
    byte 0Bh
    byte 0Bh
    byte 0Ch
    byte 0Ch
    byte 0Ch
    byte 0Ch
    byte 0Dh
    byte 0Dh
    byte 0Dh
    byte 0Eh
    byte 0Eh
    byte 0Eh
    byte 0Fh
    byte 0Fh
    byte 0Fh
    byte 0Fh
    byte 11h
    byte 11h
    byte 11h
    byte 12h
    byte 12h
    byte 12h
    byte 13h
    byte 13h
    byte 13h
    byte 13h
    byte 14h

align 2

powersOfTen:
    qword 00000000000000001h
    qword 0000000000000000Ah
    qword 00000000000000064h
    qword 000000000000003E8h
    qword 00000000000002710h
    qword 000000000000186A0h
    qword 000000000000F4240h
    qword 00000000000989680h
    qword 00000000005F5E100h
    qword 0000000003B9ACA00h
    qword 000000002540BE400h
    qword 0000000174876E800h
    qword 0000000E8D4A51000h
    qword 0000009184E72A000h
    qword 000005AF3107A4000h
    qword 000038D7EA4C68000h
    qword 0002386F26FC10000h
    qword 0016345785D8A0000h
    qword 00DE0B6B3A7640000h
    qword 08AC7230489E80000h
    qword 0FFFFFFFFFFFFFFFFh

Answer 1

为任意输入计算 log10 的最快方法是 table 基于前导零计数（log2 近似值）的查找，然后根据秒 table记录了落在log2近似值范围内的10次方

这正是您所发现的 over here，所以我认为您可以开始了。如果您了解 32 位版本，那么向 64 位的扩展很简单，只需将所有 table 大小加倍并用正确的值填充它们并更改一些指令以使用 64 位寄存器和 64 位加载.

在现代 x86-64 上计算 64 位整数的整数 Log10 的最快方法是什么？

What is the fastest method of calculating integer Log10 for 64-bit integers on modern x86-64?

math

optimization

assembly

x86-64

masm