CS 101:

(1)

CS 101:

Computer Programming and Utilization

Puru

with

CS101 TAs and Staff

Course webpage: https://www.cse.iitb.ac.in/~cs101/

Lecture 8: Number representation

(2)

Number representation and

variables

(3)

why numbers?

• problem solving using computers is about problem solving on numbers

• examples

– salaries, temperature, length, distance, voltage …

– picture, language, characters, …

(4)

data types of C++

• char: used for storing characters or small integers

− 1 byte will be allocated

− ASCII code of characters is stored

• float: used for storing real numbers

− 1 word will be allocated (4 bytes)

− IEEE FP representation, 8 bits exponent, 24 bits significant

• double: used for storing real numbers

− 2 words will be allocated (8 bytes)

− IEEE FP representation, 11 bits exponent, 53 bits significant

• int : used for storing integers

data_type_name variable_name;

(5)

variable declaration

0 1 2 3 4 5 6 7 8 9

...

32 bits

int sides;

Results in a memory location being reserved for this variable. The

(6)

How are all these types represented in memory/storage as bits?

How are operations on all these types

performed in terms of bits?

(7)

radix-based number systems

• Number systems with radix r has r symbols (including 0)

• (x)_r x is a string of symbols, r is the radix/base

• (100)₁₀, (100) ₂, (100) ₈, (500) ₈, (100) ₁₆, (ab)₁₆

• key idea: position of a symbol determines it's value!

PLACE VALUE

– Multiply from right to left by: r⁰, r¹, r², r³_,... and then add

(8)

decimal number system

• RADIX is 10

SYMBOLS: 0, 1, 2, 3, 4, 5, 6, 7, 8, 9

• Place-Values (as we move from right to left):

1, 10,100,1000...

• In the decimal system: 346

− Value of "6" = 6

− Value of "4" = 4 x 10

− Value of "3" = 3 x 10 x 10

(9)

hexadecimal number system

• RADIX is 16. Place Values: 1, 16, 256, 4096, …

• 16 digits (symbols)s: 0,1,2,3,4,5,6,7,8,9,a,b,c,d,e,f

• 23 in hexadecimal – Value of 3 = 3

– Value of 2 = 2 x 16

– Value of 23 in hexadecimal = 35 in decimal

• abc = 10*256+11*16+12*1 = 2748 in decimal

• 45171 in hexadecimal =

– 1 + 16*7 + 16*16*1 + 16*16*16*5 + 16*16*16*16*4

= 282993 in decimal

(10)

the binary system

128 64 32 16 8 4 2 1

• Radix is 2

• Needs ONLY digits : 0 and 1

• Place-values: powers of two

• 11 in binary:

– Value of rightmost 1 = 1 – Value of next 1 = 1 *2

– 11 in binary = 3 in decimal

• 1100101

(11)

binary system

circuits have wires that carry current, and are at a certain electric potential

digital circuits interpret electrical potential/voltage as numbers

simple convention

voltage above 5 volt = number 1

voltage between 0 and 0.2 volt = number 0 circuits designed so that voltage will never be

an inverter circuit

capacitors (like batteries) can store electrical charges

(12)

decimal to binary conversion

128 64 32 16 8 4 2 1

1 0 0 1 1 0 1 0

• Decimal to binary conversion

– Express it as a sum of powers of two

• Example: the number 154 in binary:

– 154 = 128 + 16 + 8 + 2

– 154 = 1 x 2⁷+ 0 x 2⁶+ 0 x 2⁵+ 1 x 2⁴+ 1 x 2³+0 x 2²+ 1 x 2¹+ 0 x 2⁰ – Thus, 154 in binary is 10011010

(13)

how large can the numbers be?

• the number of bits (capacitors/wires) used cannot be chosen arbitrarily

• choices allowed: 8, 16, 32, 64 (width in bits)

• example: To store 9 using 8 bits:

− 9 decimal = 0000 1001 binary

− so store the following charge pattern (H=High, L=Low)

− LLLLHLLH

• range of numbers that can be stored: 0 to 2⁸ – 1

