二进制字符串到十六进制 C++

Question

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

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

它彻底而绝对，但是很慢。

有更简单的方法吗？

Answer 1

UPDATE2 请参阅。我更喜欢这个解决方案，因为

编译速度快很多
它有更多的预测table运行时（正在进行零分配，因为所有数据都是静态的）

EDIT indeed now benchmarking has shown the perfect hash solution to be roughly 340 x faster than the Spirit approach.

更新

添加了一个Trie-based solution。

这里的lookup-table使用了Boost Spirit内部的Trie实现来实现快速查找

当然可以将 out 替换为例如如果您愿意，可以将向量 back_inserter 或 ostreambuf_iterator<char> 添加到您的字符串流中。现在它从来没有分配过 4 个字符（当然查找 table 被分配了一次）。

您还可以简单地将输入迭代器替换为您可用的任何输入范围，而无需更改其余代码的一行。

Live On Coliru

#include <iostream>
#include <boost/spirit/include/qi.hpp>
#include <boost/spirit/include/phoenix.hpp>

namespace qi = boost::spirit::qi;

int main() {
    std::ostreambuf_iterator<char> out(std::cout);

    qi::symbols<char, char> lookup_table;
    lookup_table.add
        ("0000", '0')
        ("0001", '1')
        ("0010", '2')
        ("0011", '3')
        ("0100", '4')
        ("0101", '5')
        ("0110", '6')
        ("0111", '7')
        ("1000", '8')
        ("1001", '9')
        ("1010", 'a')
        ("1011", 'b')
        ("1100", 'c')
        ("1101", 'd')
        ("1110", 'e')
        ("1111", 'f')
        ;

    boost::spirit::istream_iterator bof(std::cin), eof;

    if (qi::parse(bof, eof, +lookup_table [ *boost::phoenix::ref(out) = qi::_1 ]))
        return 0;
    else
        return 255;
}

当使用像 od -A none -t o /dev/urandom | tr -cd '01' | dd bs=1 count=4096 | ./test 这样的随机数据进行测试时，您会得到

dfc87abf674d8fdb28ed2e36d8ac99faa9c9c4a8aa2253763510482c887e07b2e24cf36ecb7abdcb31521becca54ba1c2ff4be0399f76c2ca28c87fe13a735a0f8031959e5ed213a5d02fb71cbf32b978d2ee9e390a0e2fc6b65b24b2922fb7554a9b211ca1db1b757d1cd0b468d1cd399b114f4f8ef93ade4f33a18bcdb25e2b8138dcd7ec7ef7d2a53f905369c261e19556356ab96f0608bd07f908d3430d3fe7ec21a234c321cc79788f934250da6d2d8e2cb51173ad64ffb4769e7a28224e9bc68123249bbd9c19c01ebbdf2fe4824fb854cf018268d7a988bfd0169f395b30937230733e0f17ba3d8f979341ebde6ff48aac764c2a460625a3ec1349351fe15c8cd4cd3e2933a2840392e381e3c8fc69456eaaf4e8257837f92124e8918a071d7a569fba5e7b189831aa761b3a63feb45d317b1724c53659c00bc82ce7a0c4bcbdc196bc5c990eddc70248d49cc419721d82714256ed13568c4f0740efe42401b0ce644dceaf3507e4acae718265101562f81c237ea8551d051cba38a087fc260af83e123f774e8da956d885d0f87e72e336d8599631f3a44d30676088149b5a1292ecc8682cfbd6982bc37b7e6a5c44f42fcfaabd32c29696a6985fdca5bd6c986dfd4670c4456ac0a7e6ae50ba4218e090f829a2391dd9fc863b31c05a

老，初级答案：

从流中读取输入并每 4 个字节输出一个字符。

要点如下：

char nibble[4];
while (std::cin.read(nibble, 4))
{
    std::cout << "0123456789abcdef"[
            (nibble[0]!='0')*8 +
            (nibble[1]!='0')*4 +
            (nibble[2]!='0')*2 +
            (nibble[3]!='0')*1
        ];
}

您确实可以将转换设为查找 table。不要使用地图，因为它是基于树的，最终会追逐很多指针。但是，boost::flat_map 可能没问题。

