WIXLIB

Number SystemsandNumber Representation1

For Your AmusementQuestion: Why do computer programmers confuseChristmas and Halloween?Answer: Because 25 Dec 31 Oct-- http://www.electronicsweekly.com2

Goals of this LectureHelp you learn (or refresh your memory) about: The binary, hexadecimal, and octal number systemsFinite representation of unsigned integersFinite representation of signed integersFinite representation of rational numbers (if time)Why? A power programmer must know number systems and datarepresentation to fully understand C’s primitive data typesPrimitive values andthe operations on them3

AgendaNumber SystemsFinite representation of unsigned integersFinite representation of signed integersFinite representation of rational numbers (if time)4

The Decimal Number SystemName “decem” (Latin) tenCharacteristics Ten symbols 0 1 2 3 4 5 6 7 8 9 Positional 2945 2495 2945 (2*103) (9*102) (4*101) (5*100)(Most) people use the decimal number systemWhy?5

The Binary Number SystemName “binarius” (Latin) twoCharacteristics Two symbols 0 1 Positional 1010B 1100BMost (digital) computers use the binary number systemWhy?Terminology Bit: a binary digit Byte: (typically) 8 bits6

Decimal-Binary EquivalenceDecimal 1011121100131101141110151111Decimal Binary16 1000017 1000118 1001019 1001120 1010021 1010122 1011023 1011124 1100025 1100126 1101027 1101128 1110029 1110130 1111031 11111.7

Decimal-Binary ConversionBinary to decimal: expand using positional notation100101B (1*25) (0*24) (0*23) (1*22) (0*21) (1*20) 32 0 0 4 0 1 378

Decimal-Binary ConversionDecimal to binary: do the reverse Determine largest power of 2 number; write template37 (?*25) (?*24) (?*23) (?*22) (?*21) (?*20) Fill in template37 (1*25) (0*24) (0*23) (1*22) (0*21) (1*20)-325-41100101B-109

Decimal-Binary ConversionDecimal to binary shortcut Repeatedly divide by 2, consider remainder37189421//////222222 18 R 1 9 R 0 4 R 1 2 R 0 1 R 0 0 R 1Read from bottomto top: 100101B10

The Hexadecimal Number SystemName “hexa” (Greek) six “decem” (Latin) tenCharacteristics Sixteen symbols 0 1 2 3 4 5 6 7 8 9 A B C D E F Positional A13DH 3DA1HComputer programmers often use the hexadecimal numbersystemWhy?11

Decimal-Hexadecimal EquivalenceDecimal Hex0011223344556677889910A11B12C13D14E15FDecimal Hex16 1017 1118 1219 1320 1421 1522 1623 1724 1825 1926 1A27 1B28 1C29 1D30 1E31 1FDecimal Hex32 2033 2134 2235 2336 2437 2538 2639 2740 2841 2942 2A43 2B44 2C45 2D46 2E47 2F. .12

Decimal-Hexadecimal ConversionHexadecimal to decimal: expand using positional notation25H (2*161) (5*160) 32 5 37Decimal to hexadecimal: use the shortcut37 / 16 2 R 52 / 16 0 R 2Read from bottomto top: 25H13

Binary-Hexadecimal ConversionObservation: 161 24 Every 1 hexadecimal digit corresponds to 4 binary digitsBinary to hexadecimal1010000100111101BA13DHDigit count in binary numbernot a multiple of 4 pad with zeros on leftHexadecimal to binaryA13DH1010000100111101BDiscard leading zerosfrom binary number ifappropriateIs it clear why programmersoften use hexadecimal?14

The Octal Number SystemName “octo” (Latin) eightCharacteristics Eight symbols 0 1 2 3 4 5 6 7 Positional 1743O 7314OComputer programmers often use the octal number systemWhy?15

Decimal-Octal EquivalenceDecimal 7Decimal 7332834293530363137Decimal 3534454455546564757.16

Decimal-Octal ConversionOctal to decimal: expand using positional notation37O (3*81) (7*80) 24 7 31Decimal to octal: use the shortcut31 / 8 3 R 73 / 8 0 R 3Read from bottomto top: 37O17

Binary-Octal ConversionObservation: 81 23 Every 1 octal digit corresponds to 3 binary digitsBinary to octal001010000100111101B1 2 0 4 7 5ODigit count in binary numbernot a multiple of 3 pad with zeros on leftOctal to binary1 2 0 4 7 5O001010000100111101BDiscard leading zerosfrom binary number ifappropriateIs it clear why programmerssometimes use octal?18

