二进制字符串转十六进制（C++）

Question

二进制字符串转十六进制（C++）

9

当把二进制字符串转换为十六进制时，我只能按照我找到的答案来处理一定大小的字符串。但我希望以比目前唯一能够完全处理的方法更有效地将海量二进制字符串转换成完整的十六进制形式：

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

2

你的代码因二进制未对齐到4位而失败... - W.F.

我们可以假设输入是4位的倍数吗？ - sehe

1

我确实说过“巨大的二进制字符串”——是的，这些字符串总是4的倍数。 - fakeaccount

2

以Nx4个8位字符的缓冲区为流。忘记它们是字符，将缓冲区视为uint32_t *，然后您可以一次比较32位。比玩弄字符串和字符要快得多。 - Andy Brown

在字符串中保留空间大小为size()/4。否则，使用stringstream。 - Rado

显示剩余2条评论

10个回答

5

可能是这样的

，这样的东西。

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

- user4703182

这将如何支持“大量二进制字符串”？（强调不是我的） - sehe

3

这是我提到的其中一个解决方案之一——顺便说一下，谢谢你没有把强调归功于自己 :P - fakeaccount

4

更新2 请参考此处的基于完美哈希的解决方案。我更偏向于这个解决方案，因为：

编译速度更快
运行时更可预测（由于所有数据都是静态的，因此没有发生任何分配）

编辑：实际上现在进行的基准测试显示，完美哈希解决方案比Spirit方案快约340倍。点击此处查看：

更新

添加了基于Trie结构的解决方案。

此处的查询表使用Boost Spirit的内部Trie实现进行快速查询。

当然，如果你喜欢，可以将out替换为例如向量back_inserter或ostreambuf_iterator<char>到你的字符串流。现在，它甚至不会分配4个字符（虽然当然查询表会被分配一次）。

你还可以将输入迭代器轻松替换为任何可用的输入范围，而不改变代码的其余部分。

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

你确实可以将转换变成查找表。不要使用基于树的映射，因为它会追踪很多指针。然而，boost::flat_map 可能是个不错的选择。

- sehe

添加了一种基于 Trie 的解决方案，它在内存中甚至不会分配超过 4 个字节。输入和输出都是流式的。我现在已经测试了查找表。请在 **Coliru 上实时查看**。 - sehe

4

这是我的做法：

找到最小的正整数 n，使得这些整数在模 n 意义下余数不同：

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

这些是“0000”、“0001”等的ASCII表示。我按顺序列出它们，假设你的机器是大端字节序；如果是小端字节序，则例如“0001”的表示将为0x31303030，而不是0x30303031。你只需要执行一次此操作。n不会很大——我预计它应该小于100。

构建一个表格 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];

- TonyK

很好，使用模运算的解决方案不错。当我在考虑一次比较32位时，我也尝试想出一种算术/位移方法来将比较减少到一个表格中。但从未想过使用模运算。我喜欢这个方法。 - Andy Brown

这给了我灵感，你的想法在概念上接近完美哈希。我实现了它（https://dev59.com/Sojca4cB1Zd3GeqP4v55#29214966）：LUT是26项 - 这并不需要太多开销，并且所有机器都是constexpr。 - sehe

你的魔数'n'是18。在紧密循环中只有一个'%'，我看不出这怎么可能更快。在x86汇编语言中，余数作为'div'指令的一部分返回，因此这种方法应该是最优的。 - Andy Brown

4

我有一种奇怪的感觉，似乎我在这个问题上漏掉了一些重要的东西。乍一看，这似乎应该可以解决：

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实现）都会进行额外的复制。

无论如何，使用它看起来应该像这样:

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

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

由于它使用迭代器，因此可以轻松地（只是一个明显的例子）从istreambuf_iterator中获取输入以直接处理来自文件的数据。然而，这通常不是最快的方法--通常使用istream::read读取大块数据，然后使用ostream::write一次写入大块数据会获得更好的速度。但这不需要影响实际的转换代码--您只需将指针传递到输入和输出缓冲区中，它将使用它们作为迭代器。

