Saw this on reddit, good quality tutorial.

  • mrkite@programming.dev
    link
    fedilink
    English
    arrow-up
    2
    ·
    1 year ago

    As comprehensive as that is, they don’t explain why we use 2’s complement for negatives, and that’s a shame because it’s a really intuitive answer when it’s explained.

    For the following, pretend we’re dealing with 4-bit numbers… 0000 to 1111. Just to keep the examples sane.

    With 4 bits, we can represent 0 to 15… but let’s add negative the dumbest way possible. Just make the high bit negative, so 0000b-0111b is 0 to 7, and 1000b-1111b is -0 to -7. We have 0 and negative 0, which is weird but let’s ignore that for now. Does this system even work with basic arithmetic? Let’s do a sanity check. If we have a negative number and add 1 to it, it should get closer to 0. -4 + 1 = 1100b plus 0001b = 1101b or -5. That’s the opposite of what we want.

    So to fix our problem we just need to reverse the order of the negative numbers. We can easily do that by inverting all the bits. 0000b-0111b is still 0 to 7, but now 1000b-1111b is -7 to -0. Does the math work? Let’s see: -4 + 1 = 1011b plus 0001b = 1100b or -3! It works!

    You’ll find ones-complement actually works quite well for arithmetic. So why don’t we use it? You’ll recall we ignored the fact that there is a positive and a negative zero. Let’s address that now. The two zeros means comparisons are a pain. 0 != -0 without a bunch of extra logic.

    It’s a simple fix. What if we shift the negative number line over so the two zeros are the same? Simply add 1 to the number after inverting. 1111b (which was previously -0 in 1s complement) rolls over to become 0000b, which is 0! 1110b (-2 in 1s complement) becomes 1111b and we’ll call it -1, and so on. It even gives us an extra number because 1000b represents -8, which we couldn’t represent in 1s complement.

    And that’s why we use 2s complement, and now you’ll always remember why and how it works.