How integers are stored in memory using two’s complement
An integer is a number with no fractional part; it can be positive, negative or zero. In ordinary usage, one uses a minus sign to designate a negative integer. However, a computer can only store information in bits, which can only have the values zero or one. So how do we store negative integers in a computer then?
Integer data types in C are typically 1, 2, 4 or 8 bytes in length, or 8, 16, 32, or 64 bits in length.
Integer types can be:
- Unsigned: that can store values from 0 to 2^n -1, as simple binary numbers
- Signed: that can store values from -(2^(n-1)) to 2^(n-1), as two’s complement binary format. Values greater than or equal to zer0 are stored with same bit values as unsigned numbers.
n is number of bits in the machine
Compiler differentiates between positive and negative number from sign bit. MSB (most significant bit) is a sign bit. If it is zero it means the number is positive. If it is 1 means the number is negative. Compiler first takes its 2 complement and then displays the number with negative sign. If 32 bits are there to store number then maximum value you can store in it is ( 2³¹)-1 which takes 31 bits in its representation. It means MSB is always zero for positive number. If all the bits are 1s the number is -1.
Decoding 2’s Complement Numbers
For positive values, if the leftmost (sign) bit is zero, the value is positive so simply do a binary to decimal conversion.
This example was run on 64-bit machine so there are about 57 zeros before this number so number is positive and the rest we calculate right to left as powers of two starting at zero and then multiplied by the bit at that power.
So going right to left we have;
0*2⁰ + 0*2¹ + 1*2² + 0*2³ + 1*2⁴ + 0*2⁵ + 1*2⁶
= 0 + 0 + 4 + 0 + 16 + 0 + 64 = 84
There are three steps necessary to convert a negative decimal integer to two’s complement form:
- Start with the positive binary value, expanded to fill the number of bits you will be storing the number into.
- Complement/flip all of the bits. This means all of the 1s become 0s and all of the 0s become 1s
- Add one to the flipped bits.
Let’s use -84 since we already used it above.
Step 1. 84 = 0…000…0001010100
Step 2. 1…111…1110101011
Step 3. add 1 so we get 1…111…1110101100
So we have 1…111…1110101100 just like in screenshot above
Interesting consequence in 2’s complement arithmetic
In unsigned arithmetic a carry of the most significant digit means that there has been an overflow, but in signed arithmetic an overflow is not so easy to detect. In fact, signed arithmetic overflows are detected by checking the consistency of the signs of the operands and the final answer.
A signed overflow can occur in an addition or subtraction if:
- the sum of two positive numbers is negative;
- the sum of two negative numbers is non-negative;
- subtracting a positive number from a negative one yields a positive result;
- subtracting a negative number from a non-negative one yields a negative result.
The CPU doesn’t know if a number is signed or unsigned when it moves it from one place to another. When the compiler creates the machine language file, it chooses the correct operation to be executed to make a math operation with that number. If you declared your variable to be of the signed type, for instance, than the operation to be executed in machine language will be one that treats that memory position as a signed value.
In any software of any kind, it is always when you interpret the data that you give it meaning. A byte in memory can be a signed or unsigned number, or a character, or a part of a music file, or a pixel in a picture, etc. What gives it meaning is how you use that byte.
So in summary the number is only signed or unsigned based on your interpretation of it, the CPU gives you the tools necessary to distinguish between them, but doesn’t distinguish on its own.