Answer 2

您可以尝试二元决策树：

string binToHex;
for (size_t i = 0; i < binaryVecStr[a].size(); i += 4) {
    string tmp = binaryVecStr[a].substr(i, 4);
    if (tmp[0] == '0') {
        if (tmp[1] == '0') {
            if (tmp[2] == '0') {
                if tmp[3] == '0') {
                    binToHex += "0";
                } else {
                    binToHex += "1";
                }
            } else {
                if tmp[3] == '0') {
                    binToHex += "2";
                } else {
                    binToHex += "3";
                }
            }
        } else {
            if (tmp[2] == '0') {
                if tmp[3] == '0') {
                    binToHex += "4";
                } else {
                    binToHex += "5";
                }
            } else {
                if tmp[3] == '0') {
                    binToHex += "6";
                } else {
                    binToHex += "7";
                }
            }
        }
    } else {
        if (tmp[1] == '0') {
            if (tmp[2] == '0') {
                if tmp[3] == '0') {
                    binToHex += "8";
                } else {
                    binToHex += "9";
                }
            } else {
                if tmp[3] == '0') {
                    binToHex += "A";
                } else {
                    binToHex += "B";
                }
            }
        } else {
            if (tmp[2] == '0') {
                if tmp[3] == '0') {
                    binToHex += "C";
                } else {
                    binToHex += "D";
                }
            } else {
                if tmp[3] == '0') {
                    binToHex += "E";
                } else {
                    binToHex += "F";
                }
            }
        }
    }
}
hexOStr << binToHex;

您可能还想考虑更紧凑的表示同一个决策树，比如

string binToHex;
for (size_t i = 0; i < binaryVecStr[a].size(); i += 4) {
    string tmp = binaryVecStr[a].substr(i, 4);
    binToHex += (tmp[0] == '0' ?
                    (tmp[1] == '0' ?
                        (tmp[2] == '0' ?
                            (tmp[3] == '0' ? "0" : "1") :
                            (tmp[3] == '0' ? "2" : "3")) :
                        (tmp[2] == '0' ?
                            (tmp[3] == '0' ? "4" : "5") :
                            (tmp[3] == '0' ? "6" : "7"))) :
                    (tmp[1] == '0' ?
                        (tmp[2] == '0' ?
                            (tmp[3] == '0' ? "8" : "9") :
                            (tmp[3] == '0' ? "A" : "B")) :
                        (tmp[2] == '0' ?
                            (tmp[3] == '0' ? "C" : "D") :
                            (tmp[3] == '0' ? "E" : "F"))));
}
hexOStr << binToHex;

更新： 按照 ASCII 到整数解决方案的思路：

unsigned int nibble = static_cast<unsigned int*>(buffer);
nibble &= 0x01010101;     // 0x31313131 --> 0x01010101
nibble |= (nibble >> 15); // 0x01010101 --> 0x01010303
nibble |= (nibble >> 6);  // 0x01010303 --> 0x0105070C
char* hexDigit = hexDigitTable[nibble & 15];

hexDigitTable（char[16] 类型）的内容将取决于是否你在小端或大端机器上。

Answer 3

这似乎有效。

std::vector<char> binaryVecStr = { '0', '0', '0', '1', '1', '1', '1', '0' };

string binToHex;
binToHex.reserve(binaryVecStr.size()/4);
for (uint32_t * ptr = reinterpret_cast<uint32_t *>(binaryVecStr.data()); ptr < reinterpret_cast<uint32_t *>(binaryVecStr.data()) + binaryVecStr.size() / 4; ++ptr) {
    switch (*ptr) {
        case 0x30303030:
            binToHex += "0";
            break;
        case 0x31303030:
            binToHex += "1";
            break;
        case 0x30313030:
            binToHex += "2";
            break;
        case 0x31313030:
            binToHex += "3";
            break;
        case 0x30303130:
            binToHex += "4";
            break;
        case 0x31303130:
            binToHex += "5";
            break;
        case 0x30313130:
            binToHex += "6";
            break;
        case 0x31313130:
            binToHex += "7";
            break;
        case 0x30303031:
            binToHex += "8";
            break;
        case 0x31303031:
            binToHex += "9";
            break;
        case 0x30313031:
            binToHex += "A";
            break;
        case 0x31313031:
            binToHex += "B";
            break;
        case 0x30303131:
            binToHex += "C";
            break;
        case 0x31303131:
            binToHex += "D";
            break;
        case 0x30313131:
            binToHex += "E";
            break;
        case 0x31313131:
            binToHex += "F";
            break;
        default:
            // invalid input
            binToHex += "?";
    }
}

