二进制字符串到十六进制 c

Question

将二进制字符串更改为十六进制时，我只能根据我找到的答案将其设置为一定的大小。但是我想以比这更有效的方式将 MASSIVE Binary 字符串更改为完整的十六进制字符串，这是我遇到的唯一完全做到这一点的方法：

 for(size_t i = 0; i < (binarySubVec.size() - 1); i++){
    string binToHex, tmp = "0000";
    for (size_t j = 0; j < binaryVecStr[i].size(); j += 4){
        tmp = binaryVecStr[i].substr(j, 4);
        if      (!tmp.compare("0000")) binToHex += "0";
        else if (!tmp.compare("0001")) binToHex += "1";
        else if (!tmp.compare("0010")) binToHex += "2";
        else if (!tmp.compare("0011")) binToHex += "3";
        else if (!tmp.compare("0100")) binToHex += "4";
        else if (!tmp.compare("0101")) binToHex += "5";
        else if (!tmp.compare("0110")) binToHex += "6";
        else if (!tmp.compare("0111")) binToHex += "7";
        else if (!tmp.compare("1000")) binToHex += "8";
        else if (!tmp.compare("1001")) binToHex += "9";
        else if (!tmp.compare("1010")) binToHex += "A";
        else if (!tmp.compare("1011")) binToHex += "B";
        else if (!tmp.compare("1100")) binToHex += "C";
        else if (!tmp.compare("1101")) binToHex += "D";
        else if (!tmp.compare("1110")) binToHex += "E";
        else if (!tmp.compare("1111")) binToHex += "F";
        else continue;
    }
    hexOStr << binToHex;
    hexOStr << " ";
}

它彻底而绝对，但速度很慢。

有没有更简单的方法来做到这一点？

原文由 fakeaccount 发布，翻译遵循 CC BY-SA 4.0 许可协议

Answer 1

更新 最后添加了比较和基准

这是基于完美哈希的另一种方法。完美的哈希是使用 gperf 生成的（如下所述： Is it possible to map string to int faster than using hashmap? ）。

我通过将函数局部静态数据移开并将 --- hexdigit() 和 hash() 标记为 constexpr 来进一步优化。这消除了不必要的任何初始化开销，并为编译器提供了充分的优化空间/

我不认为事情会变得比这快得多。

如果可能，您 可以 尝试一次读取例如 1024 个半字节，并让编译器有机会使用 AVX/SSE 指令集对操作进行矢量化。 （我没有检查生成的代码是否会发生这种情况。）

在流模式下将 std::cin 转换为 std::cout 的完整示例代码是：

 #include <iostream>

int main()
{
    char buffer[4096];
    while (std::cin.read(buffer, sizeof(buffer)), std::cin.gcount())
    {
        size_t got = std::cin.gcount();
        char* out = buffer;

        for (auto it = buffer; it < buffer+got; it += 4)
            *out++ = Perfect_Hash::hexchar(it);

        std::cout.write(buffer, got/4);
    }
}

这是 Perfect_Hash 类，使用 hexchar 查找略有编辑和扩展。请注意，它确实验证了 --- 使用 assert DEBUG 构建的输入：

住在科利鲁

#include <array>
#include <algorithm>
#include <cassert>

class Perfect_Hash {
    /* C++ code produced by gperf version 3.0.4 */
    /* Command-line: gperf -L C++ -7 -C -E -m 100 table  */
    /* Computed positions: -k'1-4' */

    /* maximum key range = 16, duplicates = 0 */
  private:
      static constexpr unsigned char asso_values[] = {
          27, 27, 27, 27, 27, 27, 27, 27, 27, 27, 27, 27, 27, 27, 27, 27, 27, 27, 27, 27, 27, 27, 27, 27, 27, 27, 27,
          27, 27, 27, 27, 27, 27, 27, 27, 27, 27, 27, 27, 27, 27, 27, 27, 27, 27, 27, 27, 27, 15, 7,  3,  1,  0,  27,
          27, 27, 27, 27, 27, 27, 27, 27, 27, 27, 27, 27, 27, 27, 27, 27, 27, 27, 27, 27, 27, 27, 27, 27, 27, 27, 27,
          27, 27, 27, 27, 27, 27, 27, 27, 27, 27, 27, 27, 27, 27, 27, 27, 27, 27, 27, 27, 27, 27, 27, 27, 27, 27, 27,
          27, 27, 27, 27, 27, 27, 27, 27, 27, 27, 27, 27, 27, 27, 27, 27, 27, 27, 27, 27, 27, 27, 27};
      template <typename It>
      static constexpr unsigned int hash(It str)
      {
          return
              asso_values[(unsigned char)str[3] + 2] + asso_values[(unsigned char)str[2] + 1] +
              asso_values[(unsigned char)str[1] + 3] + asso_values[(unsigned char)str[0]];
      }

