Representing Integers in Binary
This is Part 2 in a three-part series about binary representations and bit shifting. Follow these links for Part 1 and Part 3.
We’re going to build upon material we talked about last time. If you have not read that one before, and especially if you are not familiar with counting in binary–then go back and read that post before reading this one. It will make a lot more sense if you do.
Binary (base-2) and other bases for number systems was mostly a mathematical toy until computers came along. Most people used the base-10 decimal system that we are all quite familiar with, and were happy.
Alas, in the very early days of computing, it became very clear that a computer would be way easier to make if every piece of hardware designed to store data could use two states instead of ten. Suddenly, what was a mathematical toy became essential to the computing world, because much that had been done in the binary number system could immediately be applied to the computing world.
If you only have two states to represent data in a computer–on and off or 1 and 0–then the binary system is a natural fit.
C# and virtually all other languages use the binary number system to represent integers in memory.
I’ll keep it simple here and look at only a single byte, but the concepts are identical if you’re using 2, 4, or 8 bytes. Those can just store much bigger numbers.
With any data type, you must come up with a way to represent the possible values using the bits that are reserved for values of the type.
The simplest example is the bool type, which really only needs to represent two values: true and false.
C# says, “false is assigned to the bit pattern 00000000 and true is assigned to the bit pattern 00000001. While we’ll generally only use 00000001 for true, if we somehow end up with any other bit pattern, such as 10000001, that will also be treated as true.”
Other data types are not as simple. Fortunately, all of the integer types work on similar principles.
For all of the integer types, it works like this. We assign the number 0 to be the bit pattern 00000000. The number 1 is the bit pattern 00000001. Then we proceed to count in base-2/binary. The number 2 is the bit pattern 00000010. The number 3 is the bit pattern 00000011. The number 4 is 00000100.
Representing Negative Values in Binary
So how do we represent negative values?
As we saw in the previous post, in the math world, we’d just slap a negative sign on the front. -101 is a valid negative base-2 number.
On a computer, however, we can’t set a bit to “negative”. We need some way to represent negative values using only zeroes and ones.
There are a lot of ways we could do this.
One simple way that is not used for integers is to just pick a single bit to be the sign bit. A 0 means positive and a 1 means negative. If we were to do this, then 00000001 would mean 1 while 10000001 would mean -1.
Floating-point types actually use this strategy, but integers do not.
Instead, integers use something much stranger. (I say “strange,” and it will be for a human. But it makes the circuitry in the hardware much simpler, which is why it is done this way.) Signed integer types will use a representation called two’s complement representation.
The highest positive number that 8 bits can store is the bit pattern 01111111, which is 127.
When you add one to this, the bit pattern does the normal thing and just rolls over to the next bit pattern, which would be 10000000.
But this number represents the largest negative number the type can represent: -128, in the case of 8 bits.
And basically, numbers just go up from there. The bit pattern 10000001 represents -127. The bit pattern 10000010 is -126, and so on, until you get to 11111101 which is -3, 11111110 which is -2, and 11111111, which is -1.
When you add one more to the bit pattern, you’ve overflowed the whole type and it gets reset back to the bit pattern of 00000000, which is 0 again.
A little weird, right?
But it does make sense from the perspective of designing and building CPUs, so it is what virtually every programming langauge anywhere uses, despite the weirdness.
At any rate, all of the integer types use this general pattern. Signed types will use two’s complement to represent negative values, while unsigned types will just use that bit on the big end to represent one more place value.
Floating-point types use a very different scheme that we will save for another day.
Click here to go on to Part 3 and learn about why bit shifting works the way it does.