Modulo-2 Division Calculator
Divide binary strings using modulo-2 long division. See XOR subtraction, quotient generation, shifted divisor positions, intermediate remainders and the final modulo-2 remainder step by step.
| Step | Current Dividend | Degree Difference | Shifted Divisor | XOR Operation | New Remainder |
|---|---|---|---|---|---|
| Enter values and calculate to view modulo-2 division steps. | |||||
What Is Modulo-2 Division?
Modulo-2 division is a form of binary polynomial division where coefficients are calculated over GF(2). The arithmetic uses only 0 and 1, and subtraction is performed without borrowing.
Instead of ordinary binary subtraction, modulo-2 division uses XOR between the current dividend portion and an appropriately shifted divisor.
The process continues until the remaining polynomial has a lower degree than the divisor. The resulting values are the modulo-2 quotient and remainder.
Modulo-2 Arithmetic Rules
Modulo-2 Subtraction
0 – 1 = 1
1 – 0 = 1
1 – 1 = 0
These results are the same as XOR.
XOR Rules
0 XOR 1 = 1
1 XOR 0 = 1
1 XOR 1 = 0
How Modulo-2 Long Division Works
1. Compare Degrees
Compare the highest active bit position of the current dividend with the highest bit position of the divisor.
2. Shift the Divisor
Move the divisor left until its leading 1 aligns with the leading 1 of the current dividend.
3. XOR
XOR the shifted divisor with the current dividend instead of performing ordinary subtraction.
4. Repeat
Continue until the remainder degree becomes smaller than the divisor degree.
Modulo-2 Division Algorithm
While:
degree(Current) is at least degree(Divisor)
1. Find degree difference
2. Shift divisor left by that difference
3. Add the corresponding quotient term
4. XOR Current with shifted divisor
5. Use the XOR result as the new Current
When the loop ends:
Quotient = generated quotient bits
Remainder = Current
Worked Example: 1101 Divided by 101
1101
Divisor:
101
First align:
1010
1101 XOR 1010
= 0111
Normalize:
111
Next XOR:
111 XOR 101
= 010
Remainder:
10
Quotient:
11
The Same Example in Polynomial Form
= x^3 + x^2 + 1
101
= x^2 + 1
Quotient:
11
= x + 1
Remainder:
10
= x
Modulo-2 Remainder
The calculation stops when the degree of the current remainder becomes lower than the degree of the divisor.
< degree(Divisor)
Unlike ordinary integer division, this rule is based on polynomial degree rather than comparing the decimal numeric values of the bit strings.
How the Modulo-2 Quotient Is Generated
Each successful alignment of the divisor with the current leading dividend term contributes a 1 at the corresponding quotient position.
The quotient therefore records which shifted copies of the divisor were XORed from the dividend.
Modulo-2 Division and CRC Calculations
Modulo-2 division is a core mathematical operation used in cyclic redundancy check systems. In a CRC calculation, a data bit string is typically processed using a generator polynomial represented as a binary divisor.
The resulting polynomial remainder can be used as a check value. This calculator focuses on the underlying modulo-2 division itself rather than implementing a particular CRC standard.
Modulo-2 Division vs Ordinary Binary Division
| Feature | Ordinary Binary Division | Modulo-2 Division |
|---|---|---|
| Interpretation | Binary integers | GF(2) polynomials |
| Subtraction | Uses borrow rules | Uses XOR |
| Carry / borrow | May occur | Never used |
| Stopping rule | Remainder smaller numerically | Remainder degree lower than divisor |
| Common use | Integer arithmetic | Polynomial and CRC mathematics |
Why XOR Replaces Subtraction
In GF(2), every coefficient is either zero or one and calculations are reduced modulo 2. As a result, addition and subtraction produce the same coefficient table.
1 – 0 = 1
0 – 1 = 1
0 – 0 = 0
This is identical to XOR.
Modulo-2 Division Examples
| Dividend | Divisor | Quotient | Remainder |
|---|---|---|---|
| 101 | 11 | 11 | 0 |
| 111 | 101 | 1 | 10 |
| 1101 | 101 | 11 | 10 |
| 1011 | 11 | 110 | 1 |
| 10011 | 101 | 101 | 10 |
Do Leading Zeros Affect Modulo-2 Division?
Leading zeros do not change a polynomial coefficient pattern, so the calculator removes unnecessary leading zeros before performing division.
and
1101
represent the same normalized polynomial coefficient sequence.
Important Modulo-2 Division Notes
The divisor must contain at least one 1 and the normalized divisor should begin with 1.
Modulo-2 subtraction uses XOR and requires no borrowing.
The final remainder is valid when its polynomial degree is lower than the divisor degree.
A zero dividend produces quotient 0 and remainder 0.
Division by the zero polynomial is undefined.
This tool demonstrates the division operation used in CRC mathematics, but it does not automatically append CRC zeros or implement any particular CRC standard.