binary long division

[find_the_fun]

binary long division - updated with actual example

Basically what I'm asking is when is a digit in the quotient 0?


This is from an exercise where I'm supposed to fill in the boxes. I don't understand how they completed the parts that are given to me. Why is the first number 1 when 1111>1010

 

[Evgeny.Makarov]

You are right; this is strange. I think division should like like this.

         1011011
    ------------
1111)10101011000
      1111
     -----
       1100
          0
       ----
       11001
        1111
       -----
        10101
         1111
          ---
          1100
             0
          ----
          11000
           1111
          -----
           10010
            1111
            ----
              11

 

[find_the_fun]

I guess it was a mistake. I'll let you know if I find any others like it.

 

[find_the_fun]

Actually this isn't long division in binary, it's a special type of division used to compute the CRC of a message. The divisor goes into the numerator iff they have the same length e.g. 111 divides 101 once but 111 divides 011 zero times (because 011 is 2 digits long which is less than the 3 digits of 111). Instead of subtracting xor is used. So the second digit in the quotient in the above example would be 0. Apparently this is faster for computers to do than real long division.

I'm not sure if this is describing the same concept but here's a >>wikipedia article<< on the math of CRC.

For anyone less mathematically inclined >>this webpage<< does a good job at explaining it.