Wednesday, October 17, 2018

Representation of Integers


Few basic things to know


  • Most Significant Bit (MSB) also called as Most Significant Digit (MSD). This is indeed the first digit (from left) in a binary number. More accurately the digit with the highest radix (base) value.
  • Least Significant Bit (LSB) or Least Significant Digit (LSD). This is the digit of a binary number with the least radix value, probably the last digit.
  • In binary number one digit is called as a bit.
  • Computer memory is a place that store data and it has a fixed length of bits. Generally 8bit, 16bit, 32bit and 64bit in length.










Data Representation

  • Computer uses a fixed number of bits to represent a single piece of data. Generally computers use 8bit, 16bit, 32bit and 64bit in size of binary numbers to represent different type and size of data.
  • N-number of bit memory (location) can store 2n of different types of values.
  • For an example 8bit memory can store 256 of different data values.
  • 3bit memory can store 8 distinct values (patterns) 000, 001, 010, 011, 100, 101, 110, or 111

  • When we interpret these values, we need to know exactly what represent with these values.
  • If we know that these represent decimal numbers, then we know it is from 0-7 then it is a different value.
  • So this interpretation of a binary pattern called data representation or encoding.

Integer Representation

Integers are whole numbers or fixed point numbers. The radix point is fixed after the LSB.

Example: 3774 is a fixed point number (integer)
2949.94 is a floating point number (real number)

qIn a computer integers and floating point numbers are treated differently and processed separately. Floating point numbers are processed in a separate processor called floating point processor.
qComputers use fixed number of bits to represent integers. Commonly use bit lengths are 8bit, 16bit, 32bit and 64bit.
qThere are two types of integers
qUnsigned integers: can represent zero and positive numbers only
qSigned integers: can represent zero, positive and negative numbers.
q
qThere are three schemas (ways) to represent signed integers.
qSign Magnitude representation
q1’s complement representation
q2’s complement representation


qWe learned about two different types of Integers;
qUnsigned Integers – that can represent only zero and positive numbers. The value of an unsigned integer interpreted as the “magnitude of underlying binary pattern or the normal way we convert binary to decimal.
q
Example: 8bit binary number 0100 0010B (B = Binary)
0100 0010B = 2x21 + 2x26 = 4+64 = 68D (D = Decimal)
8bit   = 0000 0000
16bit = 0000 0000 0000 0000
32bit = 0000 0000 0000 0000 0000 0000 0000 0000
64bit = 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000
All above numbers represent zero in different bit systems. The bit length of each system is different.


n-bit Unsigned Integers

qAn n-bit pattern can represent 2n distinct integers. This range from 0 to (2n)-1


When you are programming you need to select the correct and appropriate bit size to store integers. If you want to store small numbers less than 255, you can select 8bit number, selecting 32bit length to store small numbers is a waste of resources.


Signed Integers

qSigned integers can represent zero, positive and negative numbers.
qThe MSB (Most Significant Bit) – Normally the first bit from left, represent the sign of the integer. Zero (0) to represent positive (+) sign and One (1) to represent negative (-) sign.
qThe magnitude of the integer represent differently in different schemas.
qThere are three schemas to represent signed integers.

1.Sign Magnitude Representation
2.1’s Complement Representation
3.2’s Complement Representation


Example of Signed Integers:
  +2344 is a positive integer  -23434 is a negative integer


n-bit Sign Magnitude Representation

qMost Significant Bit (MSB) is the sign bit. 0 representing positive and 1 representing negative signs.
qThe remaining (n-1) bits represent the magnitude / absolute value of the integer interpreted according to its binary pattern.


Examples:
n=8 (8bit number) and binary number is 01000001
Sign bit (MSB) is 0 à this is a positive number
Absolute value 1000001 à 65
01000001B = +65D
B = Binary, D = Decimal

Examples:
n=8 (8bit number) and binary number is 00000000
Sign bit (MSB) is 0 à this is a positive number
Absolute value 0000000 à 0
00000000B = +0D
n=8 (8bit number) and binary number is 10000000
Sign bit (MSB) is 1 à this is a negative number
Absolute value 0000000 à 0
10000000B = -0D