- Jerry Coffin

你的版本在逻辑上接近于我的“天真”版本。但不知何故，它的速度却与完美哈希解决方案一样快。我稍后会看看原因。暂时给你点赞+1。 - sehe

1

你如何更改 char input[] = ... 的输入？ - fakeaccount

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）每个字符占8位（并非所有平台均为真实情况）

2）它需要小端序（意味着至少在x86、x86_64上可用）

它假定binaryVecStr是std::vector，但也可以使用字符串。它假定binaryVecStr.size() % 4 == 0

- graywolf

你仍然为完整的缓冲区保留内存，如果流大小变大（例如大于可用内存），这将成为一个阻碍。 - sehe

我已经这样做，并将其与我的解决方案进行了基准测试（有关更多结果，请参见我的答案）。当我使用您的针对流IO进行优化的代码并在相同的测试环境中进行测试时，它以约314MB/s的速度运行。至少输出是_正确_的，没有修复（我只是将十六进制数字变成小写字母，以便可以校验结果的正确性）。以下是用于基准测试的精确代码：**Live On Coliru** - sehe

好的，1.14GB/s相当令人印象深刻。就我的解决方案而言，我有点失望它这么慢 :/ - graywolf

我不确定。我猜测这是分支的原因：http://goo.gl/2Xg1Hw。但它并不是很慢 :) 大多数解决方案要慢得多。 - sehe

3

这是我能想到的最快的方法：

#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 的基准测试结果，它比其他任何东西都要快。

- orlp

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

< p > hexDigitTable 的内容（类型为 char[16]）取决于您所用的是小端或大端机器。 < /p >

- David K

使用这个测试程序，我已经将这个解决方案的基准测试速度达到了约307MB/s。当然，在循环中进行字符串构建会不必要地减慢它的速度。在 **Coliru上实时查看**（以及反汇编 http://goo.gl/KYvUxb）中查看它。 - sehe

@sehe，这个回答比你的要少雄心壮志得多！我只是想做一件事，就是在不重新思考程序逻辑的情况下减少每个循环执行的“if”数量。这是一个小而快速的优化。改变字符串构建方式也是一个好主意。你在哪里进行了基准测试？ - David K

在我的工作站上，我目前正在修复最后输入块处理中的一个错误（之前没有注意到，因为4 GB是4 KB的倍数）。 - sehe

2

对于这个问题，我觉得有一个简单的方法：

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整除，我不知道会发生什么，而且我也没有测试过这段代码的性能。 在线示例

- PaperBirdMaster

如所述，此代码存在几个问题。吞吐量大约为8.5MB/s，您可以在我的答案中进行比较。我使用了这个来进行基准测试：**Live On Coliru**。看看您能否找到已修复的问题（除了偏爱流式传输之外） :) - sehe

@sehe总是很乐意教我们如何改进代码，非常感谢（还有感谢你帮忙而不是投反对票）:D - PaperBirdMaster

1

我认为使用Trie树或其他数据结构太过复杂，我更愿意选择一些计算量较大但背后的算法更加合理和整洁的方案：反向扫描并对四个元素进行分组。

但是我的解决方案仍然强健可靠且具有功能性，它可以处理长的二进制字符串，并且还包括检查代码和删除前缀0函数：

string bstohs(const string& bs) {
    string hs = {};
    auto c = bs.rbegin();
    auto end = bs.rend();
    if (bs.rfind("0b", 0) == 0) {
        end -= 2;
    }
    int localSum = 0;
    while (end - c > 3) {
        localSum = (*c - '0') + ((*(c + 1) - '0') << 1) + ((*(c + 2) - '0') << 2) + ((*(c + 3) - '0') << 3);
        hs = (localSum > 9 ? string(1, 'a' + localSum - 10) : to_string(localSum)) + hs;
        c += 4;
    }
    localSum = 0;
    for (auto lst = c; end - lst > 0; lst++) {
        if (*lst != '0') {
            localSum += ((*lst - '0') << (lst - c));
        }
    }
    hs = to_string(localSum) + hs;
    return "0x" + hs.erase(0, min(hs.find_first_not_of('0'), hs.size() - 1));
}