AgendaNumber SystemsFinite representation of unsigned integersFinite representation of signed integersFinite representation of rational numbers (if time)19

Unsigned Data Types: Java vs. CJava has type int Can represent signed integersC has type: signed int Can represent signed integers int Same as signed int unsigned int Can represent only unsigned integersTo understand C, must consider representation of bothunsigned and signed integers20

Representing Unsigned IntegersMathematics Range is 0 to Computer programming Range limited by computer’s word size Word size is n bits range is 0 to 2n – 1 Exceed range overflowNobel computers with gcc217 n 32, so range is 0 to 232 – 1 (4,294,967,295)Pretend computer n 4, so range is 0 to 24 – 1 (15)Hereafter, assume word size 4 All points generalize to word size 32, word size n21

Representing Unsigned IntegersOn pretend 11011110111122

Adding Unsigned IntegersAddition3 10-1310011B 1010B---1101B7 10-1110111B 1010B---10001BResults are mod 24Start at right columnProceed leftwardCarry 1 when necessaryBeware of overflowHow would youdetect overflowprogrammatically?23

Subtracting Unsigned IntegersSubtraction10- 7-31202021010B- 0111B---0011B3- 10-920011B- 1010B---1001BResults are mod 24Start at right columnProceed leftwardBorrow 2 when necessaryBeware of overflowHow would youdetect overflowprogrammatically?24

Shifting Unsigned IntegersBitwise right shift ( in C): fill on left with zeros10 1 51010B0101B10 2 21010B0010BWhat is the effectarithmetically? (Nofair looking ahead)Bitwise left shift ( in C): fill on right with zeros5 1 100101B1010B3 2 120011B1100BWhat is the effectarithmetically? (Nofair looking ahead)Results are mod 2425

Other Operations on Unsigned IntsBitwise NOT ( in C) Flip each bit 10 51010B 0101BBitwise AND (& in C) Logical AND corresponding bits10& 7-21010B& 0111B---0010BUseful for settingselected bits to 026

Other Operations on Unsigned IntsBitwise OR: ( in C) Logical OR corresponding bits10 1-111010B 0001B---1011BUseful for settingselected bits to 1Bitwise exclusive OR ( in C) Logical exclusive OR corresponding bits10 10-01010B 1010B---0000Bx x setsall bits to 027

Aside: Using Bitwise Ops for ArithCan use , , and & to do some arithmetic efficientlyx * 2y x y 3*4 3*22 3 2 12x / 2y x y 13/4 13/22 13 2 3x % 2y x & (2y-1) 13%4 13%22 13&(22-1) 13&3 113& 3-1Fast way to multiplyby a power of 2Fast way to divideby a power of 2Fast way to modby a power of 21101B& 0011B---0001B28

Aside: Example C Program#include stdio.h #include stdlib.h int main(void){ unsigned int n;unsigned int count;printf("Enter an unsigned integer: ");if (scanf("%u", &n) ! 1){ fprintf(stderr, "Error: Expect unsigned int.\n");exit(EXIT FAILURE);}for (count 0; n 0; n n 1)count (n & 1);printf("%u\n", count);return 0;}What does itwrite?How could this beexpressed moresuccinctly?29

AgendaNumber SystemsFinite representation of unsigned integersFinite representation of signed integersFinite representation of rational numbers (if time)30

Signed 1100111DefinitionHigh-order bit indicates sign0 positive1 negativeRemaining bits indicate magnitude1101B -101B -50101B 101B 531

Signed Magnitude 00111Computing negativeneg(x) flip high order bit of xneg(0101B) 1101Bneg(1101B) 0101BPros and cons easy for people to understand symmetric- two reps of zero32

Ones’ 01100111DefinitionHigh-order bit has weight -71010B (1*-7) (0*4) (1*2) (0*1) -50010B (0*-7) (0*4) (1*2) (0*1) 233

Ones’ Complement 00111Computing negativeneg(x) xneg(0101B) 1010Bneg(1010B) 0101BComputing negative (alternative)neg(x) 1111B - xneg(0101B) 1111B – 0101B 1010Bneg(1010B) 1111B – 1010B 0101BPros and cons symmetric- two reps of zero34

Two’s 01100111DefinitionHigh-order bit has weight -81010B (1*-8) (0*4) (1*2) (0*1) -60010B (0*-8) (0*4) (1*2) (0*1) 235

Two’s Complement 00111Computing negativeneg(x) x 1neg(x) onescomp(x) 1neg(0101B) 1010B 1 1011Bneg(1011B) 0100B 1 0101BPros and cons- not symmetric one rep of zero36