std::cout << binToHex;

注意，它使用了一些假设：

1) char 有 8 位（并非在所有平台上都是如此）

2) 它需要小端（意味着它至少在 x86 上工作，x86_64）

它假设 binaryVecStr 是 std::vector，但也适用于字符串。它假设 binaryVecStr.size() % 4 == 0

Answer 4

可能是这样的

#include <iostream>
#include <string>
#include <iomanip>
#include <sstream>
int main()
{
    std::cout << std::hex << std::stoll("100110110010100100111101010001001101100101010110000101111111111",NULL,  2) << std::endl;

    std::stringstream ss;
    ss << std::hex << std::stoll("100110110010100100111101010001001101100101010110000101111111111", NULL, 2);
    std::cout << ss.str() << std::endl;

    return 0;
}

Answer 5

以下是我的做法：

找到最小的正整数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。

构建一个 table char HexChar[n] 和 HexChar[0x30303030 % n] = '0', HexChar[0x30303031 % n] = '1' 等（或者 HexChar[0x31303030 % n] = '1' 等，如果你的机器是小端）。

现在转换快如闪电（我假设 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];

Answer 6

至于一个简单的方法来做到这一点，我认为这个非常简洁：

std::string bintxt_2_hextxt(const std::string &bin)
{
    std::stringstream reader(bin);
    std::stringstream result;

    while (reader)
    {
        std::bitset<8> digit;
        reader >> digit;
        result << std::hex << digit.to_ulong();
    }

    return result.str();
}

我不知道应该从哪里读取你的数据，所以我使用了 std::string 作为输入数据；但如果它来自文本文件或数据流，将 reader 更改为 std::ifstream.

应该不会让人头疼

小心！我不知道如果流字符不能被 8 整除会发生什么，而且我还没有测试这段代码的性能。

Live example

Answer 7

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

这是另一个基于完美哈希的方法。完美的哈希是使用 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 class，使用 hexchar 查找略微编辑和扩展。请注意，它确实使用 assert:

在 DEBUG 构建中验证输入

Live On Coliru

#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

03bef5fb79c7da917e3ebffdd8c41488d2b841dac86572cf7672d22f1f727627a2c4a48b15ef27eb0854dd99756b24c678e3b50022d695cc5f5c8aefaced2a39241bfd5deedcfa0a89060598c6b056d934719eba9ccf29e430d2def5751640ff17860dcb287df8a94089ade0283ee3d76b9fefcce3f3006b8c71399119423e780cef81e9752657e97c7629a9644be1e7c96b5d0324ab16d20902b55bb142c0451e675973489ae4891ec170663823f9c1c9b2a11fcb1c39452aff76120b21421069af337d14e89e48ee802b1cecd8d0886a9a0e90dea5437198d8d0d7ef59c46f9a069a83835286a9a8292d2d7adb4e7fb0ef42ad4734467063d181745aaa6694215af7430f95e854b7cad813efbbae0d2eb099523f215cff6d9c45e3edcaf63f78a485af8f2bfc2e27d46d61561b155d619450623b7aa8ca085c6eedfcc19209066033180d8ce1715e8ec9086a7c28df6e4202ee29705802f0c2872fbf06323366cf64ecfc5ea6f15ba6467730a8856a1c9ebf8cc188e889e783c50b85824803ed7d7505152b891cb2ac2d6f4d1329e100a2e3b2bdd50809b48f0024af1b5092b35779c863cd9c6b0b8e278f5bec966dd0e5c4756064cca010130acf24071d02de39ef8ba8bd1b6e9681066be3804d36ca83e7032274e4c8e8cacf520e8078f8fa80eb8e70af40367f53e53a7d7f7afe8704c46f58339d660b8151c91bddf82b4096

