Вы можете вычислить результат применения нулей n не за время O (1), а за время O (log n ).Это сделано в zlib's crc32_combine().Создается двоичная матрица, которая представляет операцию применения одного нулевого бита к CRC.Матрица 32x32 умножает 32-битный CRC на GF (2), где сложение заменяется на исключающее-или (^), а умножение заменяется на и (&), бит за битом.
Тогда эта матрица можетбыть в квадрате, чтобы получить оператор для двух нулей.Это в квадрате, чтобы получить оператор для четырех нулей.Третий возводится в квадрат, чтобы оператор получил восемь нулей.И так далее по мере необходимости.
Теперь этот набор операторов может быть применен к CRC на основе одного бита из числа n нулевых битов, для которого вы хотите вычислить CRC.
Вы можете предварительно вычислить результирующий матричный оператор для любого числа нулевых битов, если случайно узнаете, что будете часто применять именно столько нулей.Тогда это просто умножение матрицы на вектор, что на самом деле O (1).
Вам не нужно использовать инструкцию pclmulqdq, предложенную здесь в другом ответе, но это будет немного быстрееесли есть.Это не изменит O () операции.