如果我想计算大量连续零字节的 CRC32 值，在给定零运行长度的情况下，是否可以使用恒定时间公式？例如，如果我知道我有 1000 个字节全部用零填充，有没有办法避免 1000 次迭代的循环（只是一个例子，对于这个问题，实际的零数量是无限的）？
您可以计算应用的结果n归零不是在 O(1) 时间内，而是在 O(logn） 时间。这是在 zlib 中完成的crc32_combine()。构造一个二进制矩阵来表示将单个零位应用于 CRC 的操作。 32x32 矩阵将 32 位 CRC 乘以 GF(2)，其中加法由异或 (^) 代替，乘法由与 (&) 逐位代替。
然后可以将该矩阵平方以获得两个零的运算符。将其平方以获得四个零的运算符。第三个平方得到八个零的运算符。依此类推。
现在可以根据数字中的一位将这组运算符应用于 CRCn您要计算其 CRC 的零位。
如果您碰巧知道您将经常应用恰好那么多的零，您可以预先计算任意数量的零位的结果矩阵运算符。那么它只是一个向量与一个矩阵相乘，实际上是 O(1)。
您不需要使用pclmulqdq此处另一个答案中建议了说明，但如果您有的话，速度会更快一些。它不会改变操作的 O()。
本文内容由网友自发贡献，版权归原作者所有，本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容，请联系:hwhale#tublm.com(使用前将#替换为@)