Problems (Drawbacks / Limitations) of Sign Magnitude Representation:
qThere are two representation for the number zero
qEven the number zero need to have a sign, since it is not necessary nor accurate and may leads to confusions.
qPositive and negative numbers need to process separately.



n-bit 1’s Complement Representation


In this representation, the MSB is the sign bit 0 represent positive and 1 represent negative numbers. The remaining n-1 bits represent the magnitude (value) of the integer.
qIn positive integers, the value of the integer is the binary pattern (value) of the n-1 bit magnitude. Same as Sign Magnitude Representation.
qFor negative integers, the absolute value is the n-1 binary pattern value of the inverse magnitude (complement).


Example: 1 000 0001B (sign bit = 1, negative integer)
Complement of 000 0001 is 111 1110 = 126D
1 000 0001B = -126D
In the 1’s Complement Representation, there are two different representation for zero;

0000 0000B and 1111 1111B hence +0 and -0

Since the processing method of positive and negative integers are different, computer need to process the positive and negative numbers separately.


n-bit 2’s Complement Representation

In 2’s Complement Representation also the MSB is the sign bit 0 represent positive and 1 represent negative integers.

For positive integers, the value of the integer equal to the magnitude of n-1 binary pattern

For negative integers, the absolute value of the integer equal to the magnitude of the complement of n-1 binary pattern plus one.

Example: 1 000 0001B (MSB = 1 is a negative number)
Complement of 000 0001 = 111 1110
Let’s add 1 to the complement = 111 1111 = 127
1 000 0001B = -127D
Advantages of 2’s Complement Representation

qThere is only one representation for the number 0
qIn binary addition and subtraction, both positive and negative numbers can treated together (process together)
qSubtraction can use the addition logic
qComputers use 2’s Complement Representation for processing integers.



Addition, Subtraction, Overflow and Underflow

Addition of positive integers

Example: n=8, 65D + 5D = 70D

65D   à   0100 0001B
5D   à   0000 0101B
65D + 5D   à  0100 0110B OK 70D within the range of -128 to +127

Subtraction is the addition of positive and negative integers

Example: n=8, 65D – 5D = 60D à 65D + (-5D)

65D   à   0100 0001B
-5D   à   1111 1011B
65D + (-5D)   à  0011 1100B à 60D OK within the range of -128 to +127
Overflow and underflow happens when the result is not within the acceptable range

Example of Overflow: n=8, 127D + D = 129D (not within -128 and +127, exceed maximum value)

127D   à   0111 1111B
2D   à   0000 0010B
127D + 2D   à  1000 0001B à -127D wrong answer

Example of underflow: n=8, -125D – 5D = -130D (not within -128 and +127, below the minimum value)

-125D   à   1000 0011B
-5D   à   1111 1011B
-125D + (-5D)   à  0111 1110B à +126D wrong answer

Range of n-bit 2’s complement signed integers

An n-bit 2’s complement integer can represent integers from -2(n-1) to +2(n-1)-1. This can represent all the integers within the range without missing any integers.

8bit from -128 to +127
16bit from -32,768 to +32,767
32bit from -2,147,483,648 to + 2,147,483,647
64bit from -9,223,372,036,854,775,888 to + 9,223,372,036,854,775,887

Decoding 2’s complement numbers

Check the sign bit first. If sign bit = 0, the number is positive and the absolute value if the binary value of remaining n-1 integers.
If the sign bit = 1, the integer is negative. To get the absolute value;
Invert remaining n-1 bits and add 1 or
Scan from left until the first occurrence of 1. Flip all values from that point to the left. Binary value of this pattern gives the absolute value of the negative integer.


Example:
N=8 bit pattern = 1 100 0100 B
Negative number
Scan from right, until the first occurrence of 1, flip all values from that point to left
011 1100 B = 60 D
Represented negative value is -60 D

Big Endian vs. Little Endian

Modern computers store one byte of memory in single memory location / address. 1 byte = 8 bits. Therefore in 32bit integer stores in 4 memory locations.

