2's COMPLEMENT

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, a minus sign is used to designate a negative integer. However, a computer can only store information in bits, which can only have the values zero or one.

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

virtual memory addresses available per process for unsigned integers

• 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.

virtual memory addresses available per process for signed integers

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.

Example:

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:

1. Start with the positive binary value, expanded to fill the number of bits you will be storing the number into.
2. Complement/flip all of the bits. This means all of the 1s become 0s and all of the 0s become 1s
3. Add one to the flipped bits.

Example:

Let’s use -84 .

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;

sum of two positive numbers is negative

• the sum of two negative numbers is non-negative;

sum of two negative numbers is non-negative

• subtracting a positive number from a negative one yields a positive result;

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.

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.