基准

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

naive.cpp (no hacks, no libraries); Live disassembly on Godbolt
spirit.cpp (Trie); ~~Live~~ disassembly on pastebin
和this answer: perfect.cpp hash based; Live disassembly on Godbolt

为了做一些比较，我

使用相同的编译器 (GCC 4.9) 和标志 (-O3 -march=native -g0 -DNDEBUG) 编译它们
优化 input/output 所以它不会被 4 chars/write 个单个字符读取
创建了一个大输入文件（1 GB）

结果如下：

令人惊讶的是，第一个答案中的 naive 方法效果相当好
这里精神真的很差；它的速度为 3.4MB/s，因此整个文件需要 294 秒 (!!!)。我们已经将它排除在排行榜之外
naive.cpp 的平均吞吐量约为 720MB/s，perfect.cpp[=82= 的平均吞吐量约为 1.14GB/s ]

这使得完美哈希方法比朴素方法快大约 50%。

*Summary I'd say the naive approach was plenty good on whim 10 hours ago. If you really want high throughput, the perfect hash is a nice start, but consider hand-rolling a SIMD based solution

Answer 8

我有一种奇怪的感觉，我一定错过了关于这里问题的一些重要信息。乍一看，这似乎应该可行：

template <class RanIt, class OutIt>
void make_hex(RanIt b, RanIt e, OutIt o) {
    static const char rets[] = "0123456789ABCDEF";

    if ((e-b) %4 != 0)
        throw std::runtime_error("Length must be a multiple of 4");

    while (b != e) {
        int index = 
            ((*(b + 0) - '0') << 3) |
            ((*(b + 1) - '0') << 2) |
            ((*(b + 2) - '0') << 1) |
            ((*(b + 3) - '0') << 0);
        *o++ = rets[index];
        b += 4;
    }
}

至少，这似乎应该尽可能快——在我看来，它非常接近获得输出所需的每个输入的最小处理量。

为了最大限度地提高速度，它确实将对输入的错误检查减少到（可能低于）最低限度。您当然可以根据减法的结果确定输入中的每个字符之前是“0”还是“1”。或者，您可以很容易地使用 (*(b + 0) != '0') << 3 将 0 视为 0，将其他任何内容视为 1。同样，您可以使用：(*(b + 0) == '1') << 3 将 1 视为 1，将其他任何内容视为 0。

该代码确实避免了计算每个 index 值所需的 4 次计算之间的依赖关系，因此智能编译器应该可以并行执行这些计算。

因为它只适用于迭代器，所以它避免了对输入数据进行额外的复制，因为（例如）几乎任何使用 substr 的东西都可以（特别是 std::string 的实现不t 包括短字符串优化）。

无论如何，使用它看起来像这样：

int main() { 
    char input[] = "0000000100100011010001010110011110001001101010111100110111101111";

    make_hex(input, input+64, std::ostream_iterator<char>(std::cout));
}

因为它确实使用迭代器，所以它可以很容易地（仅举一个明显的例子）从 istreambuf_iterator 获取输入以直接从文件处理数据。不过，这很少是最快的方法——使用 istream::read 读取大块，使用 ostream::write 一次写入大块通常会获得更快的速度。不过，这不需要影响实际的转换代码——您只需将指针传递给输入和输出缓冲区，它就会将它们用作迭代器。

Answer 9

这是我能想到的最快速度：

#include <iostream>

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

        for (const char* it = buffer; it < buffer + got; it += 4) {
            unsigned long r;
            r  = it[3];
            r += it[2] * 2;
            r += it[1] * 4;
            r += it[0] * 8;
            *out++ = "0123456789abcdef"[r - 15*'0'];
        }

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

根据@sehe 的基准测试，它在这个问题上比其他任何东西都快。

二进制字符串到十六进制 C++

Binary String to Hex c++

c++

binary

hex

从流中读取输入并每 4 个字节输出一个字符。

我不希望事情变得比这快得多。

基准