c++ - 如何划分位集？

Question

我用两个 bitsets存储两个多项式。我希望其中之一除以 2，我想得到除法后的余数。例如，如果我希望它出现在纸上:

w1= 110011010000000
w2 = 1111001

           101000100
     110011010000000 : 1111001
     1111001
     --1111110
       1111001
       ----1110000
           1111001
           ---100100 = remainder

Answer 1

很少有 CPU 有像这样的 GF(2) 除法的内置指令，所以你需要自己用移位和异或来实现它。基本上，您可以像在纸上那样实现它——向上移动除数直到其最高位与被除数的最高位匹配，然后异或并向下移动，记录每个需要异或的位置作为商的一点。如果所有有问题的多项式都适合一个词，您可以只使用 unsigned 整数类型。否则，您将需要一些多精度位集类型。 C++ std::bitset 可用于此，尽管存在问题(没有简单的方法可以在不同大小的位集之间进行转换，没有位扫描函数)。

template<size_t N> int top_bit_set(const bitset<N> &a) {
    int i;
    for (i = N-1; i >= 0; i--)
        if (a.test(i)) break;
    return i;
}


template<size_t N>
bitset<N> gf2_div(bitset<N> dividend, bitset<N> divisor, bitset<N> &remainder) {
    bitset<N> quotient(0);
    int divisor_size = top_bit_set(divisor);
    if (divisor_size < 0) throw divide_by_zero();
    int bit;
    while ((bit = top_bit_set(dividend)) >= divisor_size) {
        quotient.set(bit - divisor_size);
        dividend ^= divisor << (bit - divisor_size); }
    remainder = dividend;
    return quotient;
}