# Calculating CRC by long division: How to decide the top number of long division?

Ok, I know how to use long division by using regular numbers, but when comes to binary numbers I'm getting confused.

In following calculation I can see the equation solved but I don't understand where the top number came from. How to decide what bit goes on top while doing this?

PS. We are doing the XOR comparison.

-

In long division, every time you successfully subtract a multiple of the divisor, that (single digit) multiplier goes in the quotient above the right hand digit of the multiple of the divisor. In binary, the multiplier is always $1$ since there is no other positive single digit.
If you cannot subtract a multiple of the divisor with a right hand digit in that place because the running remainder is too small, then you put $0$ in that place in the quotient.
There's no need for scare quotes here really -- what is going on is not long division of binary numbers, but long polynomial division of formal polynomials with coefficients in $\mathbb F_2$ (i.e., the integers modulo 2). We see only the coefficients because writing down the "$x^i+$" over and over would waste space without contributing information that is not inherent in the horizontal positions anyway. In polynomial division you subtract each coefficient by itself, without any carry between columns, and it so happens that subtraction modulo 2 is the same as XOR. –  Henning Makholm Feb 24 '12 at 23:57