Term “Endian” means the order of storing bytes in memory. In Big Endian standard – the most significant byte stores first in the lowest memory location. In Little Endian standard, the least significant byte (LSB) stores in the lowest memory location.

Floating Point Number Representation

A floating point number (also called as a real number) is a number with a decimal point. A floating point number can represent a very large positive or negative number as well as a very small negative or positive number. A real number has a range of -1.23x1088 to 1.25x1088 including zero.

Scientifically a floating point number represent as a number with a fraction and exponent of a certain radix.  F x rE
Same floating point number can represent in different ways. Consider 5.456D

We can represent this number in following ways:

54.532 x 100
5.4532 x 101
0.54532 x 102 and so on….

Since there are many ways to represent the same floating point number, we need to define a standard, so every floating point number should be in this standard. To make it standard, we can normalized the fraction part. In normalized form, there is only single none zero digit represent before the radix point. In above example 5.4532 x 101 is the normalized form of 54.532 number.
In computers, there is an issue of “Loss of Precision” in storing floating point numbers. An n-bit system can only stores 2n distinct finite numbers. Even within a small range 0.00 – 0.01, there are infinite number of decimal numbers. But the number of bits in a computer system is limited, only a the approximate number used, resulting in loss of accuracy.

Processing of a real number (floating number arithmetic) is very much less efficient and slower than processing of integers. In computers, real numbers uses fraction (F) and exponent (E) with radix (r) of 2. Both F and E can be negative or positive. In modern computing uses IEEE 754 standard to represent floating point numbers. There are two representation schemes

32 bit single precision and
64 bit double precision

IEEE-754 32-bit Single-Precision Floating-Point Numbers

In 32-bit single precision floating point number representation, decimal number represent in following structure:

The most significant bit is the sign bit. Zero for positive numbers and One for negative numbers.
Next following 8bit represent the exponent (E)
Remaining 23bit represent the fraction (F)

You may wonder why radix (r) is not represent here. Because radix is always 2 for binary numbers (in computers).

IEEE-754 64-bit Double-Precision Floating-Point Numbers


64-bit double precision floating point number representation is similar to 32-bit single precision floating point number representation. Only difference is assignment of bit range for exponent and fraction.

The most significant bit is the sign bit. Zero for positive numbers and One for negative numbers.
Next following 11-bit represent the exponent (E)
Remaining 52-bit represent the fraction (F)

Character Encoding

In computer memory, characters are represented (encode) using character schemes called as “character set”, “charset”, “character map” or “code page”. There are several standard schemes such as ASCII, EBCDIC, UTF, etc.

7-bit ASCII Code (aka US-ASCII, ISO/IEC 646, ITU-T T.50)
ASCII (American Standard Code for Information Interchange) is one of the earlier character coding schemes.
ASCII is originally a 7-bit code. It has been extended to 8-bit to better utilize the 8-bit computer memory organization. (The 8th-bit was originally used for parity check in the early computers). This is called ASCII-8 Code.

EBCDIC Code
This is stands for “Extended Binary Code Decimal Interchange Code”. This is a 8-bit code scheme without parity. With this up to 256 characters can be coded.
Unicode (aka ISO/IEC 10646 Universal Character Set)
Before Unicode, no single character encoding scheme could represent characters in all languages.
Unicode aims to provide a standard character encoding scheme, which is universal, efficient, uniform and unambiguous. Unicode standard is maintained by a non-profit organization called the Unicode Consortium (@ www.unicode.org). Unicode is an ISO/IEC standard 10646.
Unicode is backward compatible with the 7-bit US-ASCII and 8-bit Latin-1 (ISO-8859-1). That is, the first 128 characters are the same as US-ASCII; and the first 256 characters are the same as Latin-1.
Unicode originally uses 16 bits , which can represent up to 65,536 characters.

You can download this presentation on slideshare.



No comments:

Post a Comment

Important Notice!

Dear students and friends. When you commenting please do not mention your email address. Because your email address will be publicly available and visible to all. Soon, it will start sending tons of spams because email crawlers can extract your email from feed text.

To contact me directly regarding any inquiry you may send an email to info@bcslectures.website and I will reply accordingly.