1. Limited time only! Sign up for a free 30min personal tutor trial with Chegg Tutors
    Dismiss Notice
Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Homework Help: Modulo 2 long division

  1. Mar 20, 2013 #1
    Hello, I am trying to understand the following modulo 2 long division.
    I understand that 1101 goes into 1111, so you write a 1 on the top.
    The next stage after 'XOR'ing is to bring down the 1.
    Now, 1101 does not go into 101, so you write a 0 at the top. So far so so good.
    Now you bring down another 1 and 1101 still does not go into 1011, so how come they wrote a 1 in the third position at the top ? Shouldn't that be a zero ?

    If someone could please explain where I am going wrong, I would most grateful.
    1. The problem statement, all variables and given/known data

    2. Relevant equations

    3. The attempt at a solution

    Attached Files:

    • difv.jpg
      File size:
      40.9 KB
  2. jcsd
  3. Mar 20, 2013 #2


    User Avatar
    Homework Helper

    Since modulo 2 math uses xor instead of add or subtract, then only the most sigificant bit of the divisor and current remainder / dividend matter, so 1101 "goes into" 1011 because you're using xor, not subtract. The goal during the division process is to zero out the most significant bit(s) of the current remainder / dividend.

    Consider what would happen if you didn't treat 1101 as "going into" 1011, you'd be stuck with a 5 bit number (10110) and since there are no borrows when doing xor, you would never be able to clear that uppermost bit left in the remainder with an xor of 10110 and 1101.

    Another way to look at these numbers is to consider them to be polynomials with 1 bit finite field (modulo 2) coefficients. This would mean that

    1101 = 1 x3 + 1 x2 + 0 x + 1
    1011 = 1 x3 + 0 x2 + 1 x + 1

    So when doing modulo 2 division, then 1101 goes into any number where the x^3 coefficient is a 1.
    Last edited: Mar 20, 2013
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook

Have something to add?
Draft saved Draft deleted