Storage and Integers! And how!
A blog for personal edification via Holberton Curriculum.
On today’s show we cover how integers are stored in memory using two’s complement. Deep breath. This is a heavy math one.
Two’s complement is a mathematical operation on binary numbers and is an example of a radix complement. The two’s complement of an n-bit number is defined as its complement in respect to 2^n. For instance: the three-bit number 010. The two’s complement is 110 because 010(2 in decimal)+ 110(6 in decimal)= 8, which is 2³. This allows numbers to be stored, for instance in RAM, using the methods shown below.
In mathematics, the “method of complements” is a technique to encode a symmetric range of positive and negative integers in a way that they can use the same algorithm for addition throughout the whole range. For a given number of places, half of the possible representations of numbers encode the positive numbers. The other half represents their respective additive inverses. The pairs of mutually additive inverse numbers are called complements. Thus subtraction of any number is implemented by adding its complement.
The gcc (currently standard) compiler differentiates between positive and negative numbers from the sign bit. An ‘int’ is actually 1 sign bit plus 31 data bits. This means 31 bits are available for storing the number being assigned to a ‘int’ type variable and 1 bit is reserved for maintaining the sign of the number. The sign is also represented by binary digits: 0 for positive, 1 for negative. In the case of a 1 the compiler first clarifies its 2 complement and then displays the number with a negative sign. Not anything weird though. Just “-”
In the case of a 0, the number is positive.
A positive output will be as simple as translating from binary to decimal. It’s definitely simpler in practice than reading a math book.
Each position from right to left is the last position times two. The ones are on switches and the zeroes are off. You only count the on switches. Add at the end.
How to apply two’s complement to a negative number:
- Expand the positive number to fill the number of bits you need for output.
- Invert the numbers by flipping all the switches(zeroes and ones) on or off.
- Add one to the flipped bits.
The process of negatives by example breakdown:
- 6 = 000110 (This math functions no matter how many bits you have. The inverse is based on the total including all digits.)
- flip: 111001
- add 1: 111010
we end up with this final number for the same reason you move digits around in base 10. Adding 1 to 1 creates a 2. So you just append the round up as a 1 in the next slot. Repeat as necessary.
The reason why this works is that flipping bits is equivalent to subtracting the number from (2^n — 1). We actually need to subtract the number from 2^n, and step 3 compensates for that — 1.
There is a small difference between signed and unsigned calculations: detection of overflow.
In 3 bit arithmetic, the multiplication –1 * –2 -> 2 produces the correct answer. But, the equivalent unsigned multiplication 7 * 6->2 produces an answer that is only correct in modular arithmetic, not “actually” correct.
Unsigned carry (can’t believe these integers won’t get a license. That’s felonous) of the sign bit (AKA the most significant bit) indicates there has been an overflow. But with signed integers, it’s not so simple. It can usually be detected by the final output and the consistency of the operands.
All of that will come with later updates. For now, I think I’ve covered enough of my bases. And I’ve had quite a lot of “fun” simplifying what honestly was an incredibly long and arduous trek down Mathematical-Spiral Lane in the city of Smoothsbrain, OH.