2
Demystifying bitwise operations, a gentle C tutorial
(www.andreinc.net)
Welcome to the C community!
C is quirky, flawed, and an enormous success.
... When I read commentary about suggestions for where C should go, I often think back and give thanks that it wasn't developed under the advice of a worldwide crowd.
... The only way to learn a new programming language is by writing programs in it.
🌐 https://en.cppreference.com/w/c
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.