如何划分位集?
How can I divide bitsets?
我用两个bitsets来存储两个多项式。我希望其中之一除以 2,我想得到除法后的余数。例如,如果我想要它在纸上:
w1= 110011010000000
w2 = 1111001
101000100
110011010000000 : 1111001
1111001
--1111110
1111001
----1110000
1111001
---100100 = remainder
很少有 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;
}
我用两个bitsets来存储两个多项式。我希望其中之一除以 2,我想得到除法后的余数。例如,如果我想要它在纸上:
w1= 110011010000000
w2 = 1111001
101000100
110011010000000 : 1111001
1111001
--1111110
1111001
----1110000
1111001
---100100 = remainder
很少有 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;
}