首页   技术笔记   网址导航   Json在线解析   二维码   Ip地址查询   在线流程图  
新用户注册 | 会员登录
当前位置:  开发笔记 > 编程语言 > 正文

在C++中将十六进制转换为整数的最快方法是什么？

作者：135369一生真爱_890 | 2023-09-09 17:57
如何解决《在C++中将十六进制转换为整数的最快方法是什么？》经验，为你挑选了2个好方法。

我正在尝试尽快将十六进制转换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;
}

101010.. 16

提议的解决方案比OP的if-else更快:

无序地图查找表

如果输入字符串始终是十六进制数,则可以将查找表定义为unordered_map:

std::unordered_map 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];
}

查找表作为用户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.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. Christophe提出的紧凑if-else:

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];
}

table先前显示的无序地图在哪里.

5.查找表(用户constexpr文字):

long long hextoint(char number) {
  return table[(std::size_t)number];
}

表是用户定义的文字,如上所示.

实验设置

我定义了一个将输入十六进制字符串转换为整数的函数:

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
populate_vec(int const N) {
  random_device rd;
  mt19937 eng{ rd() };
  uniform_int_distribution distr(0, std::numeric_limits::max() - 1);
  std::vector out(N);
  for(int i(0); i < N; ++i) {
    out[i] = int_to_hex(distr(eng));
  }
  return out;
}

我创建了分别填充50000,100000,150000,200000和250000随机十六进制字符串的向量.然后,对于每个算法,我运行100个实验并平均时间结果.

编译器是带有优化选项的GCC 5.2版-O3.

结果:

在此输入图像描述

在此输入图像描述

在此输入图像描述

在此输入图像描述

在此输入图像描述

在此输入图像描述

讨论

从结果我们可以得出结论,对于这些实验设置,建议的表方法优于所有其他方法.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.

结果:

在此输入图像描述

表格方法仍然更快.



1> 101010..：

提议的解决方案比OP的if-else更快:

无序地图查找表

如果输入字符串始终是十六进制数,则可以将查找表定义为unordered_map:

std::unordered_map 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];
}

查找表作为用户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.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. Christophe提出的紧凑if-else:

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];
}

table先前显示的无序地图在哪里.

5.查找表(用户constexpr文字):

long long hextoint(char number) {
  return table[(std::size_t)number];
}

表是用户定义的文字,如上所示.

实验设置

我定义了一个将输入十六进制字符串转换为整数的函数:

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
populate_vec(int const N) {
  random_device rd;
  mt19937 eng{ rd() };
  uniform_int_distribution distr(0, std::numeric_limits::max() - 1);
  std::vector out(N);
  for(int i(0); i < N; ++i) {
    out[i] = int_to_hex(distr(eng));
  }
  return out;
}

我创建了分别填充50000,100000,150000,200000和250000随机十六进制字符串的向量.然后,对于每个算法,我运行100个实验并平均时间结果.

编译器是带有优化选项的GCC 5.2版-O3.

结果:

在此输入图像描述

在此输入图像描述

在此输入图像描述

在此输入图像描述

在此输入图像描述

在此输入图像描述

讨论

从结果我们可以得出结论,对于这些实验设置,建议的表方法优于所有其他方法.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.

结果:

在此输入图像描述

表格方法仍然更快.



2> g24l..：

对于不同的系统,这个问题显然可能有不同的答案,从这个意义上讲,它从一开始就是不适合的.例如,i486没有管道,奔腾没有SSE.

要问的正确问题是:" 在X系统中将单个字符十六进制转换为dec 的最快方法是什么,例如i686 ".

在这里的方法中,对于具有多级流水线的系统,其答案实际上是相同或非常非常非常相同.任何没有管道的系统都会向查找表方法(LUT)弯曲,但如果内存访问速度慢,则条件方法(CEV)或按位评估方法(BEV)可能会受益于xor与负载的速度.给定CPU.

(CEV)将来自寄存器的比较和条件移动分解为2个加载有效地址,不易于误预测.所有这些命令在奔腾管道中都是可配对的.所以他们实际上进入了一个周期.

  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以及用于对齐的一些nops,并且应该采用最小的1个周期.如前所述,只有数据依赖.

  48 63 ff                movslq %edi,%rdi
  8b 04 bd 00 1d 40 00    mov    0x401d00(,%rdi,4),%eax

(BEV)是一个不同的野兽,因为它实际上需要2个mov + 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是一个候选者)只转换一个信号char.相反,人们会期望通过实际制作循环并调用该函数来转换更大的字符串.

因此,在这种情况下,更好的可矢量化的代码是胜利者.LUT没有矢量化,BEV和CEV具有更好的行为.一般来说,这样的微优化不会让你随处可见,编写你的代码并让它们直播(即让编译器运行).

所以我实际上已经在这个意义上建立了一些测试,这些测试可以在任何具有c ++ 11编译器和随机设备源的系统上轻松重现,例如任何*nix系统.如果一个人不允许矢量化-O2CEV/LUT几乎相等,但一旦-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表的线性度.

[简单易行]:条件评估 - > 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 int decfromhex()
{
  int constexpr x = n;
  return x<58 ? x-48 : x -87;
}

[查找表]:查找表 - > 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];
}

在所有,最后似乎是最快的,在第一次看.第二个是仅在编译时和常量表达式.

[结果](请确认):*BEV是最快的,处理大小写字母,但仅限于不处理大写字母的CEV.随着字符串大小的增加,LUT变得比CEV和BEV都慢.

str-size 16-12384的示例性结果可以在下面找到(越低越好)

在此输入图像描述

显示平均时间(100次运行).气泡的大小是正常的误差.

可以使用运行测试的脚本.

已经在一组随机生成的字符串上对conditional CEV,bitwise BEV和lookup table LUT进行了测试.测试相当简单,来自:

测试源代码

这些是可以验证的:

    一个输入的本地副本串被放置在每次本地缓冲区.

    一个结果的本地副本被保存,然后将其复制到堆,每串测试

    仅提取对字符串操作的时间的持续时间

    统一的方法,没有复杂的机械和包装/周围的代码适合其他情况.

    没有采样使用整个时序

    执行CPU预热

    在测试之间进行休眠以允许编组代码,使得一个测试不利用先前的测试.

    编译是用.进行的g++ -std=c++11 -O3 -march=native dectohex.cpp -o d2h

    启动与taskset -c 0 d2h

    没有线程依赖或多线程

    实际上正在使用结果,以避免任何类型的循环优化

作为附注,我在练习版本3中看到使用较旧的c ++ 98编译器要快得多.

[BOTTOM LINE]:毫无顾虑地使用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解决方案一样快.

我的个人电脑上的字符串大小为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
-------------------------------------------------------------------

例如,为了总共不同的字符串,2sec在一个大小的str上暂停运行测试,输出计时,并在以下命令中计数,编译并运行测试.25610000double precisionnanoseconds

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

你的BEV是正确的,还是应该是'9*(x >> 6)+(x&0xf)`？你的pastebin也使用了decfromhex2的三元组.
推荐阅读
devbox
135369一生真爱_890
这个屌丝很懒，什么也没留下！
关注作者
Tags | 热门标签
RankList | 热门文章
DevBox开发工具箱 | 专业的在线开发工具网站    京公网安备 11010802040832号  |  京ICP备19059560号-6
Copyright © 1998 - 2020 DevBox.CN. All Rights Reserved devBox.cn 开发工具箱 版权所有