以下是测试主函数：

int main(){
    string bs = "0b";
    srand((unsigned)time(NULL)); 
    int test_time, test_max_len;
    cout << "input test time: ";
    cin >> test_time;
    cout << "input test max len: ";
    cin >> test_max_len;
    for (int i = 0; i < test_time; i++) {
        int test_len = rand() % test_max_len;
        bs += "1";
        for (int j = 1; j < test_len; j++) {
            bs += to_string(rand() % 2);
        }
        cout << "test case " << i << "\nraw bs: " << bs << "\nbin len: " << bs.size() - 2 << "\nnow hs: " << bstohs(bs) << endl;
        bs = "0b";
    }
    return 0;
}

一个测试用例:

input test time: 3
input test max len: 400
test case 0
raw bs: 0b1111000001010110010011101010111110001101111101001101000110111111000110011000111000001100111101010111010010000111011001000010100110010100001000101001010001111111010010111111111000000101100110100000000101110111110000110100011001100111111100101011101111010000001101001000011000110110011000011000110110001101010011000001111101111010010010100001010100010110010
bin len: 355
now hs: 0x782b2757c6fa68df8cc7067aba43b214ca114a3fa5ff02cd00bbe1a333f95de81a431b30c6c6a60fbd250a8b2
test case 1
raw bs: 0b110111101010110011001110000110001101010100011011100111000000000111010011000100000011110010100100001101111000100010011110001010100000101010001101011001110111010010001100111011101010100010000110011111011110100010110100010000010010001011111000101110101100110010111010001111010101110011111110
bin len: 288
now hs: 0xdeacce18d51b9c01d3103ca437889e2a0a8d67748ceea8867de8b44122f8baccba3d5cfe
test case 2
raw bs: 0b11010001010111100010001010100111011010111110001111011100000111111011001010110010011011110101001111011
bin len: 101
now hs: 0x1a2bc454ed7c7b83f6564dea7b

环境:

#include <iostream>
#include <string>
#include <stdlib.h>
using namespace std;

- user14844539

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- sehe · Accepted Answer

更新：在文末添加了比较和基准测试。

这里有另一种方法，基于完美哈希。使用gperf生成了完美哈希（就像这里描述的那样：是否可能比使用哈希映射更快地将字符串映射到整数？）。

我进一步优化了代码，将函数局部静态变量挪到了一边，并将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查找。请注意，在DEBUG构建中，它使用assert验证输入：

在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（无hack，无库）; 在Godbolt上进行实时反汇编

spirit.cpp（Trie）; 在pastebin上进行实时反汇编
和这个答案：perfect.cpp哈希基础; 在Godbolt上进行实时反汇编

为了进行一些比较，我：

使用相同的编译器（GCC 4.9）和标志（-O3 -march=native -g0 -DNDEBUG）对它们进行了编译
优化了输入/输出，使其不会每次读取4个字符/写入单个字符
创建了一个大的输入文件（1千兆字节）

以下是结果：

令人惊讶的是，第一个答案中的naive方法表现得相当不错
Spirit在这里表现非常差; 它的吞吐量为3.4MB/s，因此整个文件需要294秒（！！！）。我们已经将其从图表中删除了
平均吞吐量为naive.cpp约为720MB/s，而perfect.cpp约为1.14GB/s
这使得完美哈希方法比朴素方法快大约50%。

*摘要我会说朴素方法足够好如我10小时前发布的那样。如果您真的想要高吞吐量，则完美哈希是一个不错的开始，但请考虑手动编写基于SIMD的解决方案