提问人:Vas 提问时间:6/1/2023 最后编辑:Peter CordesVas 更新时间:6/1/2023 访问量:150
将 UInt64 十六进制字符串转换为 UInt32 值的最快方法,保留尽可能多的前导数字,即截断
The fastest way to convert a UInt64 hex string to a UInt32 value preserving as many leading digits as possible, i.e. truncation
问:
我正在寻找将表示 ulong 的十六进制字符串解析为 uint 的最快方法,保留 uint 可以处理的尽可能多的前导数字并丢弃其余数字。例如
string hex = “0xab54a9a1df8a0edb”;12345678991234567899 应该输出:uint result = 1234567899;
我可以通过简单地将十六进制解析为 ulong 来做到这一点,使用 ToString 获取数字,然后尽可能多地放入 uint 而不会溢出,但我需要更快的东西。谢谢。首选 C# 代码,但任何代码都可以。
答:
对于十进制截断,十六进制数字的所有高位都会影响低 9 或 10 位十进制数字,因此您需要转换整个内容。有没有一种算法可以快速将大量十六进制字符串转换为字节流? asm/C/C++ 具有具有 SSE 内部函数的 C++。我在那里发表了一些可能的改进,并 https://github.com/zbjornson/fast-hex.如果您使用 SIMD 在较大的缓冲区中查找数字文字,这可能特别好,因此您可能已经在 SIMD 寄存器中拥有十六进制字符串。(不确定 SIMDJSON 是否这样做。
十六进制字符串到 64 位整数是 SIMD 当然可以加速的,例如,做一些事情将每个数字映射到 0-15 个整数,组合成对的字节以打包半字节(例如使用 x86),然后将这些 8 位块洗牌到寄存器的底部。(例如 或 )。x86 至少具有有效的 SIMD 到 GP 整数,尽管在某些 ARM CPU 上 ARM 等效项很慢。pmaddubsw
packuswb
pshufb
movq rax, xmm0
(如果您的字符串是固定长度的,并且可能不需要检查不是十六进制数字的无效字符,那么从 SIMD 获得 ASCII 十六进制 -> uint 的加速要容易得多。
(C#) 的十进制截断以适应 (C#u64
ulong
u32
uint
)
10 次幂的取模截断为一定数量的十进制数字。
(uint)(x % 10000000000)
works for some numbers, but 10000000000 (1e10 = one followed by 10 zeros) is larger than 2^32-1. Consider an input like (). We'd get producing (keeping the low 32 bits of that 34-bit number.)0x2540be3ff
9999999999
(uint)9999999999
1410065407 = 0x540be3ff
So perhaps try modulo 1e10, but if it's too big for u32 then modulo 1e9.
ulong tendigit = x % 10000000000; // 1e10
uint truncated = tendigit <= (ulong)0xffffffff ? tendigit : (x % 1000000000); // % 1e9 keeps 9 decimal digits
If this isn't correct C# syntax or the literals need some decoration to make them (like C for good measure), please let me know.ulong
10000000000uLL
It's probably at least as efficient to just modulo the original number two different ways than to try to get the leading decimal digit of and subtract it or whatever. The asm is going to need two 64-bit multiplicative inverse constants, and starting from the original number again keeps critical-path latency shorter for out-of-order exec if branch prediction predicts that it needs to calculate the nine-digit truncation.x % 1e10
Binary truncation
@Matthew Whited deleted his answer (due to a bug in the decimal truncation part), but his binary truncation part based on substrings of the original hex input could perhaps be more efficient in some cases than doing the full conversion and then casting to a narrower type or masking with AND.
If you want the last 8 bytes of the hex string
uint.Parse(hex[^8..],NumberStyles.HexNumber)
If you want the first 8 bytes
uint.Parse(hex[2..10], NumberStyles.HexNumber);
评论
ulong
ulong
x & 0xFFFFFFFFuLL
(uint32_t)x
pext
movq rax, xmm0
pext rax, rax, rdx
0xab54a9a1df8a0edb
0xdf8a0edb
3750366939
u64 % 10000000000