在 C++ 中将十六进制转换为整数的最快方法是什么？
What's the fastest way to convert hex to integer in C++?
我正在尝试尽快将十六进制 char 转换为整数。
这只是一行：
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;
}
假设您的函数是为一个有效的十六进制数字调用的，它平均将花费至少 8 次比较操作（可能还有 7 次跳转）。相当昂贵。
一个更紧凑的替代方案：
if (number >= '0' && number<='9')
return number-'0';
else if (number >= 'a' && number <='f')
return number-'a'+0x0a;
else return -1;
另一种选择是使用 查找 table（交易 space 与速度），您只需初始化一次，然后访问直接：
if (number>=0)
return mytable[number];
else return -1;
如果你想一次转换一个以上的数字，你可以看看this question)
编辑：基准测试
在此处 Ike's observations, Ive written a small informal benchmark (available online 之后），您可以 运行 在您最喜欢的编译器上。
结论：
- 查找table总是赢家
- 开关比 if 链更好。
- 对于msvc2015（release），第二好的是我的精简版，紧随其后的是101010的地图版。
- 在ideone上用gcc，第二个是switch版本，紧接着是compact版本。
比 OP 的 if-else 渲染速度更快的建议解决方案：
- 无序地图查找Table
假设您的输入字符串始终是十六进制数字，您可以将查找 table 定义为 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];
}
- 查找 Table 作为用户
constexpr 文字 (C++14)
或者，如果你想要更快的东西而不是 unordered_map，你可以使用新的 C++14 工具和用户文字类型，并在编译时将你的 table 定义为文字类型：
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.org 上的 Nikos Athanasiou 编写的代码作为 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.查找 Table (unordered_map):
long long hextoint(char number) {
return table[(std::size_t)number];
}
其中 table 是之前显示的无序映射。
5.查找 Table（用户 constexpr 文字）：
long long hextoint(char number) {
return table[(std::size_t)number];
}
其中 table 是用户定义的文字，如上所示。
实验设置
我定义了一个函数，t运行将输入的十六进制字符串转换为整数：
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;
}
我还定义了一个函数，用 运行dom 十六进制字符串填充字符串向量：
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 运行dom 十六进制字符串的向量。然后对于每个算法我 运行 100 次实验并对时间结果取平均值。
编译器是 GCC 版本 5.2，带有优化选项 -O3。
结果：
讨论
从结果中我们可以得出结论，对于这些实验设置，所提出的 table 方法优于所有其他方法。 if-else 方法是迄今为止最差的，因为 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 .
结果：
仍然 table 方法渲染速度更快。
这个问题显然在不同的系统上可能会有不同的答案，从这个意义上说，它从一开始就是病态的。例如，i486 没有流水线，奔腾没有 SSE。
The correct question to ask would be: " what is the fastest way to
convert a single char hex to dec in X system , e.g. i686 " .
在本文的方法中，在具有多级流水线的系统上，对此的答案实际上相同或非常非常接近。任何没有管道的系统都会倾向于查找 table 方法 (LUT)，但如果内存访问速度较慢，则条件方法 (CEV) 或按位求值方法 (BEV) 可能会受益，具体取决于异或的速度vs 给定 CPU 的负载。
(CEV) 将寄存器 which is not prone to mis-prediction 中的比较和条件移动分解为 2 个加载有效地址。所有这些命令在奔腾流水线中都是可配对的。所以他们实际上进入了 1 个周期。
8d 57 d0 lea -0x30(%rdi),%edx
83 ff 39 cmp [=10=]x39,%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 [=12=]x57,%edx
83 f0 30 xor [=12=]x30,%eax
83 e7 40 and [=12=]x40,%edi
0f 45 c2 cmovne %edx,%eax
当然，在非常罕见的情况下，它对应用程序至关重要（也许 Mars Pathfinder 是一个候选者）转换 只是一个 signle char。相反，人们会期望通过实际进行循环并调用该函数来转换更大的字符串。
因此，在这种情况下，可更好地向量化的代码是赢家。 LUT 没有向量化，BEV 和 CEV 有更好的表现。 一般来说，这样的微优化不会让你到任何地方，写下你的代码并让它生活（即让编译器 运行）。
所以我实际上已经在这个意义上构建了一些测试，这些测试 可以在任何具有 c++11 编译器和随机设备源的系统上轻松重现，例如任何 *nix系统。如果不允许矢量化 -O2 CEV/LUT 几乎相等，但是一旦设置 -O3 编写更可分解的代码的优势就会显示差异。
To summarised, if you have an old compiler use LUT, if
your system is low-end or old consider BEV, otherwise the compiler
will outsmart you and you should use 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 table 的线性度。
[简单易行]：条件求值->CEV
int decfromhex(int const x)
{
return x<58?x-48:x-87;
}
[又脏又复杂]：按位求值 -> BEV
int decfromhex(int const x)
{
return 9*(x&16)+( x & 0xf );
}
[编译时间]：模板条件求值 -> TCV
template<char n> int decfromhex()
{
int constexpr x = n;
return x<58 ? x-48 : x -87;
}
[查找table]：查找table -> LUT
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];
}
其中，最后一个似乎是最快的初看起来。第二个是只在编译时和常量表达式。
[RESULT] (Please verify): *BEV is the fastest among all and handles lower and upper case letter , but only marginal to CEV which does not handle capital letters. LUT becomes slower than both CEV and BEV as the size of the string increases.
可以在下面找到 str-sizes 16-12384 的示例结果（越低越好）
显示平均时间 (100 运行s )。气泡大小为正常误差。
The script for running the tests is available.
已对 conditional CEV、bitwise BEV 和 lookup table LUT 在一组随机生成的字符串上。测试相当简单，来自：
这些是可验证的：
- 输入字符串的本地副本每次都放在本地缓冲区中。
- 保存结果的本地副本，然后为每个字符串测试将其复制到堆中
- Duration仅针对字符串被提取的时间
- 统一方法，没有复杂的机制和wrap/around适合其他情况的代码。
- 不采样使用整个时序
- CPU执行预热
- 在测试之间休眠 允许编组代码，这样一个测试就不会利用前一个测试。
- 编译用
g++ -std=c++11 -O3 -march=native dectohex.cpp -o d2h 执行
- 启动
taskset -c 0 d2h
- 无线程依赖或多线程
- 实际使用结果，以避免任何类型的循环优化
作为旁注，我在实践中看到版本 3 对于旧的 c++98 编译器要快得多。
[BOTTOM LINE]: use CEV without fear, unless you know your variables at compile time where you could use version TCV. The LUT
should only be used after significant performance per use case
evaluation, and probably with older compilers. Another case is when
your set is larger i.e. {0,1,2,3,4,5,6,7,8,9,a,b,c,d,e,f,A,B,C,D,E,F}
. This can be achieved as well. Finally if you are permormance hungry use BEV .
unordered_map 的结果已被删除，因为它们太慢而无法比较，或者充其量可能与 LUT 解决方案一样快。
我的个人电脑对大小为 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
[如何阅读结果]
平均值显示为计算给定大小的字符串所需的微秒。
给出了每个测试的总时间。平均值计算为计算一个字符串的时间 sum/total（该区域中没有其他代码但可以矢量化，没关系）。误差是时间的标准偏差。
均值告诉我们平均应该期望什么，以及时间遵循正态性的误差。在这种情况下，只有当它很小时，这是一个公平的错误度量（否则我们应该使用适合正分布的东西）。在 缓存未命中 、 处理器调度 和许多其他因素的情况下，通常应该期望出现高错误。
该代码有一个定义为 运行 测试的唯一宏，允许定义编译时变量以设置测试，并打印完整信息，例如：
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
-------------------------------------------------------------------
例如 运行 测试 2sec 在大小为 256 的 str 上暂停，总共 10000 个不同的字符串，输出计时 double precision，并在 nanoseconds 中计算以下命令编译和 运行s 测试。
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
好吧，这是个奇怪的问题。将单个十六进制字符转换为整数是如此之快，以至于很难说哪个更快，因为所有方法几乎都可能比您为使用它们而编写的代码更快 =)
我假设以下情况：
- 我们有现代 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 个时钟。
hextoint_cond 版本有 4 条指令，但 cmov 被分成两个独立的微指令。所以总共有 5 个微指令，每个微指令都可以在三个算术端口 0、1 和 5 中的任何一个上进行处理。所以假设它需要 5/3 个周期时间。请注意，内存加载端口是空闲的，因此即使您必须从内存加载输入值，时间也不会增加。
hextoint_cond2版本有5条指令。但在紧密循环中，常量可以预加载到寄存器中，因此只有比较、cmov 和减法。它们总共是 4 微指令，每个值有 4/3 个周期（即使读取内存）。
hextoint_bit 版本是一种保证没有分支和查找的解决方案，如果您不想总是检查编译器是否生成了 cmov 指令，这将很方便。第一个 mov 是免费的，因为常量可以在紧密循环中预加载。其余的是 5 条算术指令，在端口 0、1、5 中有 5 微指令。因此它应该需要 5/3 个周期（即使读取内存）。
基准
我已经对上述 C++ 函数进行了基准测试。在基准测试中，生成了 64 KB 的随机数据，然后每个函数在该数据上 运行 多次。所有结果都添加到校验和以确保编译器不会删除代码。使用手动 8x 展开。我在 Ivy Bridge 3.4 Ghz 内核上进行了测试，它与 Sandy Bridge 非常相似。每个输出字符串包含：函数名称、基准测试所用的总时间、每个输入值的循环数、所有输出的总和。
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 倍以获得最佳性能（以消除循环开销）。
您可能已经注意到，这两种方法的速度在很大程度上取决于代码周围的操作。例如。添加内存负载会使第一种方法花费的时间加倍，但不会影响其他方法。
P.S. 很可能你真的不需要优化它。
这是我最喜欢的hex-to-int代码：
inline int htoi(int x) {
return 9 * (x >> 6) + (x & 017);
}
它是 case-insensitive 的字母，即 return 正确的 "a" 和 "A" 的结果。
如果您（或其他人）实际上正在转换值数组，我制作了一个 AVX2 SIMD 编码器和解码器，其基准测试速度比最快的标量实现快 12 倍：https://github.com/zbjornson/fast-hex
16 个十六进制值可以方便地（两次）装入 YMM 寄存器，因此您可以使用 PSHUFB 进行并行查找。解码有点困难，并且基于位运算。
我正在尝试尽快将十六进制 char 转换为整数。
这只是一行：
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;
}
假设您的函数是为一个有效的十六进制数字调用的，它平均将花费至少 8 次比较操作（可能还有 7 次跳转）。相当昂贵。
一个更紧凑的替代方案：
if (number >= '0' && number<='9')
return number-'0';
else if (number >= 'a' && number <='f')
return number-'a'+0x0a;
else return -1;
另一种选择是使用 查找 table（交易 space 与速度），您只需初始化一次，然后访问直接：
if (number>=0)
return mytable[number];
else return -1;
如果你想一次转换一个以上的数字，你可以看看this question)
编辑：基准测试
在此处 Ike's observations, Ive written a small informal benchmark (available online 之后），您可以 运行 在您最喜欢的编译器上。
结论：
- 查找table总是赢家
- 开关比 if 链更好。
- 对于msvc2015（release），第二好的是我的精简版，紧随其后的是101010的地图版。
- 在ideone上用gcc，第二个是switch版本，紧接着是compact版本。
比 OP 的 if-else 渲染速度更快的建议解决方案：
- 无序地图查找Table
假设您的输入字符串始终是十六进制数字，您可以将查找 table 定义为 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];
}
- 查找 Table 作为用户
constexpr文字 (C++14)
或者，如果你想要更快的东西而不是 unordered_map，你可以使用新的 C++14 工具和用户文字类型，并在编译时将你的 table 定义为文字类型：
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.org 上的 Nikos Athanasiou 编写的代码作为 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.查找 Table (unordered_map):
long long hextoint(char number) { return table[(std::size_t)number]; }
其中 table 是之前显示的无序映射。
5.查找 Table（用户 constexpr 文字）：
long long hextoint(char number) { return table[(std::size_t)number]; }
其中 table 是用户定义的文字，如上所示。
实验设置
我定义了一个函数，t运行将输入的十六进制字符串转换为整数：
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; }
我还定义了一个函数，用 运行dom 十六进制字符串填充字符串向量：
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 运行dom 十六进制字符串的向量。然后对于每个算法我 运行 100 次实验并对时间结果取平均值。
编译器是 GCC 版本 5.2，带有优化选项 -O3。
结果：
讨论
从结果中我们可以得出结论，对于这些实验设置，所提出的 table 方法优于所有其他方法。 if-else 方法是迄今为止最差的，因为 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 .
结果：
仍然 table 方法渲染速度更快。
这个问题显然在不同的系统上可能会有不同的答案，从这个意义上说，它从一开始就是病态的。例如，i486 没有流水线，奔腾没有 SSE。
The correct question to ask would be: " what is the fastest way to convert a single char hex to dec in X system , e.g. i686 " .
在本文的方法中，在具有多级流水线的系统上，对此的答案实际上相同或非常非常接近。任何没有管道的系统都会倾向于查找 table 方法 (LUT)，但如果内存访问速度较慢，则条件方法 (CEV) 或按位求值方法 (BEV) 可能会受益，具体取决于异或的速度vs 给定 CPU 的负载。
(CEV) 将寄存器 which is not prone to mis-prediction 中的比较和条件移动分解为 2 个加载有效地址。所有这些命令在奔腾流水线中都是可配对的。所以他们实际上进入了 1 个周期。
8d 57 d0 lea -0x30(%rdi),%edx
83 ff 39 cmp [=10=]x39,%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 [=12=]x57,%edx
83 f0 30 xor [=12=]x30,%eax
83 e7 40 and [=12=]x40,%edi
0f 45 c2 cmovne %edx,%eax
当然，在非常罕见的情况下，它对应用程序至关重要（也许 Mars Pathfinder 是一个候选者）转换 只是一个 signle char。相反，人们会期望通过实际进行循环并调用该函数来转换更大的字符串。
因此，在这种情况下，可更好地向量化的代码是赢家。 LUT 没有向量化，BEV 和 CEV 有更好的表现。 一般来说，这样的微优化不会让你到任何地方，写下你的代码并让它生活（即让编译器 运行）。
所以我实际上已经在这个意义上构建了一些测试，这些测试 可以在任何具有 c++11 编译器和随机设备源的系统上轻松重现，例如任何 *nix系统。如果不允许矢量化 -O2 CEV/LUT 几乎相等，但是一旦设置 -O3 编写更可分解的代码的优势就会显示差异。
To summarised, if you have an old compiler use LUT, if your system is low-end or old consider BEV, otherwise the compiler will outsmart you and you should use 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 table 的线性度。
[简单易行]：条件求值->CEV
int decfromhex(int const x)
{
return x<58?x-48:x-87;
}
[又脏又复杂]：按位求值 -> BEV
int decfromhex(int const x)
{
return 9*(x&16)+( x & 0xf );
}
[编译时间]：模板条件求值 -> TCV
template<char n> int decfromhex()
{
int constexpr x = n;
return x<58 ? x-48 : x -87;
}
[查找table]：查找table -> LUT
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];
}
其中，最后一个似乎是最快的初看起来。第二个是只在编译时和常量表达式。
[RESULT] (Please verify): *BEV is the fastest among all and handles lower and upper case letter , but only marginal to CEV which does not handle capital letters. LUT becomes slower than both CEV and BEV as the size of the string increases.
可以在下面找到 str-sizes 16-12384 的示例结果（越低越好）
显示平均时间 (100 运行s )。气泡大小为正常误差。
The script for running the tests is available.
已对 conditional CEV、bitwise BEV 和 lookup table LUT 在一组随机生成的字符串上。测试相当简单，来自：
这些是可验证的：
- 输入字符串的本地副本每次都放在本地缓冲区中。
- 保存结果的本地副本，然后为每个字符串测试将其复制到堆中
- Duration仅针对字符串被提取的时间
- 统一方法，没有复杂的机制和wrap/around适合其他情况的代码。
- 不采样使用整个时序
- CPU执行预热
- 在测试之间休眠 允许编组代码，这样一个测试就不会利用前一个测试。
- 编译用
g++ -std=c++11 -O3 -march=native dectohex.cpp -o d2h执行
- 启动
taskset -c 0 d2h - 无线程依赖或多线程
- 实际使用结果，以避免任何类型的循环优化
作为旁注，我在实践中看到版本 3 对于旧的 c++98 编译器要快得多。
[BOTTOM LINE]: use CEV without fear, unless you know your variables at compile time where you could use version TCV. The LUT should only be used after significant performance per use case evaluation, and probably with older compilers. Another case is when your set is larger i.e. {0,1,2,3,4,5,6,7,8,9,a,b,c,d,e,f,A,B,C,D,E,F} . This can be achieved as well. Finally if you are permormance hungry use BEV .
unordered_map 的结果已被删除，因为它们太慢而无法比较，或者充其量可能与 LUT 解决方案一样快。
我的个人电脑对大小为 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
[如何阅读结果]
平均值显示为计算给定大小的字符串所需的微秒。
给出了每个测试的总时间。平均值计算为计算一个字符串的时间 sum/total（该区域中没有其他代码但可以矢量化，没关系）。误差是时间的标准偏差。
均值告诉我们平均应该期望什么，以及时间遵循正态性的误差。在这种情况下，只有当它很小时，这是一个公平的错误度量（否则我们应该使用适合正分布的东西）。在 缓存未命中 、 处理器调度 和许多其他因素的情况下，通常应该期望出现高错误。
该代码有一个定义为 运行 测试的唯一宏，允许定义编译时变量以设置测试，并打印完整信息，例如：
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
-------------------------------------------------------------------
例如 运行 测试 2sec 在大小为 256 的 str 上暂停，总共 10000 个不同的字符串，输出计时 double precision，并在 nanoseconds 中计算以下命令编译和 运行s 测试。
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
好吧，这是个奇怪的问题。将单个十六进制字符转换为整数是如此之快，以至于很难说哪个更快，因为所有方法几乎都可能比您为使用它们而编写的代码更快 =)
我假设以下情况：
- 我们有现代 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 个时钟。
hextoint_cond 版本有 4 条指令，但 cmov 被分成两个独立的微指令。所以总共有 5 个微指令，每个微指令都可以在三个算术端口 0、1 和 5 中的任何一个上进行处理。所以假设它需要 5/3 个周期时间。请注意，内存加载端口是空闲的，因此即使您必须从内存加载输入值，时间也不会增加。
hextoint_cond2版本有5条指令。但在紧密循环中，常量可以预加载到寄存器中，因此只有比较、cmov 和减法。它们总共是 4 微指令，每个值有 4/3 个周期（即使读取内存）。
hextoint_bit 版本是一种保证没有分支和查找的解决方案，如果您不想总是检查编译器是否生成了 cmov 指令，这将很方便。第一个 mov 是免费的，因为常量可以在紧密循环中预加载。其余的是 5 条算术指令，在端口 0、1、5 中有 5 微指令。因此它应该需要 5/3 个周期（即使读取内存）。
基准
我已经对上述 C++ 函数进行了基准测试。在基准测试中，生成了 64 KB 的随机数据，然后每个函数在该数据上 运行 多次。所有结果都添加到校验和以确保编译器不会删除代码。使用手动 8x 展开。我在 Ivy Bridge 3.4 Ghz 内核上进行了测试，它与 Sandy Bridge 非常相似。每个输出字符串包含：函数名称、基准测试所用的总时间、每个输入值的循环数、所有输出的总和。
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 倍以获得最佳性能（以消除循环开销）。 您可能已经注意到，这两种方法的速度在很大程度上取决于代码周围的操作。例如。添加内存负载会使第一种方法花费的时间加倍，但不会影响其他方法。
P.S. 很可能你真的不需要优化它。
这是我最喜欢的hex-to-int代码：
inline int htoi(int x) {
return 9 * (x >> 6) + (x & 017);
}
它是 case-insensitive 的字母，即 return 正确的 "a" 和 "A" 的结果。
如果您（或其他人）实际上正在转换值数组，我制作了一个 AVX2 SIMD 编码器和解码器，其基准测试速度比最快的标量实现快 12 倍：https://github.com/zbjornson/fast-hex
16 个十六进制值可以方便地（两次）装入 YMM 寄存器，因此您可以使用 PSHUFB 进行并行查找。解码有点困难，并且基于位运算。