Modulo 2 binary division (XOR not subtracting) method

enter image description here

I have attached an image showing a Modulo 2 binary division.

I can roughly understand the working below which is using XOR calculation but I am not sure how the answer (in red) is being computed based on the workings.

I have searched the net and couldn't find any good step by step guide to solve this binary long division.

Hope someone can enlighten me.


Solution 1:

Each bit is the highest order bit of what remains so far, right shifted by four places because the dividend has highest term $2^4$. So the first bit is $1$ (as always). Because the first subtraction results in a $0$ in the next column, the second bit of the quotient is $0$. It is just like base $10$ division, if you get a zero in the next column over you put a zero in the quotient and skip it. Try dividing $\frac {100100}{99}$

Solution 2:

First of all, this is XOR not subtraction. Similar bits being XOR'ed always equal 0, different bits (no matter the order) in an XOR always equal 1. 0 XOR 0 = 0, 1 XOR 1 = 0, 1 XOR 0 = 1, 0 XOR 1 = 1. Once you have grasped this firmly, it makes the math easier and behaves very similarly to traditional long division as far as having leading zero's in the dividend, put a 0 in the quotient and shift the divisor over one.

A 1 is placed above the 5th bit like in regular long division to mark the place of the last character of the Divisor. If we follow the bits in order the first part is 11100 XOR 11011 Bit1 1 XOR 1 = 0 Bit2 1 XOR 1 = 0 Bit3 1 XOR 0 = 1 Bit4 0 XOR 1 = 1 Bit5 0 XOR 1 = 1

This gives you a remainder of 0111. Since there is a leading 0 in the dividend the divisor gets shifted over again and a 0 is placed above the 6th bit.

This process is repeated until the divisor's last bit is in line with the dividend's last bit. If there is a leading 0 in the dividend place a 0 over the last bit in the dividend, if there is not a leading 0, place a 1 and do the math.

Important to note: once the last XOR math has been calculated, the remainder is your Modulo.