c++ - 在 C++ 中检查哈希的大小

Question

就像使用区块链一样，我想检查散列是否满足大小要求。这在 Python 中相当容易，但我在 C++ 中实现相同的系统时遇到了一些困难。为了清楚我的目标，第一个例子是 python 实现:

difficulty = 25
hash = "0000004fbbc4261dc666d31d4718566b7e11770c2414e1b48c9e37e380e8e0f0"
print(int(hash, 16) < 2 ** (256 - difficulty))

我遇到的主要问题是这些数字 - 在 C++ 中很难处理如此大的数字(例如 2 ** 256)。这可以通过 boost/multiprecision 库解决:

boost::multiprecision::cpp_int x = boost::multiprecision::pow(2, 256)

但是，我似乎无法找到一种方法将我的哈希值转换为数值进行比较。这是我正在尝试做的一个通用示例:

int main() {
      string hash = "0000004fbbc4261dc666d31d4718566b7e11770c2414e1b48c9e37e380e8e0f0";
      double difficulty = 256 - 25;
      cpp_int requirement = boost::multiprecision::pow(2, difficulty);

      // Something to convert hash into a number for comparison (converted_hash)

      if (converted_hash < requirement) {
           cout << "True" << endl;
      }
      return 1;
}

散列是从我的 Web 服务器或本地 python 脚本接收的，在这种情况下，散列通过 fstream 读入 C++ 程序。无论哪种方式，它都会在到达时成为一个字符串。
由于我已经将python集成到这个项目中，我并不完全反对简单地使用这个算法的Python版本；但是，有时采取更简单的方法会阻止您学习，因此除非这是一项非常繁琐的任务，否则我想尝试用 C++ 来完成它。

Answer 1

您的基本需求是计算第一个非零位之前存在多少个零位。这实际上与多精度无关，它可以重新表述为一个简单的计数问题:

// takes hexadecimal ASCII [0-9a-fA-F]
inline int count_zeros(char ch) {
    if (ch < '1') return 4;
    if (ch < '2') return 3;
    if (ch < '4') return 2;
    if (ch < '8') return 1;
    return 0; // see ASCII table, [a-zA-Z] are all greater than '8'
}

int count_zeros(const std::string& hash) {
    int sum = 0;
    for (char ch : hash) {
        int zeros = count_zeros(ch);
        sum += zeros;
        if (zeros < 4)
            break;
    }
    return sum;
}

一个有趣的优化是意识到循环有两个终止条件，如果我们检查小于 '0' 的字符(包括空终止符)，我们可以将它们 fold 在一起，并且还会在任何无效输入上停止:

// takes hexadecimal [0-9a-fA-F]
inline int count_zeros(char ch) {
    if (ch < '0') return 0; // change 1
    if (ch < '1') return 4;
    if (ch < '2') return 3;
    if (ch < '4') return 2;
    if (ch < '8') return 1;
    return 0; // see ASCII table, [a-zA-Z] are all greater than '8'
}

int count_zeros(const std::string& hash) {
    int sum = 0;
    for (const char* it = hash.c_str(); ; ++it) { // change 2
        int zeros = count_zeros(*it);
        sum += zeros;
        if (zeros < 4)
            break;
    }
    return sum;
}

使用 g++ -Os 编译时会产生较小的代码.