在C中将十六进制转换为整数的最快方法是什么？
我正在尝试尽快将十六进制char转换为整数。
这只有一行:< code > int x = atoi(hex . c _ str)；
有没有更快的方法？
在这里，我尝试了一种更动态的方法，它稍微快一点。
int hextoint(char number) {
if (number == '0') {
return 0;
}
if (number == '1') {
return 1;
}
if (number == '2') {
return 2;
}
/*
* 3 through 8
*/
if (number == '9') {
return 9;
}
if (number == 'a') {
return 10;
}
if (number == 'b') {
return 11;
}
if (number == 'c') {
return 12;
}
if (number == 'd') {
return 13;
}
if (number == 'e') {
return 14;
}
if (number == 'f') {
return 15;
}
return -1;
}
共有3个答案
这个问题很奇怪。将一个十六进制字符转换成一个整数是如此之快，以至于很难判断哪个更快，因为所有的方法几乎都可能比你为了使用它们而编写的代码更快=)
我将假设以下事项：
- 我们有一个现代化的x86（64）CPU。
- 输入字符的 ASCII 代码存储在通用寄存器中，例如在
eax中。 - 输出整数必须在通用寄存器中获取。
- 输入字符保证是有效的十六进制数字（16 种情况之一）。
现在这里有几种解决问题的方法：第一种基于查找，两种基于三元运算符，最后一种基于位运算：
int hextoint_lut(char x) {
static char lut[256] = {???};
return lut[uint8_t(x)];
}
int hextoint_cond(char x) {
uint32_t dig = x - '0';
uint32_t alp = dig + ('0' - 'a' + 10);
return dig <= 9U ? dig : alp;
}
int hextoint_cond2(char x) {
uint32_t offset = (uint8_t(x) <= uint8_t('9') ? '0' : 'a' - 10);
return uint8_t(x) - offset;
}
int hextoint_bit(char x) {
int b = uint8_t(x);
int mask = (('9' - b) >> 31);
int offset = '0' + (mask & int('a' - '0' - 10));
return b - offset;
}
下面是生成的相应程序集列表(只显示了相关的部分):
;hextoint_lut;
movsx eax, BYTE PTR [rax+rcx] ; just load the byte =)
;hextoint_cond;
sub edx, 48 ; subtract '0'
cmp edx, 9 ; compare to '9'
lea eax, DWORD PTR [rdx-39] ; add ('0' - 'a' + 10)
cmovbe eax, edx ; choose between two cases in branchless way
;hextoint_cond2; ; (modified slightly)
mov eax, 48
mov edx, 87 ; set two offsets to registers
cmp ecx, 57 ; compare with '9'
cmovbe edx, eax ; choose one offset
sub ecx, edx ; subtract the offset
;hextoint_bit;
mov ecx, 57 ; load '9'
sub ecx, eax ; get '9' - x
sar ecx, 31 ; convert to mask if negative
and ecx, 39 ; set to 39 (for x > '9')
sub eax, ecx ; subtract 39 or 0
sub eax, 48 ; subtract '0'
我将尝试估计每种方法在吞吐量意义上所花费的周期数，吞吐量本质上是当一次处理大量数字时每一个输入数字所花费的时间。以Sandy Bridge架构为例。
hextoint_lut函数由单个内存负载组成，它在端口2或3上占用1个uop。这两个端口都专用于内存负载，它们内部也有地址计算，能够执行rax rcx而不需要额外的成本。有两个这样的端口，每个端口可以在一个周期内执行一个uop。所以据说这个版本需要0.5个时钟时间。如果我们必须从内存中加载输入号，那么每个值需要多一个内存负载，所以总成本是1个时钟。
< code>hextoint_cond版本有4条指令，但< code>cmov分成两个独立的微指令。因此总共有5个微操作，每个微操作都可以在三个算术端口0、1和5中的任何一个上处理。所以大概需要5/3个周期的时间。请注意，内存加载端口是空闲的，因此即使您必须从内存中加载输入值，时间也不会增加。
< code>hextoint_cond2版本有5条指令。但是在一个紧循环中，常量可以预加载到寄存器中，所以只有比较、cmov和减法。它们总共有4个UOP，每个值有4/3个周期(即使有内存读取)。
hextoint_bit版本是一个保证没有分支和查找的解决方案，如果您不想始终检查编译器是否生成了cmov指令，这将非常方便。第一个mov是免费的，因为常量可以在紧密循环中预加载。其余的是5个算术指令，端口0，1，5中有5个uops。因此，它应该需要5/3个周期（即使有内存读取）。
我已经为上述C函数执行了一个基准测试。在基准测试中，生成了64KB的随机数据，然后每个函数在这些数据上运行多次。所有结果都将添加到校验和中，以确保编译器不会删除代码。使用手动8x展开。我在常春藤桥3.4 Ghz内核上进行了测试，它与桑迪桥非常相似。每个输出字符串包含：函数名、基准测试花费的总时间、每个输入值的周期数、所有输出的总和。
基准代码
MSVC2013 x64 /O2:
hextoint_lut: 0.741 sec, 1.2 cycles (check: -1022918656)
hextoint_cond: 1.925 sec, 3.0 cycles (check: -1022918656)
hextoint_cond2: 1.660 sec, 2.6 cycles (check: -1022918656)
hextoint_bit: 1.400 sec, 2.2 cycles (check: -1022918656)
GCC 4.8.3 x64 -O3 -fno-tree-vectorize
hextoint_lut: 0.702 sec, 1.1 cycles (check: -1114112000)
hextoint_cond: 1.513 sec, 2.4 cycles (check: -1114112000)
hextoint_cond2: 2.543 sec, 4.0 cycles (check: -1114112000)
hextoint_bit: 1.544 sec, 2.4 cycles (check: -1114112000)
GCC 4.8.3 x64 -O3
hextoint_lut: 0.702 sec, 1.1 cycles (check: -1114112000)
hextoint_cond: 0.717 sec, 1.1 cycles (check: -1114112000)
hextoint_cond2: 0.468 sec, 0.7 cycles (check: -1114112000)
hextoint_bit: 0.577 sec, 0.9 cycles (check: -1114112000)
显然，LUT方法每个值需要一个周期（正如预测的那样）。其他方法通常每个值需要2.2到2.6个周期。在GCC的情况下，hextoint_cond2很慢，因为编译器使用cmp sbb和Magic而不是所需的cmov指令。还要注意，默认情况下，GCC向量化了大多数方法（最后一段），这比不可向量化的LUT方法提供了预期更快的结果。请注意，手动向量化会提供更大的提升。
注意hextoint_cond用普通条件跳转代替cmov会有一个分支。假设随机输入十六进制数字，它几乎总是被错误预测。所以我认为性能会很糟糕。
我已经分析了吞吐量性能。但是如果我们必须处理大量的输入值，那么我们肯定应该向量化转换以获得更好的速度。hextoint_cond可以用SSE以非常简单的方式向量化。它只使用4条指令就可以处理16个字节到16个字节，我想大约需要2个周期。
请注意，为了查看任何性能差异，必须确保所有输入值都适合缓存（L1 是最佳情况）。如果您从主内存中读取输入数据，即使 std：：atoi 在考虑的方法中也同样快 =）
此外，您还应该展开主循环 4 倍甚至 8 倍，以获得最佳性能（以消除环路开销）。您可能已经注意到，这两种方法的速度在很大程度上取决于代码周围的操作。例如，添加内存负载会使第一种方法所花费的时间加倍，但不会影响其他方法。
附言：很可能你真的不需要优化它。
显然，这个问题在不同的系统上可能有不同的答案，从这个意义上说，它从一开始就是不适定的。例如，i486没有流水线，奔腾没有SSE。
要问的正确问题是：“在X系统中将单个char hex转换为dec的最快方法是什么，例如i686”。
在这里的方法中，在具有多级流水线的系统上，这个问题的答案实际上是相同的或者非常非常接近相同的。任何没有流水线的系统都将倾向于查找表方法(LUT)，但是如果内存访问很慢，则条件方法(CEV)或逐位评估方法(BEV)可能会受益，这取决于给定CPU的xor与load的速度。
（CEV）将比较地址和不易预测错误的寄存器条件移动地址分解为2个有效负载地址。所有这些命令都可以在pentium管道中使用。所以它们实际上是一个循环。
8d 57 d0 lea -0x30(%rdi),%edx
83 ff 39 cmp $0x39,%edi
8d 47 a9 lea -0x57(%rdi),%eax
0f 4e c2 cmovle %edx,%eax
(LUT)分解为寄存器之间的mov和来自数据相关存储位置的mov，加上一些用于对齐的nop，并且应该至少占用1个周期。如前所述，只有数据依赖。
48 63 ff movslq %edi,%rdi
8b 04 bd 00 1d 40 00 mov 0x401d00(,%rdi,4),%eax
（BEV）是一个不同的野兽，因为它实际上需要2个movs 2个xors 1和一个条件mov。这些也可以很好地流水线化。
89 fa mov %edi,%edx
89 f8 mov %edi,%eax
83 f2 57 xor $0x57,%edx
83 f0 30 xor $0x30,%eax
83 e7 40 and $0x40,%edi
0f 45 c2 cmovne %edx,%eax
当然，很少有情况下只转换单个字符是应用程序关键的（可能Mars Pathfinder是一个候选者）。相反，人们希望通过实际生成循环并调用该函数来转换更大的字符串。
因此，在这种情况下，可更好地矢量化的代码是赢家。LUT 不会进行矢量化，并且 BEV 和 CEV 具有更好的行为。一般来说，这种微优化不会让你在任何地方，编写你的代码并让生活（即让编译器运行）。
因此，我实际上构建了一些这样的测试，它们可以在任何带有c 11编译器和随机设备源的系统上轻松重现，比如任何*nix系统。如果不允许向量化，那么< code>-O2 CEV/LUT几乎相等，但是一旦设置了< code>-O3，编写更具可分解性的代码的优势就会显示出差异。
总而言之，如果你有一个旧的编译器使用LUT，如果你的系统是低端或旧的，请考虑BEV，否则编译器会比你聪明，你应该使用CEV。
问题：有问题的是从字符集 {0，1，2，3，4，5，6，7，8，9，a，b，c，d，e，f} 转换为 {0，1，2，3，4，5，6，7，8，9，10，11，12，13，14，15} 的集合。没有正在考虑大写字母。
这个想法是利用ascii表分段的线性。
【简单易行】：条件评估——
int decfromhex(int const x)
{
return x<58?x-48:x-87;
}
[肮脏而复杂]：按位评估-
int decfromhex(int const x)
{
return 9*(x&16)+( x & 0xf );
}
[编译时间]：模板条件求值-
template<char n> int decfromhex()
{
int constexpr x = n;
return x<58 ? x-48 : x -87;
}
[查阅表格]： 查阅表格 -
int decfromhex(char n)
{
static int constexpr x[255]={
// fill everything with invalid, e.g. -1 except places\
// 48-57 and 97-102 where you place 0..15
};
return x[n];
}
其中，最后一种乍一看似乎是最快的。第二种仅在编译时和常量表达式中。
[结果](请验证):*BEV是所有中速度最快的，可以处理小写和大写字母，但仅次于不处理大写字母的CEV。随着字符串大小的增加，LUT变得比CEV和BEV都慢。
str大小为16-12384的示例性结果可以在下面找到(越低越好)
显示平均时间(100次运行)。气泡的大小是正常误差。
运行测试的html" target="_blank">脚本是可用的。
已经在一组随机生成的字符串上对< code >条件 CEV、< code >按位 BEV和< code >查找表 LUT进行了测试。测试相当简单，来自:
测试源代码
这些是可验证的：
-
< li >输入字符串的本地副本每次都放在本地缓冲区中。 < li >保留结果的本地副本，然后针对每个字符串测试将其复制到堆中 < li >仅提取字符串操作时间的持续时间 < li >统一方法，没有适用于其他情况的复杂机制和环绕代码。 < li >不采样，使用整个时序 < li >执行CPU预热 < li >在测试之间进行Hibernate，以允许封送代码，这样一个测试就不会利用前一个测试。 < li >使用< code > g-STD = c 11-O3-March = native dectohex . CPP-o d2h 执行编译 < li >使用< code>taskset -c 0 d2h启动 < li >没有线程依赖性或多线程 < li >实际上正在使用结果，以避免任何类型的循环优化
作为补充说明，我在实践中看到，对于较旧的c98编译器，版本3要快得多。
[底线]:使用CEV没有恐惧，除非你知道你的变量在编译时，你可以使用TCV版本。只有在对每个用例进行了显著的性能评估后，才应该使用LUT，并且可能是在旧编译器上使用。另一种情况是当你的集合较大时即{0，1，2，3，4，5，6，7，8，9，A，B，C，D，E，F，A，B，C，D，E，F}。这也是可以实现的。最后，如果你渴望表现，使用BEV。
unordered_map的结果已经被删除，因为它们太慢了，无法进行比较，或者最好的情况可能与LUT解决方案一样快。
我个人PC上大小为12384/256的字符串和100个字符串的结果：
g++ -DS=2 -DSTR_SIZE=256 -DSET_SIZE=100 -DUNITS=nanoseconds -O3 -std=c++11 -march=native dectohex.cpp -o d2h && taskset -c 0 ./d2h
sign: -2709
-------------------------------------------------------------------
(CEV) Total: 185568 nanoseconds - mean: 323.98 nanoseconds error: 88.2699 nanoseconds
(BEV) Total: 185568 nanoseconds - mean: 337.68 nanoseconds error: 113.784 nanoseconds
(LUT) Total: 229612 nanoseconds - mean: 667.89 nanoseconds error: 441.824 nanoseconds
-------------------------------------------------------------------
g++ -DS=2 -DSTR_SIZE=12384 -DSET_SIZE=100 -DUNITS=nanoseconds -O3 -std=c++11 -march=native hextodec.cpp -o d2h && taskset -c 0 ./h2d
-------------------------------------------------------------------
(CEV) Total: 5539902 nanoseconds - mean: 6229.1 nanoseconds error: 1052.45 nanoseconds
(BEV) Total: 5539902 nanoseconds - mean: 5911.64 nanoseconds error: 1547.27 nanoseconds
(LUT) Total: 6346209 nanoseconds - mean: 14384.6 nanoseconds error: 1795.71 nanoseconds
-------------------------------------------------------------------
Precision: 1 ns
GCC 4.9.3编译成金属的系统的结果，该系统没有加载在256/12384大小的弦上，并且对于100个弦
g++ -DS=2 -DSTR_SIZE=256 -DSET_SIZE=100 -DUNITS=nanoseconds -O3 -std=c++++11 -march=native dectohex.cpp -o d2h && taskset -c 0 ./d2h
sign: -2882
-------------------------------------------------------------------
(CEV) Total: 237449 nanoseconds - mean: 444.17 nanoseconds error: 117.337 nanoseconds
(BEV) Total: 237449 nanoseconds - mean: 413.59 nanoseconds error: 109.973 nanoseconds
(LUT) Total: 262469 nanoseconds - mean: 731.61 nanoseconds error: 11.7507 nanoseconds
-------------------------------------------------------------------
Precision: 1 ns
g++ -DS=2 -DSTR_SIZE=12384 -DSET_SIZE=100 -DUNITS=nanoseconds -O3 -std=c++11 -march=native dectohex.cpp -o d2h && taskset -c 0 ./d2h
sign: -137532
-------------------------------------------------------------------
(CEV) Total: 6834796 nanoseconds - mean: 9138.93 nanoseconds error: 144.134 nanoseconds
(BEV) Total: 6834796 nanoseconds - mean: 8588.37 nanoseconds error: 4479.47 nanoseconds
(LUT) Total: 8395700 nanoseconds - mean: 24171.1 nanoseconds error: 1600.46 nanoseconds
-------------------------------------------------------------------
Precision: 1 ns
[如何阅读结果]
平均值显示为计算给定大小的字符串所需的微秒。
给出了每个测试的总时间。平均值计算为计算一个字符串的时间总和/总时间（该区域中没有其他代码，但可以矢量化，没关系）。误差是时间的均方差。
均值告诉我们平均而言我们应该期待什么，以及时间跟随正态的误差。在这种情况下，只有当误差很小时，它才是一个公平的误差度量（否则我们应该使用适合正分布的东西）。在缓存未命中，处理器调度和许多其他因素的情况下，通常应该预料到高错误。
该代码定义了一个用于运行测试的唯一宏，允许定义编译时变量以设置测试，并打印完整的信息，例如：
g++ -DS=2 -DSTR_SIZE=64 -DSET_SIZE=1000 -DUNITS=nanoseconds -O3 -std=c++11 -march=native dectohex.cpp -o d2h && taskset -c 0 ./d2h
sign: -6935
-------------------------------------------------------------------
(CEV) Total: 947378 nanoseconds - mean: 300.871 nanoseconds error: 442.644 nanoseconds
(BEV) Total: 947378 nanoseconds - mean: 277.866 nanoseconds error: 43.7235 nanoseconds
(LUT) Total: 1040307 nanoseconds - mean: 375.877 nanoseconds error: 14.5706 nanoseconds
-------------------------------------------------------------------
例如，要在大小为256的str上以2sec暂停运行测试，总共10000不同的字符串，输出时序以双精度为单位，计数以纳秒为单位，以下命令编译并运行测试。
g++ -DS=2 -DSTR_SIZE=256 -DSET_SIZE=10000 -DUTYPE=double -DUNITS=nanoseconds -O3 -std=c++11 -march=native dectohex.cpp -o d2h && taskset -c 0 ./d2h
- 无序地图查找表
假设您的输入字符串总是十六进制数字，您可以将查找表定义为< code>unordered_map:
std::unordered_map<char, int> table {
{'0', 0}, {'1', 1}, {'2', 2},
{'3', 3}, {'4', 4}, {'5', 5},
{'6', 6}, {'7', 7}, {'8', 8},
{'9', 9}, {'a', 10}, {'A', 10},
{'b', 11}, {'B', 11}, {'c', 12},
{'C', 12}, {'d', 13}, {'D', 13},
{'e', 14}, {'E', 14}, {'f', 15},
{'F', 15}, {'x', 0}, {'X', 0}};
int hextoint(char number) {
return table[(std::size_t)number];
}
-
< li >作为用户< code>constexpr文字的查找表(C 14)
或者，如果您想要更快的速度，而不是使用unordered_map，则可以将新的C 14工具与用户文本类型一起使用，并在编译时将表定义为文本类型：
struct Table {
long long tab[128];
constexpr Table() : tab {} {
tab['1'] = 1;
tab['2'] = 2;
tab['3'] = 3;
tab['4'] = 4;
tab['5'] = 5;
tab['6'] = 6;
tab['7'] = 7;
tab['8'] = 8;
tab['9'] = 9;
tab['a'] = 10;
tab['A'] = 10;
tab['b'] = 11;
tab['B'] = 11;
tab['c'] = 12;
tab['C'] = 12;
tab['d'] = 13;
tab['D'] = 13;
tab['e'] = 14;
tab['E'] = 14;
tab['f'] = 15;
tab['F'] = 15;
}
constexpr long long operator[](char const idx) const { return tab[(std::size_t) idx]; }
} constexpr table;
constexpr int hextoint(char number) {
return table[(std::size_t)number];
}
现场演示
我用最近发布在isocpp上的Nikos Athanasiou编写的代码运行基准测试。org作为C微观基准测试的建议方法。
比较的算法是：
1. OP的原始if-else：
long long hextoint3(char number) {
if(number == '0') return 0;
if(number == '1') return 1;
if(number == '2') return 2;
if(number == '3') return 3;
if(number == '4') return 4;
if(number == '5') return 5;
if(number == '6') return 6;
if(number == '7') return 7;
if(number == '8') return 8;
if(number == '9') return 9;
if(number == 'a' || number == 'A') return 10;
if(number == 'b' || number == 'B') return 11;
if(number == 'c' || number == 'C') return 12;
if(number == 'd' || number == 'D') return 13;
if(number == 'e' || number == 'E') return 14;
if(number == 'f' || number == 'F') return 15;
return 0;
}
2.紧凑if-else，由Christophe提出:
long long hextoint(char number) {
if (number >= '0' && number <= '9') return number - '0';
else if (number >= 'a' && number <= 'f') return number - 'a' + 0x0a;
else if (number >= 'A' && number <= 'F') return number - 'A' + 0X0a;
else return 0;
}
3.修正了g24l提出的三进制运算符版本，也处理大写字母输入:
long long hextoint(char in) {
int const x = in;
return (x <= 57)? x - 48 : (x <= 70)? (x - 65) + 0x0a : (x - 97) + 0x0a;
}
4. 查找表 （unordered_map）：
long long hextoint(char number) {
return table[(std::size_t)number];
}
其中< code>table是前面显示的无序映射。
5. 查找表（用户同义词文字）：
long long hextoint(char number) {
return table[(std::size_t)number];
}
其中 table 是用户定义的文字，如上所示。
实验设置
我定义了一个将输入十六进制字符串转换为整数的函数：
long long hexstrtoint(std::string const &str, long long(*f)(char)) {
long long ret = 0;
for(int j(1), i(str.size() - 1); i >= 0; --i, j *= 16) {
ret += (j * f(str[i]));
}
return ret;
}
我还定义了一个用随机十六进制字符串填充字符串向量的函数:
std::vector<std::string>
populate_vec(int const N) {
random_device rd;
mt19937 eng{ rd() };
uniform_int_distribution<long long> distr(0, std::numeric_limits<long long>::max() - 1);
std::vector<std::string> out(N);
for(int i(0); i < N; ++i) {
out[i] = int_to_hex(distr(eng));
}
return out;
}
我创建了分别填充50000、100000、150000、200000和250000个随机十六进制字符串的向量。然后对于每个算法，我运行100个实验并平均时间结果。
编译器是带有优化选项-O3的GCC 5.2版。
结果：
讨论
从结果中我们可以得出结论，对于这些实验设置，所提出的表格方法优于所有其他方法。if-else方法是迄今为止最差的方法，其中< code>unordered_map虽然胜于if-else方法，但它明显比其他建议的方法慢。
代码
stgatilov提出的按位运算方法的结果：
long long hextoint(char x) {
int b = uint8_t(x);
int maskLetter = (('9' - b) >> 31);
int maskSmall = (('Z' - b) >> 31);
int offset = '0' + (maskLetter & int('A' - '0' - 10)) + (maskSmall & int('a' - 'A'));
return b - offset;
}
编辑：
我还针对table方法测试了g24l的原始代码：
long long hextoint(char in) {
long long const x = in;
return x < 58? x - 48 : x - 87;
}
请注意，此方法不处理大写字母 A、B、C、D、E 和 F。
结果：
表格方法仍然渲染得更快。
-
我有十六进制字符串，例如“0x103E”，我想将其转换为整数。意思是to我尝试了但它给出了数字格式异常。我如何实现这一点？
-
问题内容： 我正在尝试将一个数字从一个整数转换为另一个整数，如果以十六进制打印，它将看起来与原始整数相同。 例如： 将20转换为32（即0x20） 将54转换为84（即0x54） 问题答案： 即，将原始数字视为十六进制，然后将其转换为十进制。
-
本文向大家介绍C++实现十六进制字符串转换为十进制整数的方法，包括了C++实现十六进制字符串转换为十进制整数的方法的使用技巧和注意事项，需要的朋友参考一下 本文实例讲述了C++实现十六进制字符串转换为十进制整数的方法。分享给大家供大家参考。具体实现方法如下： 希望本文所述对大家的C++程序设计有所帮助。
-
问题内容： 我写了一些代码将十六进制显示字符串转换为十进制整数。但是，当输入类似100a或625b（带有字母的东西）时，我得到了这样的错误： java.lang.NumberFormatException：对于输入字符串：java.lang.Integer.parseInt（未知源）处的java.lang.NumberFormatException.forInputString（未知源）处为“ 1
-
我正在写一个Rust程序，读取I2C总线并保存数据。当我读取I2C总线时，我会得到十六进制值，比如，，等等。 现在，我只能将其作为字符串处理并按原样保存。有没有办法把它解析成一个整数？它有内置的功能吗？
-
问题内容： 如上面的标题。我想从一个十六进制数字 我想转换为。 问题答案：