If your numbers are likely to be larger, then use 16/32/64 bits

• choose the number of bits depending upon how large you expect the number to be.

(14)

limits of different data types

• 8 bits

• 16 bits

• 32 bits

– 4294967295

(15)

representing positive and negative integers

• the width (8/16/32/64) bits is fixed

• can represent/store 2ⁿ values in total

• how to handle positive and negative numbers?

(16)

representing positive and negative integers

• one of the bits is used to indicate sign

• sign bit = 0 means positive, = 1 means negative number

• to store -9 :

− 1000 1001, Leftmost bit = sign bit, Left with 7 bits for numbers

• range stored: -(2⁷ – 1) to 2⁷ – 1

(17)

representing positive and negative integers

• One of the bits is used to indicate sign

• Sign bit = 0 means positive, = 1 means negative number

• To store -9 use

− 10001001, Leftmost bit = sign bit, 7 bits for value

• Range stored: -(2⁷ – 1) to 2⁷ – 1

(18)

two’s complement representation

• For a n-bit number (numbers to be stored in n bits)

• If x is positive: (0 <= x <= 2^n-1 – 1)

– Binary form of x

• If x is negative ( -2^n-1 <= x < 0)

– Binary form of 2ⁿ + x

– E.g. -9 in 2's complement:

100000000 - 000001001 = 11110111 = 247 decimal – Can also be obtained by one’s complement + 1

(19)

representing non-negative numbers

• The number of bits (capacitors/wires) used cannot be chosen arbitrarily

• choices allowed: 8, 16, 32, 64

• example: To store 25 using 32 bits:

− 25 Decimal = 00000000000000000000000000011001

− So store the following charge pattern (H=High, L=Low)

− LLLLLLLLLLLLLLLLLLLLLLLLLLLHHLLH

• range stored: 0 to 2³² – 1. If your numbers are likely to be larger, then use 64 bits

• choose the number of bits depending upon how large you expect the number to be.

(20)

representing positive and negative integers

• To store -25 use

− 10000000000000000000000000011001, Leftmost bit = sign bit

• Range stored: -(2³¹ – 1) to 2³¹ – 1

(21)

representing positive and negative integers

• To store -25 use

− 10000000000000000000000000011001, Leftmost bit = sign bit

• Range stored: -(2³¹ – 1) to 2³¹ – 1

• Actual representation: Two’s complement

– If x is positive: (0 <= x <= 2^n-1 – 1)

• Binary form of x

– If x is negative ( -2^n-1 <= x < 0)

• Binary form of 2ⁿ + x

• E.g. -25 in 2's complement: 11111111111111111111111111111100111

