Binary Division Vs Decimal Divison As I was working with a program for my CRC code calculation, I hit upon a situation where I had to divide two binary strings. Now, what I did was just convert the binary string to decimal format, did a modulo operation to find out the remainder. 

But as it turns out, I am wrong in every single sample cases. 
For example, in this post, the dividend is 3664 and the divisor is 27. 

Now, 3664 mod 27 is 19, which does not agree with the remainder presented in the figure which says it's 4. 

Please help me out here. 

Thanks in advance :)
Short answer: don't do that. The CRC calculation is not division of
one number by another, and if you try to treat it as such
(by converting to decimal and doing ordinary division on the decimal numbers)
you will usually get the wrong answer.



Long answer:

The CRC calculation represents the incoming data as a polynomial
whose coefficients are in $\mathbb Z/2\mathbb Z$,
that is, the coefficients are integers modulo $2$,
which have the subtraction rules
\begin{align}
0 - 0 \equiv 0 \pmod 2 \\
1 - 0 \equiv 1 \pmod 2 \\
1 - 1 \equiv 0 \pmod 2 \\
0 - 1 \equiv 1 \pmod 2 \\
\end{align}
The last equation is the one that makes it impossible to treat the
XOR "division" algorithm the same as division of one multiple-digit
binary number by another.

So a string of binary bits in this algorithm is never treated as a
binary number, that is, as a sum of powers of $2$.
Instead it is treated as a polynomial, a sum of powers of $x$.
The rightmost bit is the constant term of our polynomial; the
bit to the left of that is the coefficient of $x$, the next bit
to the left is the coefficient of $x^2$, and so forth.

For example, suppose the bits of our divisor are $1011$ as in the
example on the Wikipedia page.
We do not treat these bits as a number (whose value would be eleven);
instead, we treat the bits $1,1,0,1$ as coefficients of the polynomial 
$1x^3+0x^2+1x+1 = x^3+x+1$ modulo $2$.

Now to make this a very simple example,
suppose the incoming message is not $11010011101100,$ as
in Wikipedia's example, but instead is  $00000000000001.$

The first step of the algorithm is to pad the message
to $00000000000001000,$ which will be treated as the polynomial
$1x^3+0x^2+0x+0 = x^3$ modulo $2.$
Now the synthetic division of $x^3$ by $x^3+x+1$
looks like this modulo $2$:
\begin{align}
1 &amp;\\
1x^3+0x^2+1x+1\ \overline{)\ 1x^3 +0x^2+0x+0} &amp;\\
\underline{1x^3+0x^2+1x+1} \\
1x + 1
\end{align}

Notice that we used the rule $0 - 1 \equiv 1 \pmod 2$
for the last two terms on the right,
that is, we used the fact that $-1\equiv1 \pmod2.$
Another way to write this is: 
$$
x^3 - (x^3+x+1) = x^3 - x^3 - x - 1 = -x - 1 \equiv x + 1 \pmod 2.
$$
The remainder of the division is the polynomial $x+1$,
which gives us the CRC bits $011.$

But notice that if you try to view the dividend and divisor as
numbers and the CRC bits as the remainder when dividing one
number by another, the result above makes no sense at all.
The dividend is the number eight, the divisor is eleven,
and therefore the remainder should just be eight again
(since the divisor is greater than the dividend).
But the CRC bits appear to be the number three!
(Notice that this result is just as nonsensical for binary numbers
as for decimal numbers, which is one reason I wrote the names of
the numbers in English rather than using their decimal
representations.)



Incidentally, there is a very good reason not to use an algorithm
that would be equivalent to division of numbers:
division of numbers is a very expensive operation compared to
the XOR "division" algorithm, even if all we want is the remainder
and we ignore the quotient.
In fact, division of one number by another is one of the most
time-consuming of the "simple" arithmetic operations on a computer.
(The exception is division by a power of $2,$ which is very fast
but would be useless in a CRC-like algorithm.)

By using the XOR algorithm, a computer can process a long stream
of incoming data while using a lot less of its resources than would
otherwise be required, leaving those resources free to do something else.
If the CRC check is performed by specialized hardware,
that hardware can be far simpler than it would have had to be
if it needed to find the remainder of a numerical division.
Aha!

Here is the part you mean:

11010011101100 000 &lt;--- input right padded by 3 bits

1011               &lt;--- divisor (4 bits) = x³ + x + 1

If you convert 110100111011000
from binary,
you get
27096.

If you convert 110100111011
from binary,
you get
3387,
not
3664,
which is
11100101000 in binary.