Как я могу разделить биты?

Question

Я использую два bitsets для хранения двух полиномов. Я хочу, чтобы один из них был разделен на 2-й, и я хочу получить остаток после деления. Например, если я хотел бы это на бумаге:

w1= 110011010000000 
w2 = 1111001 

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

Answer 1

Очень немногие процессоры имеют встроенные инструкции для GF (2) разделение, как это, так что вам нужно реализовать его самостоятельно сдвигами и операцию XOR. В принципе, вы реализуете его точно так же, как вы делали это на бумаге, - сдвигайте делитель до тех пор, пока его верхний бит не сравняется с делителем, затем xor и сдвигом назад, записывая каждую позицию, где вам нужно xor как часть частного. Если все рассматриваемые многочлены совпадают в одном слове, вы можете просто использовать для него целые числа unsigned. В противном случае вам понадобится некоторый тип битового набора multiprecision. Для этого можно использовать 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; 
}