CS1102 Introduction to Computer Studies Lecture 2: Binary Number System PDF

CS1102 Introduction to Computer Studies Not to be redistributed Lecture 02 to Course Hero or any other public websites Binary Number System Semester A, 2024-2025...

CS1102 Introduction to Computer Studies Not to be redistributed Lecture 02 to Course Hero or any other public websites Binary Number System Semester A, 2024-2025 Department of Computer Science City University of Hong Kong 1 Agenda Binary System Hexadecimal System Representations in Binary Numbers Signed Binary Integers Text Representation in Computer Howard Leung/ CS1102 Lec 02 2 Agenda Binary System Hexadecimal System Representations in Binary Numbers Signed Binary Integers Text Representation in Computer Howard Leung/ CS1102 Lec 02 3 Think about it You may have known or heard people say the followings: Computers use binary system to represent information But…. What is a binary system? How is it different from the number system used by humans? Why and how do computers use binary system? Howard Leung/ CS1102 Lec 02 4 Number System Used by Humans Children often use fingers to help them count After the largest 1-digit number 9, the next number is represented by a 2-digit number, i.e., 10 We say that we count in base 10 The number system used Humans use these symbols to represent single by humans is called a decimal system digits (1-digit number): 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 Howard Leung/ CS1102 Lec 02 5 Different number systems Decimal (base 10): commonly used Binary (base 2): computer system Hexadecimal (base 16): color values, some IP addresses Octal (base 8): file permission Interconnected through the reliance on powers of 2 Sexagesimal (base 60): time (minutes and seconds) Dozen/duodecimal (base 12): time (hour), item package Howard Leung/ CS1102 Lec 02 6 Number System Used by Computers Computers use binary system to represent information Examples: A light switch may be on (1) or off (0) An electronic circuit may be closed (1) or open (0) A specific location on a tape or disk may have a positive charge (1) or negative charge (0) Howard Leung/ CS1102 Lec 02 7 Why computer systems are binary? Simplicity of circuit design: binary has only two states 0 or 1, making it easier to design and build reliable electronic circuits Error resistance: easier to interpret with only 0 or 1 Efficiency: operations can be easily performed with logic gates (will cover later in Lec 3) Storage: easy to represent using magnetic states or electrical charges Howard Leung/ CS1102 Lec 02 8 Binary System Under a binary system, we only have 2 symbols: 0, 1 The above symbols are called bits (binary digit) Who invented “bit”? Wikipedia After the largest 1-bit number 1, the next number is represented by a 2-bit number, i.e., 10, 11 Numbers in a binary system are in base 2 Sometimes we use a number in subscript to represent the base, e.g., e.g., 102 = 210 [10 in base 2 is equal to 2 in base 10] Pronounced as Pronounced as “one zero” “ten” Howard Leung/ CS1102 Lec 02 9 Decimal and Binary Number Systems Decimal Binary 0 0 1 1 2 10 3 11 Given a decimal 4 100 Given a binary number, number, how to 5 101 how to convert it to its convert it to its binary 6 110 decimal representation representation 7 111 (binary-to-decimal (decimal-to-binary 8 1000 conversion)? conversion)? 9 1001 10 1010 11 1011 12 1100 13 1101 14 1110 15 1111 …… Howard Leung/ CS1102 Lec 02 10 Binary  Decimal Conversion (1) Let’s first try to examine a multiple digit decimal number e.g., 37510= 3×100 + 7×10 + 5 = 3×102 + 7×101 + 5×100 hundreds tens ones This technique can be applied to convert a multiple bit binary number to decimal e.g., 10112 = 1×23 + 0×22 + 1×21 + 1×20 = 1×8 + 0×4 + 1×2 + 1×1 = 1110 Howard Leung/ CS1102 Lec 02 11 Binary  Decimal Conversion (2) More generally, any k-digit number of base b can be expressed in the following way. dk-1dk-2 …d1d0 = dk-1×bk-1 + dk-2×bk-2 + … + d1×b1 + d0×b0 = ∑𝑘𝑘−1 𝑖𝑖 𝑖𝑖=0 (𝑑𝑑𝑖𝑖 × 𝑏𝑏 ) Howard Leung/ CS1102 Lec 02 12 Decimal  Binary Conversion (1) e.g., what is 1110 in binary? Repeated division can be used to convert a Remainder decimal number to binary as follows: 11 ÷ 2 = 5 ··· 1 Dividend Divisor Quotient 1. Divide the value by two and record the remainder 5 ÷ 2 = 2 ··· 1 2. Continue to divide the quotient by two and record the remainder, until the newest quotient becomes zero 2 ÷ 2 = 1 ··· 0 3. The binary representation is the remainders listed from bottom to top in the order they were recorded 1 ÷ 2 = 0 ··· 1 2 11 2 5 ··· 1 Answer: 1 0 1 1 Simplified way: 2 2 ··· 1 Howard Leung/ CS1102 Lec 02 1 ··· 0 13 Decimal  Binary Conversion (2) Exercise: What is 1910 in Binary? Answer: 10011 19 ÷ 2 = 9 … 1 9÷2=4…1 4÷2=2…0 2÷2=1…0 1÷2=0…1 Howard Leung/ CS1102 Lec 02 14 Note on Binary ↔ Decimal Conversion The techniques from the previous slides are only applicable for positive integers Other techniques are used by computer to represent Negative numbers, e.g., −2 (to be covered later) Fractional numbers, e.g., 3.1415 Very large numbers, e.g., 6.022×1023 Very small numbers, e.g., 6.626×10-34 More details on Wikipedia. Howard Leung/ CS1102 Lec 02 15 Binary Arithmetic (1) Binary Addition Binary Subtraction The concept is the same as how you do carrying/ 0+0=0 0-0=0 borrowing when adding/ 0+1=1 0 - 1 = 1, and borrow 1 from subtracting decimal numbers 1+0=1 the next more significant bit Try to add 00095050 + 1 + 1 = 0, and carry 1 to the 1-0=1 00005500 in decimal and next more significant bit see how you do the 1-1=0 carrying learnt from your primary school e.g., e.g., Try to calculate 00550055- 0 0 0 1 1 0 1 0 = 2610 0 0 1 1 0 0 1 1 = 5110 00050550 in decimal and + 0 0 0 0 1 1 0 0 = 1210 - 0 0 0 1 0 1 1 0 = 2210 see how you do the borrowing learnt from your 0 0 1 0 0 1 1 0 = 3810 0 0 0 1 1 1 0 1 = 2910 primary school Howard Leung/ CS1102 Lec 02 16 Binary Arithmetic (2) Binary Multiplication Try to calculate 101001 x 110 as decimal numbers 0x0=0 0x1=0 1x0=0 1x1=1 i.e. add the shifted multiplicand if the bit is 1 e.g., 0 0 1 0 1 0 0 1 (4110) x 00000110 (610 ) 00000000 00101001 00101001 0 0 1 1 1 1 0 1 1 0 (24610) Howard Leung/ CS1102 Lec 02 17 Binary Arithmetic (3) Binary Division: repeated process of Try to calculate 10000111 / 101 in long division subtraction form as decimal numbers e.g., 1 1 0 1 1 (2710 ) 101 1 0 0 0 0 1 1 1 (13510) (510) - 101 110 -101 011 - 0 111 - 101 101 - 101 0 Howard Leung/ CS1102 Lec 02 18 Agenda Binary System Hexadecimal System Representations in Binary Numbers Signed Binary Integers Text Representation in Computer Howard Leung/ CS1102 Lec 02 19 Possible Number Range with a Byte A byte consists of 8 bits The smallest value represented by a byte is: 000000002=010 The largest value represented by a byte is: 111111112=25510 Thus there can be a total of 256 values (0,1,2,……,254,255) represented by a byte. Alternatively, this range can also be computed as 28 bit 7 bit 6 bit 5 bit 4 bit 3 bit 2 bit 1 bit 0 0/1 0/1 0/1 0/1 0/1 0/1 0/1 0/1 2 × 2 × 2 × 2 × 2 × 2 × 2 × 2 = 28 = 256 Howard Leung/ CS1102 Lec 02 20 Data Size Measurement Normally data size is measured by bytes with various order of magnitude: Kilobytes (KB): 210 = 1,024 bytes e.g., a simple text file Megabytes (MB): 220 = 1,024 KB = 1,048,576 bytes e.g., picture taken by your mobile phone Gigabytes (GB): 230 = 1,024 MB = 1,073,741,824 bytes e.g., maximum data usage of your mobile plan Terabytes (TB): 240 = 1,024 GB = 1,099,511,627,776 bytes e.g., storage size of your hard drive Petabytes (PB): 250 = 1,024 TB = 1,125,899,906,842,624 bytes e.g., scale of total data size of Netflix movies Exabytes (EB): 260 = 1,024 PB = 1,152,921,504,606,846,976 bytes e.g., scale of Dropbox storage system Howard Leung/ CS1102 Lec 02 21 Hexadecimal System Under a hexadecimal system, we have the following 16 symbols: 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, A, B, C, D, E, F The above symbols are called nibbles After the largest 1-nibble number F, the next number is represented by a 2-nibble number, i.e., 10 Numbers in a hexadecimal system are in base 16 Howard Leung/ CS1102 Lec 02 22 Decimal and Hexadecimal Number Systems Decimal Hexadecimal 0 0 1 1 2 2 3 3 4 4 Given a decimal number, Given a hexadecimal 5 5 how to convert it to its number, how to convert it 6 6 hexadecimal to its decimal 7 7 representation representation 8 8 (decimal-to-hexadecimal (hexadecimal-to-decimal 9 9 conversion)? conversion)? 10 A 11 B 12 C 13 D 14 E 15 F 16 10 …… Howard Leung/ CS1102 Lec 02 23 Hexadecimal  Decimal Conversion Remember binary-to-decimal conversion? e.g., 10112 = 1×23 + 0×22 + 1×21 + 1×20 = 1×8 + 0×4 + 1×2 + 1×1 = 1110 Hexadecimal-to-decimal conversion works in a similar way, while keeping in mind that the input number is in base 16 e.g., 3C816 = 3×162 + 12×161 + 8×160 C16 = 1210 = 3×256 + 12×16 + 8×1 = 768 + 192 + 8 = 96810 Howard Leung/ CS1102 Lec 02 24 Decimal  Hexadecimal Conversion Repeated division can also be used e.g., what is 96810 in hexadecimal? to convert a decimal number to Remainder hexadecimal as follows: 968 ÷ 16 = 60 ··· 8 Dividend 1. Divide the value by 16 and record the Divisor Quotient remainder converted to hexadecimal, i.e., 0,1,2,…,9,A,B,C,D,E,F 60 ÷ 16 = 3 ··· 12=C 2. Continue to divide the quotient by 16 and record the remainder, until the newest 3 ÷ 16 = 0 ··· 3 quotient becomes zero 3. The hexadecimal representation is the remainders listed from bottom to top in the order they were recorded 16 968 16 60 ··· 8 Answer: 3 C 8 Simplified way: 3 ··· 12=C Howard Leung/ CS1102 Lec 02 25 Binary  Hexadecimal Conversion So far you have learnt about conversions of Decimal ↔ Binary Decimal ↔ Hexadecimal How do you convert between binary and hexadecimal numbers? hexadecimal → binary hexadecimal → decimal What if we carry out the following 2 steps for each case? decimal → binary binary → hexadecimal 1) binary → decima e.g. 9716 in binary? 2) decimal → hexadecimal e.g. 101001012 in hexadecimal? 9716 = 9×16+7×1=15110 1) 101001012 = 27+25+22+1=16510 15110 = 128+16+4+2+1= 2) 16510 = 10×16+5×1 = A516 100101112 ∴101001012 = A516 ∴ 9716 = 100101112 Although you can get the answer by this method, this may not be the most efficient way for calculation! Howard Leung/ CS1102 Lec 02 26 Binary ↔ Hexadecimal Conversion (2) Let’s look at some examples. Can you identify some patterns? Hexadecimal Binary Hexadecimal Binary hexadecimal → binary: Each nibble from the hexadecimal number 0 0 34 11 0100 is converted individually to a 4-bit binary 1 1 39 11 1001 number 2 10 3C 11 1100 (leading 0s are appended if required, e.g., 3 11 3E 11 1110 from 100 to 0100) 4 100 74 111 0100 binary → hexadecimal: 5 101 79 111 1001 every 4 bits starting from the right of the 6 110 7C 111 1100 binary number are converted individually 7 111 7E 111 1110 to a nibble 8 1000 C4 1100 0100 9 1001 C9 1100 1001 What is 3A8D16 in binary? A 1010 CC 1100 1100 B 1011 CE 1100 1110 What is 100110111010112 in C 1100 E4 1110 0100 hexadecimal? D 1101 E9 1110 1001 E 1110 EC 1110 1100 F 1111 EE 1110 1110 Howard Leung/ CS1102 Lec 02 27 An Example: Byte Representing Colors Each color shown on screen is a combination of red, green and blue (RGB) with different intensity values In a “true color” system, a color is represented by 24 bits, 8 bits for red, 8 bits for green and 8 bits for blue. Each color component, red, green and blue, takes a value ranging from 0 to 255, e.g., Red Green Blue Purple: 172 73 185 #AC49B9 Yellow: 253 249 88 #FDF958 Note: in HTML, sometimes text or background color is defined in hexadecimal notation Howard Leung/ CS1102 Lec 02 28 Agenda Binary System Hexadecimal System Representations in Binary Numbers Signed Binary Integers Text Representation in Computer Howard Leung/ CS1102 Lec 02 29 Word A word is the number of bits that can be accessed at one time by the computer central processing unit (CPU). The more bits in a word, the more data a computer can process at one time. E.g., a 64-bit-word computer can access 64 bits (8 bytes) at a time Computers represent numbers in binary with a fixed N-bit-word Assume that N=4, then 4 bits are used to represent a number, e.g., 00002 = 010 00012 = 110 00102 = 210 …… 11112 = 1510 Note that leading 0s (underlined in red in the above examples) are added to make up the 4 bits Howard Leung/ CS1102 Lec 02 30 Enumerating Binary Numbers (1) How would you enumerate all N-bit word binary numbers in ascending order? Decimal 4-Bit Word 0 0000 Decimal 1-Bit Word Decimal 3-Bit Word 1 0001 0 0 0 000 2 0010 1 1 1 001 3 0011 2 010 3 011 4 0100 Decimal 2-Bit Word 4 100 5 0101 0 00 5 101 6 0110 1 01 6 110 7 0111 2 10 7 111 8 1000 3 11 9 1001 10 1010 Bit 0 (rightmost bit): The bit alternates between every number 11 1011 12 1100 Can you determine the pattern 13 1101 Bit 1 : The bit alternates between every 2 numbers by observing each bit column? 14 1110 15 1111 Bit 2 : The bit alternates between every 4 numbers Bit023 Howard Leung/ CS1102 Lec : The bit alternates between every 8 numbers 31 Enumerating Binary Numbers (2) Decimal Bit 4 Bit 3 Bit 2 Bit 1 Bit 0 0 0 0 0 0 0 1 0 0 0 0 1 2 0 0 0 1 0 3 0 0 0 1 1 4 0 0 1 0 0 5 0 0 1 0 1 6 0 0 1 1 0 7 0 0 1 1 1 8 0 1 0 0 0 9 0 1 0 0 1 Knowing the bit patterns 10 0 1 0 1 0 11 0 1 0 1 1 can help you quickly 12 13 0 0 1 1 1 1 0 0 0 1 enumerate N-word binary 14 0 1 1 1 0 numbers as well as double 15 0 1 1 1 1 16 1 0 0 0 0 check whether you make 17 18 1 1 0 0 0 0 0 1 1 0 any mistakes in listing 19 1 0 0 1 1 these numbers 20 1 0 1 0 0 21 1 0 1 0 1 22 1 0 1 1 0 23 1 0 1 1 1 24 1 1 0 0 0 25 1 1 0 0 1 26 1 1 0 1 0 27 1 1 0 1 1 28 1 1 1 0 0 29 1 1 1 0 1 Howard Leung/ CS1102 Lec 02 30 1 1 1 1 0 32 31 1 1 1 1 1 Number of Possible Values in N-bit Word How many possible values can be represented by an N-bit word? Decimal 2-Bit Word Decimal 3-Bit Word Decimal 4-Bit Word 0 00 0 000 0 0000 Decimal 1-Bit Word 1 001 1 0001 1 01 0 0 2 010 2 0010 2 10 1 1 3 011 3 0011 3 11 N=1: 2 possible values 4 100 4 0100 N=2: 4 possible values 5 101 5 0101 6 110 6 0110 7 111 7 0111 Remember the number of possible values N=3: 8 possible values 8 1000 that can be represented by a byte? 9 1001 10 1010 bit 7 bit 6 bit 5 bit 4 bit 3 bit 2 bit 1 bit 0 11 1011 12 1100 0/1 0/1 0/1 0/1 0/1 0/1 0/1 0/1 13 1101 14 1110 15 1111 2 × 2 × 2 × 2 × 2 × 2 × 2 × 2 = 28 = 256 N=4: 16 possible values In general, possible values can be 2N Howard Leung/ CS1102 Lec 02 represented by an N-bit word 33 Representation with Minimum Number of Bits (1) If there are K items (e.g., books), and you need to assign distinct N-bit words to these items (so as to give a unique ID in the form of an N-bit word to every item), what is the minimum value of N? For example, K=4: 1-bit word can represent 2 possible values 2-bit word can represent 4 possible values So the minimum value of N is 2 for K = 4 K=5: 2-bit word can only represent 4 possible values so it is not enough 3-bit word can represent 8 possible values So the minimum value of N is 3 for K = 5 Howard Leung/ CS1102 Lec 02 34 Representation with Minimum Number of Bits (2) In general, what is the minimum value of N to enable N-bit word to represent K items, where K is a positive integer? Note that 1-bit word can represent 2 possible values 2-bit word can represent 4 possible values 3-bit word can represent 8 possible values N-bit word can represent 2N possible values It can be observed that if K is a power of 2, i.e., 2p , then N=p If K is not a power of 2, then N=q such that 2q-1