= (100000000000000000000000000000000 -

(22)

the two’s complement wrap-around

(23)

the two’s complement wrap-around

Zero is one position to the right of center

-1=1…1 0=0…0 Max=01…1

Min=10…0

(24)

Boolean values and operations

x y x && y

0 0 0

0 1 0

1 0 0

1 1 1

• In C++, int can be reused as Boolean (0 = false,

anything else is true)

• Binary operator && (and)

x y x || y

0 0 0

0 1 1

1 0 1

1 1 1

(25)

Not and ex(clusive) or

Input x Output !x

0 1

1 0

• Unary operator ! (not)

• Binary operator exor is not available on single boolean values

• EXOR available on bit vectors (n-bit numbers)

x y x ^ y

0 0 0

0 1 1

1 0 1

1 1 0

(26)

The bool type

• Old C++ used int to store Boolean values

• But ANSI standard C++ offers a type called bool

• bool tval = true, fval = false;

• int ival = int(tval);

• However, old bad habits still allowed

– if (37) { … }

– bool bval = 37;

• Overall value unclear

(27)

Bit array manipulation

• Fixed size integers are arrays of bits

• C++ lets you do bitwise Boolean algebra

• a & b

(and),

^{a | b}

(or),

^{a^b}

(exor),

^~b

(not)

(28)

Bitwise operators

• a & b

(and),

^{a | b}

(or),

^{a^b}

(exor),

^~b

(not)

10110110 10010101 10010100

&

10110110 10010101 00100011

^

10110110 10010101

|

00100011 11011100

~

(29)

Left shift operator

• int c = 5; cout << (c << 2);

• Bits lost from the left (msb)

• Zero bits inserted from the right (lsb)

• Result is 20 (= 5 ´ 2

²

)

• Cheap way to multiply by powers of two

00000000,00000000,00000000,00010100

00000000,00000000,00000000,00000101

(30)

Right shift operator

• c >> 2

• Bits discarded to the right (lsb)

• If msb of c was 0, then 0 bits injected from left (msb)

– 5 >> 2 gives 1

• If msb of c was 1 (c was negative) then 1 bits injected from left

– -5 >> 2 gives -2 (work it out)

>> 2 gives 0xfffffffe

(31)

examples

• generate powers of 2 using shift operator

• outputs of …

int a = 1;

cout << a;

a = a << 31;

cout << a;

a = a >> 31;

cout << a;

(32)

Some applications of bit operations

• Is an int x odd or even?

• Remainder when divided by 8

• How many one bits in a 32-bit int?

(33)

Some applications of bit operations

• Is an int x odd or even?

– int isOdd = (x & 1);

• Remainder when divided by 8

– int remain = (x & 7);

– Faster than x % 8

• How many one bits in a 32-bit int?

• Repeat 32 times:

– numOnes = numOnes + (x & 0x8000000);

– x = x << 1;

In binary this looks like a one

(34)

fractions in binary

8 4 2 1 1/2 1/4 1/8 1/16

• powers on the right side of the point are negative:

• binary 0.1 = 0 + 1 x 2^-1 = 0.5 in decimal

• in binary 0.11 = 0x 1 + 1 x 2^-1+ 1 x 2^-2

= 0.5 + 0.25 = 0.75 in decimal

(35)

fractions and precision

• represent decimal number 1.45 using 3 bits and

4 bits

(36)

fractions and precision

• represent decimal number 1.45 using 3 bits and 4 bits

• with 3 bits: 1.11 => 1.375

• with 4 bits: 1.111 => 1.4375

• for actual storage as numbers all factions

converted to mantissa + exponent form

(37)

Representing floating point numbers

• Use an analogue of scientific notation:

• significand * 10^exponent, e.g. 6.022 * 10²²

• Significand (with a bit for sign) and exponent are in binary

• significand * 2^exponent

• Actual representation: more complex. “IEEE Floating Point Standard”

Costs how many bits to store

No of bits for mantissa

No of bits for exponent

float 32 24 8

double 64 52 12

(38)

Example

• Let us represent the number 3450 = 3.45 x 10³

• First: Convert to binary:

• 3450 = 2¹¹+ 2¹⁰+ 2⁸+ 2⁶+ 2⁵+2⁴+2³+ 2¹

• Thus 3450 in binary = 110101111010

• 3450 in significand-exponent notation: how?

• 1.10101111010 x 2¹⁰¹¹

− 10 in binary is 2 in decimal

− 1011 in binary is 11 in decimal, we have to move the

"binary point" 11 places to the right

11 10 9 8 7 6 5 4 3 2 1 0

1 1 0 1 0 1 1 1 1 0 1 0

(39)

Example Continued

For computer representation:

• Use 23 bits for magnitude of significand, 1 bit for sign

• Use 7 bits for magnitude of exponent, 1 bit for sign 01101011110100000000000000001011

• Decimal point is assumed after 2^nd bit.

(40)

Different Needs, Different Variable Types

• The keyword long : says, I need to store bigger or more precise numbers, so give me more than usual space.

• long unsigned int: Likely 64 bits will be allocated

• long double: likely 96 bits

unsigned int

telephone_number;

float velocity;

float mass, acceleration;

long unsigned int crypto_password;

long double

more_precise_vaule;

(41)

Const Keyword

• const double pi = 3.14;

• The keyword const means : value assigned once cannot be changed

• Useful in readability of a program

• area = pi * radius * radius;

• reads better than

• area = 3.14 * radius * radius;

(42)