MHB Understanding Binary Long Division: Finding Zero Quotient Digits

  • Thread starter Thread starter find_the_fun
  • Start date Start date
  • Tags Tags
    Binary Division
AI Thread Summary
In binary long division, a quotient digit is 0 when the divisor cannot fit into the current portion of the dividend, typically when the length of the dividend segment is shorter than the divisor. The example provided illustrates that the first number in the quotient is 1 because the divisor, 1111, fits into the first part of the dividend, 10101. The process differs from traditional long division, as it uses XOR instead of subtraction, particularly in CRC calculations. This method is faster for computers and is designed for specific applications like error-checking in data transmission. Understanding these principles is crucial for correctly completing binary division exercises.
find_the_fun
Messages
147
Reaction score
0
binary long division - updated with actual example

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

View attachment 356
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
 

Attachments

  • dontunderstand.png
    dontunderstand.png
    2.3 KB · Views: 101
Last edited:
Physics news on Phys.org
You are right; this is strange. I think division should like like this.

Code:
         1011011
    ------------
1111)10101011000
      1111
     -----
       1100
          0
       ----
       11001
        1111
       -----
        10101
         1111
          ---
          1100
             0
          ----
          11000
           1111
          -----
           10010
            1111
            ----
              11
 
I guess it was a mistake. I'll let you know if I find any others like it.
 
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.
 
Last edited:
Back
Top