      static constexpr char hex_lut[] = "???????????fbead9c873625140";
  public:
#ifdef DEBUG
    template <typename It>
    static char hexchar(It binary_nibble)
    {
        assert(Perfect_Hash::validate(binary_nibble)); // for DEBUG only
        return hex_lut[hash(binary_nibble)]; // no validation!
    }
#else
    template <typename It>
    static constexpr char hexchar(It binary_nibble)
    {
        return hex_lut[hash(binary_nibble)]; // no validation!
    }
#endif
    template <typename It>
    static bool validate(It str)
    {
        static constexpr std::array<char, 4> vocab[] = {
            {{'?', '?', '?', '?'}}, {{'?', '?', '?', '?'}}, {{'?', '?', '?', '?'}},
            {{'?', '?', '?', '?'}}, {{'?', '?', '?', '?'}}, {{'?', '?', '?', '?'}},
            {{'?', '?', '?', '?'}}, {{'?', '?', '?', '?'}}, {{'?', '?', '?', '?'}},
            {{'?', '?', '?', '?'}}, {{'?', '?', '?', '?'}},
            {{'1', '1', '1', '1'}}, {{'1', '0', '1', '1'}},
            {{'1', '1', '1', '0'}}, {{'1', '0', '1', '0'}},
            {{'1', '1', '0', '1'}}, {{'1', '0', '0', '1'}},
            {{'1', '1', '0', '0'}}, {{'1', '0', '0', '0'}},
            {{'0', '1', '1', '1'}}, {{'0', '0', '1', '1'}},
            {{'0', '1', '1', '0'}}, {{'0', '0', '1', '0'}},
            {{'0', '1', '0', '1'}}, {{'0', '0', '0', '1'}},
            {{'0', '1', '0', '0'}}, {{'0', '0', '0', '0'}},
        };
        int key = hash(str);

        if (key <= 26 && key >= 0)
            return std::equal(str, str+4, vocab[key].begin());
        else
            return false;
    }
};

constexpr unsigned char Perfect_Hash::asso_values[];
constexpr char Perfect_Hash::hex_lut[];

#include <iostream>

int main()
{
    char buffer[4096];
    while (std::cin.read(buffer, sizeof(buffer)), std::cin.gcount())
    {
        size_t got = std::cin.gcount();
        char* out = buffer;

        for (auto it = buffer; it < buffer+got; it += 4)
            *out++ = Perfect_Hash::hexchar(it);

        std::cout.write(buffer, got/4);
    }
}

例如 od -A none -t o /dev/urandom | tr -cd '01' | dd bs=1 count=4096 | ./test

基准

我想出了三种不同的方法：

1. naive.cpp（没有 hacks，没有库） ； 在 Godbolt 上 实时拆卸
2. 精神.cpp （特里） ； pastebin 上的实时反汇编
3. 这个答案：基于 完美.cpp 哈希； 在 Godbolt 上 实时拆卸

为了做一些比较，我已经

• 使用相同的编译器（GCC 4.9）和标志（ -O3 -march=native -g0 -DNDEBUG ）编译它们
• 优化的输入/输出，因此它不会读取 4 个字符/写入单个字符
• 创建了一个大型输入文件（1 GB）

结果如下：

• 令人惊讶的是，第一个答案中的 naive 方法做得相当好
• 精神在这里真的很糟糕；它的网速为 3.4MB/s，因此整个文件需要 294 秒（！！！）。我们已将其排除在图表之外
• naive.cpp 的平均吞吐量约为 720MB/s， perfect.cpp 的平均吞吐量约为 1.14GB /s
• 这使得完美的散列方法比简单的方法快大约 50%。

*总结 我会说这种天真的方法非常好 ，因为我在 10 小时前一时兴起就发布了它。如果您真的想要高吞吐量，完美的哈希是一个不错的开始，但请考虑手动滚动基于 SIMD 的解决方案

原文由 sehe 发布，翻译遵循 CC BY-SA 3.0 许可协议

Answer 2

这是我的做法：

1. 找到最小的正整数 n 使得这些整数都有不同的余数模 n ：

   0x30303030 0x30303031 0x30303130 0x30303131 0x30313030 0x30313031 0x30313130 0x30313131 0x31303030 0x31303031 0x31303130 0x31303131 0x31313030 0x31313031 0x31313130 0x31313131

这些是 “0000”,“0001” 等的 ASCII 表示。我按顺序列出了它们，假设你的机器是大端的；如果是 little-endian，例如“0001”的表示将是 0x31303030，而不是 0x30303031。您只需执行一次。 n 不会很大——我希望它小于 100。

1. 用 HexChar[0x30303030 % n] = '0', HexChar[0x30303031 % n] = '1' 等（或 HexChar[0x31303030 % n] = '1' 等，如果你的机器是 little-endian）建立一个表 char HexChar[n] 。

现在转换速度快如闪电（我假设 sizeof (int) = 4 ）：

 unsigned int const* s = binaryVecStr[a].c_str();
for (size_t i = 0; i < binaryVecStr[a].size(); i += 4, s++)
    hexOStr << HexChar[*s % n];

原文由 TonyK 发布，翻译遵循 CC BY-SA 3.0 许可协议