Two’s Complement (cont.)Almost all computers use two’s complement to representsigned integersWhy? Arithmetic is easy Will become clear soonHereafter, assume two’s complement representation ofsigned integers37

Adding Signed Integerspos pos3 3-6110011B 0011B---0110Bpos pos (overflow)7 1--81110111B 0001B---1000Bpos neg3 -1-211110011B 1111B---10010Bneg neg-3 -2--5111101B 1110B---11011BHow would youdetect overflowprogrammatically?neg neg (overflow)-6 -5-51 11010B 1011B---10101B38

Subtracting Signed IntegersPerform subtractionwith borrows3- 4--1-5- 2--71220011B- 0100B---1111B1011B- 0010B---1001BorCompute two’s compand add3 -4--10011B 1100B---1111B-5 -2--71111011 1110---1100139

Negating Signed Ints: MathQuestion: Why does two’s comp arithmetic work?Answer: [–b] mod 24 [twoscomp(b)] mod 24[–b] mod 24 [24 – b] mod 24 [24 – 1 - b 1] mod 24 [(24 – 1 - b) 1] mod 24 [onescomp(b) 1] mod 24 [twoscomp(b)] mod 24See Bryant & O’Hallaron book for much more info40

Subtracting Signed Ints: MathAnd so:[a – b] mod 24 [a twoscomp(b)] mod 24[a – [a [a [a [a [ab] mod 24 24 – b] mod 24 24 – 1 – b 1] mod 24 (24 - 1 – b) 1] mod 24 onescomp(b) 1] mod 24 twoscomp(b)] mod 24See Bryant & O’Hallaron book for much more info41

Shifting Signed IntegersBitwise left shift ( in C): fill on right with zeros3 1 60011B0110B-3 1 -61101B-1010BWhat is the effectarithmetically?Bitwise arithmetic right shift: fill on left with sign bit6 1 30110B0011BWhat is the effectarithmetically?-6 1 -31010B1101BResults are mod 2442

Shifting Signed Integers (cont.)Bitwise logical right shift: fill on left with zeros6 1 30110B0011B-6 1 51010B0101BWhat is the effectarithmetically?In C, right shift ( ) could be logical or arithmetic Not specified by C90 standard Compiler designer decidesBest to avoid shifting signed integers43

Other Operations on Signed IntsBitwise NOT ( in C) Same as with unsigned intsBitwise AND (& in C) Same as with unsigned intsBitwise OR: ( in C) Same as with unsigned intsBitwise exclusive OR ( in C) Same as with unsigned intsBest to avoid with signed integers44

AgendaNumber SystemsFinite representation of unsigned integersFinite representation of signed integersFinite representation of rational numbers (if time)45

Rational NumbersMathematics A rational number is one that can be expressedas the ratio of two integers Infinite range and precisionCompute science Finite range and precision Approximate using floating point number Binary point “floats” across bits46

IEEE Floating Point RepresentationCommon finite representation: IEEE floating point More precisely: ISO/IEEE 754 standardUsing 32 bits (type float in C): 1 bit: sign (0 positive, 1 negative) 8 bits: exponent 127 23 bits: binary fraction of the form 1.dddddddddddddddddddddddUsing 64 bits (type double in C): 1 bit: sign (0 positive, 1 negative) 11 bits: exponent 1023 52 bits: binary fraction of the dddddddd47

Floating Point ExampleSign (1 bit): 1 negative1100000111011011000000000000000032-bit representationExponent (8 bits): 10000011B 131 131 – 127 4Fraction (23 bits): 1.10110110000000000000000B 1 (1*2-1) (0*2-2) (1*2-3) (1*2-4) (0*2-5) (1*2-6) (1*2-7) 1.7109375Number: -1.7109375 * 24 -27.37548

Floating Point WarningDecimal number system canrepresent only some rationalnumbers with finite digit count Example: 1/3Binary number system canrepresent only some rationalnumbers with finite digit count Example: 1/5Beware of roundoff error Error resulting from inexactrepresentation Can 010 26/1280.00110011 51/256.49

SummaryThe binary, hexadecimal, and octal number systemsFinite representation of unsigned integersFinite representation of signed integersFinite representation of rational numbersEssential for proper understanding of C primitive data types Assembly language Machine language50

Binary-Octal Conversion Observation: 81 23 Every 1 octal digit corresponds to 3 binary digits Binary to octal Octal to binary 18 001010000100111101 B 1 2 0 4 7 5 O Digit count in binary number not a multiple of 3 pad with zeros on left Discard leading zeros from binary