Understanding Binary Long Division: Finding Zero Quotient Digits

[find_the_fun]

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

 

[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.

 

[blue_raver22]

In binary long division, a digit in the quotient is 0 when the corresponding digit in the dividend is smaller than the divisor. In other words, when performing binary long division, we are essentially subtracting the divisor from the dividend until we reach a remainder that is smaller than the divisor. This remainder then becomes the next digit in the quotient.

In your example, the first number is 1 because 1111 is larger than 1010. This means that the first digit in the quotient must be a 1, as we need to subtract the divisor (1010) from the dividend (1111) to get a remainder. The remainder in this case is 101, which is still larger than the divisor, so we continue with the next step of division. This process continues until we reach a remainder that is smaller than the divisor, at which point we can no longer subtract and the division is complete.

To better understand this concept, let's look at an actual example:

Dividend: 1101
Divisor: 101

First step: 1101 - 101 = 1000
Since 1000 is still larger than the divisor, the first digit in the quotient is 1.

Second step: 1000 - 101 = 0111
Again, 0111 is still larger than the divisor, so the second digit in the quotient is also 1.

Third step: 0111 - 101 = 0100
This time, the remainder (0100) is smaller than the divisor (101), so the third digit in the quotient is 0.

Final step: Since the remainder is now smaller than the divisor, we can no longer subtract and the division is complete. The final quotient is 110, with a remainder of 0100.

I hope this helps clarify the concept of finding zero quotient digits in binary long division. Just remember, a digit in the quotient is 0 when the corresponding digit in the dividend is smaller than the divisor.