Robert M Posted December 8, 2003 Share Posted December 8, 2003 Lesson 4 - Binary Counting In previous lessons, I have hinted that there is a standard method for counting using bits. In this lesson, I will introduce that standard method. First, I want to reiterate that this is NOT the only way to count using bits. It is simply the most common method, and therefore has considerable support for it built into most microprocessors including the 650X processor Family used in most classic gaming consoles and computers from the late 70's and 80's. Numbering Systems: ------------------ I must assume that if you can read the lessons in this class and understand them, then you must be familiar with decimal numbers and basic arithemetic like adding and subtracting. All decimal numbers are made using the ten digits: 0, 1, 2, 3, 4, 5, 6, 7, 8, and 9. When you write a decimal number larger than 9 you must use two or more digits like this: 123 which is one hundred and twenty three. The 1 in 123 does not represent 1 it represents 100. The 2 in 123 is not 2 it is 20. The 3 in 123 does represent 3. Thus we call the 1 the hundreds digit, the 2 the tens digit, and 3 the one's digit. Each digit in a large decimal number represents that digit multiplied by a power of 10 based on its position and summed together. Thus (1 * 10^2) + (2 * 10^1) + (3 * 10^0) = 100 + 20 + 3 = 123 Ta!Da! We count numbers inside computers exactly the same way except that the numbering system in computers does not have 10 digits, it only has 2 digits: 0 and 1 (bits!). The numbering system that uses only 0 and 1 is called the binary numbering system or simply binary. Since it only has 2 digits the value of each binary digit in a large binary number is muliplied by a power of 2 instead of a power of 10 as we do for decimal numbers. The following table shows the positional value of the first 16 bits in the binary number system, as a power of 2. Note that the first position is numbered zero and not one. Bit position. | | Bit value | | 2^0 = 1 => bit 2^1 = 2 2^2 = 4 => octet 2^3 = 8 => nybble 2^4 = 16 2^5 = 32 2^6 = 64 2^7 = 128 => byte 2^8 = 256 2^9 = 512 2^10 = 1024 2^11 = 2048 2^12 = 4096 2^13 = 8192 2^14 = 16384 2^15 = 32768 => word Every computer in the world has a limited number of bits. When you use binary numbers in a computer program you must decide how many bits you will use to store each number that your program must keep track of. For 650X processors the most common numbers of bits to use will be 8 (byte) and 16 (word) because the processor works with data an entire byte at a time for each instruction (see opcodes in lesson 3). You can use any number of bits, but since 8 and 16 are so common we will focus on them for the remainder of this lesson. The same rules will apply to binary numbers made of any number of bits. This should not seem strange, as you can use any number of digits to represent a decimal number. If you don't need all the digits, then your number will have 1 or more leading zeros. 0000123 is the 7-digit decimal number 123, by convention leading zeros are not shown for decimal numbers, but they are always present nonetheless. The same is true for binary numbers. In the real world you can write as big of decimal number as your writing surface will allow. In a computer your writing surface is bits. If you do not have enough bits allocated/available to store a binary number then your program can not store that number and the information will be lost. Such an event is called overflow if the number is too big, or underflow if the number is too small. We will examine overflow and underflow in detail in the next lesson. You may be curious to know what is the biggest binary number you can store in a byte or a word. You already learned the formula in lesson 2 - enumeration. Given N bits, you can store 2^N different values. Counting positive integers starts at zero not one, so N bits can store binary numbers from 0 to (2^N)-1 Example: A byte has 8 bits so N=8: Therefore, a byte can hold unsigned positive integers from 0 to (2^8)-1=256-1=255. From 0 to 255. ALGORITHM to convert decimal to binary: --------------------------------------- To convert a decimal number to binary, you must repeatedly divide that number by 2. The remainder of each division is next binary digit in the binary representation of that decimal number. when there is nothing left to divide, the conversion is done. Example: Convert 123 decimal to its binary equivalent. 123 / 2 = 61 with a remainder of 1 -------+ 61 / 2 = 30 with a remainder of 1 ------+| 30 / 2 = 15 with a remainder of 0 -----+|| 15 / 2 = 7 with a remainder of 1 ----+||| 7 / 2 = 3 with a remainder of 1 ---+|||| 3 / 2 = 1 with a remainder of 1 --+||||| 1 / 2 = 0 with a remainder of 1 -+|||||| ||||||| 123 Decimal = 1111011 binary ALGORITHM to convert binary to decimal: --------------------------------------- Any binary number can be converted to its decimal equivalent, which is often easier for humans to read and understand. To convert a binary number to decimal you must multiply each digit of the binary number by its positional value (see the first table above) and add the digit values together to form the decimal value. Example: Convert 1111011 binary to decimal 1111011 binary ||||||| ||||||+- 1 * 2^0 = 1 * 1 = 1 |||||+-- 1 * 2^1 = 1 * 2 = 2 ||||+--- 0 * 2^2 = 0 * 4 = 0 |||+---- 1 * 2^3 = 1 * 8 = 8 ||+----- 1 * 2^4 = 1 * 16 = 16 |+------ 1 * 2^5 = 1 * 32 = 32 +------- 1 * 2^6 = 1 * 64 = 64 --- 123 decimal Binary Number Notation: ----------------------- Up until now I have been explicitly stating whether a written number is binary or decimal. As you can see it can become tedious to write "binary" or "decimal" after every number to clearly indicate the numbering system being used. Luckily, a handy shorthand notation exists for us to use to save time. For the remainder of this class I will always make use of this notation to indicate whether a number is binary or decimal. Decimal Notation: A decimal number is written with no special notation at all. It is written the same way you have always written decimal numbers. Binary Notation: All binary numbers shall be preceded by the % symbol. Examples: 123 is decimal and %1111011 is its binary equivalent. 101 is decimal = One hundred and one. %101 is binary = 4 + 1 = Five MSB and LSB: Another aspect of binary notation is Most-Significant and Least-Significant Bits (MSB and LSB). By convention a binary number is written from left to right the same as a decimal number. The left-most digit of a number represents the greatest portion of the overall value of the whole number. It is the Most-Significant digit in the number. The right-most digit of any number represents the least portion of the whole value. It is the Least-Significant digit. Each digit in a binary number is a bit. Therefore, the Most-Significant Bit (MSB) of a binary number is the leftmost bit, and the Least-Significant Bit (LSB) is the right most bit. Examples %100010010 ^ ^ | | MSB LSB %10111010010010 ^ ^ | | MSB LSB %100110 ^ ^ | | MSB LSB Please get comfortable with this notation for binary numbers because you will be using it extensively when writing assembly language programs! WHAT about negative numbers! ---------------------------- You may have noticed that so far our discussion of binary has been restricted to positive integers. Computers can count negative numbers, so now we will begin to explore methods for representing negative numbers in binary. We will complete this discussion in Lesson 5. Sign Magnitude Format: The first format for negative numbers we will explore is the sign-magnitude format. The format is easy to understand. For any given binary number add an additional bit to represent the sign of the number. If the sign bit is set, then the number is negative. If the sign bit is clear then the number is positive. The sign bit is the MSB of a sign-magnitude binary number. Examples: %0101 = %0 sign and %101 magnitude = 5 %1101 = %1 sign and %101 magnitude = -5 | +-> The MSB is the Sign bit There is a problem with this method of representing negative numbers. Can you see what that problem is? The problem is with the number zero. Using this system there are 2 instances of zero, a negative zero and a positive zero. There is no such thing as negative zero, so this may not be the best method for representing negative numbers. Two's Complement Format: (Introduction) An alternative to the sign-magnitude format is the two's complement format. Two's complement is superior to sign-magnitude (usually, but not always) because there is only one way to represent zero. Another advantage of two's complement is that when you add or subtract positve and negative numbers, the result is the correct number in two's complement format. To really understand two's complement, you must know how to add and subtract binary numbers. We won't learn how to add and subtract binary numbers until lesson 5, so we will suspend further discussion of negative binary numbers until lesson 5. What about REAL numbers? Yes, you can represent REAL numbers in binary. REAL numbers can also be thought of as fractions (1.23 for example). This is an advanced topic and I don't want to go into it now because I beleive it will confuse more people than it will help them to understand. You can write many, many programs without every needing to use REAL numbers. So just put them out of your mind for now. ------------------------------------------------------------------------- Exercises: 1. Convert 213 to binary 2. Convert %00101100 to decimal 3. Convert 1087 to binary 4. COnvert %1000010100011110 to decimal 5. Using the list of binary numbers below: %00110101 %01000101 %11100001 %10100110 %01001011 %01001110 %11001001 Take the LSB from each of the above numbers, in order from top to bottom, to create a new binary number. The LSB from the first number in the list should be the LSB of the new number. The LSB of the last number in the list is the MSB of the new binary number. What is the new binary number? Now convert that number to decimal. 6. For each of the numbers below, convert them to decimal twice. The first time assume that the numbers are in unsigned positive integer format. The second time assume that the numbers are in sign-magnitude format. a. %1000101 b. %0101010 c. %1100110 d. %0000010 7. What is the range of positive unsigned integers that can be stored in a word. BONUS QUESTION 1: For each number a-d in problem 6, is each number signed or unsigned? (Hint: refer to lesson 1). BONUS Question 2: Is the sign-magnitude format an Enumeration (Lesson 2) or a code (Lesson3), and why? ------------------------------------------------------------------------- NOTE TO READERS: We are rapidly descending from broad concepts to specific details in ASsembly programming. Most often, subsequent lessons will require an understanding of previous lessons. If you have questions after studying this material, do not hesitate to ask. Quote Link to comment Share on other sites More sharing options...
Robert M Posted January 6, 2004 Author Share Posted January 6, 2004 Sorry it took me so long to post these answers. ANSWERS TO EXERCISES: 1. Convert 213 to binary 213 / 2 = 106 with a remainder of 1 ---------+ 106 / 2 = 53 with a remainder of 0 --------+| 53 / 2 = 26 with a remainder of 1 -------+|| 26 / 2 = 13 with a remainder of 0 ------+||| 13 / 2 = 6 with a remainder of 1 -----+|||| 6 / 2 = 3 with a remainder of 0 ----+||||| 3 / 2 = 1 with a remainder of 1 ---+|||||| 1 / 2 = 0 with a remainder of 1 --+||||||| %11010101 binary = 213 decimal. 2. Convert %00101100 to decimal %00101100 |||||||| |||||||+--- 0 * 2^0 = 0 * 1 = 0 ||||||+---- 0 * 2^1 = 0 * 2 = 0 |||||+----- 1 * 2^2 = 1 * 4 = 4 ||||+------ 1 * 2^3 = 1 * 8 = 8 |||+------- 0 * 2^4 = 0 * 16 = 0 ||+-------- 1 * 2^5 = 1 * 32 = 32 |+--------- 0 +---------- 0 0 + 0 + 4 + 8 + 0 + 32 + 0 + 0 = 44 decimal. 3. Convert 1087 to binary 1087 / 2 = 543 with a remainder of 1 543 / 2 = 270 with a remainder of 1 270 / 2 = 135 with a remainder of 0 135 / 2 = 67 with a remainder of 1 67 / 2 = 33 with a remainder of 1 33 / 2 = 16 with a remainder of 1 16 / 2 = 8 with a remainder of 0 8 / 2 = 4 with a remainder of 0 4 / 2 = 2 with a remainder of 0 2 / 2 = 1 with a remainder of 0 1 / 2 = 0 with a remainder of 1 So 1087 decimal = %10000111011 binary. 4. Convert %1000010100011110 to decimal | | | |||| | | | |||+---- 1 * 2^1 = 2 | | | ||+----- 1 * 2^2 = 4 | | | |+------ 1 * 2^3 = 8 | | | +------- 1 * 2^4 = 16 | | +----------- 1 * 2^8 = 256 | +------------- 1 * 2^10 = 1024 +------------------ 1 * 2^15 = 32768 2+4+8+16+256+1024+32768 = 34078 decimal 5. Using the list of binary numbers below: %00110101 %01000101 %11100001 %10100110 %01001011 %01001110 %11001001 Take the LSB from each of the above numbers, in order from top to bottom, to create a new binary number. The LSB from the first number in the list should be the LSB of the new number. The LSB of the last number in the list is the MSB of the new binary number. What is the new binary number? Now convert that number to decimal. answer: The LSB is the rightmost digit of each number, so the new binary number is: %1010111 which in decimal is: 64+0+16+0+4+2+1 = 87 6. For each of the numbers below, convert them to decimal twice. The first time assume that the numbers are in unsigned positive integer format. The second time assume that the numbers are in sign-magnitude format. a. %1000101 unsigned = 64 + 0 + 0 + 0 + 4 + 0 + 1 = 69 decimal signed = (-1) * (0 + 0 + 0 + 4 + 0 + 1 ) = -5 decimal b. %0101010 unsigned = 0 + 32 + 0 + 16 + 0 + 2 + 0 = 50 signed = (+1) * ( 32 + 0 + 16 + 0 + 2 + 0 ) = 50 c. %1100110 unsigned = 64 +32 + 0 + 0 + 4 + 2 + 0 = 102 signed = (-1) * ( 32 + 0 + 0 +4 +2 +0 ) = -38 d. %0000010 unsigned = 2 signed = 2 7. What is the range of positive unsigned integers that can be stored in a word. answer: There are two basic ways to solve this problem. I will demonstrate both because I think its important to see the relationships that make both methods arrive at the same answer. a. The first approach is to realize that smallest unsigned integer is always zero. The binary value is unsigned so no bits are needed to store the sign of the number. In that case the largest unsigned number is the value of the binary number with all bits set to 1. A word has 16 bits, so the biggest unsigned binary number in a word is %1111111111111111 If we convert that to decimal we get: 2^15 + 2^14 + 2^13 + 2^12 + 2^11 + 2^10 + 2^9 + 2^8 + 2^7 + 2^6 + 2^5 + 2^4 + 2^3 + 2^2 + 2^1 + 2^0 = 32768 + 16384 + 8192 + 4096 + 2048 + 1024 + 512 + 256 + 128 + 64 + 32 + 16 + 8 + 4 + 2 + 1 = 65535. b. The second approach is to recall the formula from lesson 2 to find the maximum number of items that you can enumerate given N bits. The binary number system is just an enumeration of the natural numbers. combinations = 2 ^ 16 = 65536 combinations. Recall however that the enumeration begins at 0, so that leaves 65536 - 1 = 65535 as the largest possible unsigned integer in a word. BONUS QUESTION 1: For each number a-d in problem 6, is each number signed or unsigned? (Hint: refer to lesson 1). answer: This is a trick question. The correct answer is both. As we learned in the first lesson bits represent whatever you the programmer say that they represent. They can represent both at the exact same time. It doesn't matter, they are only bits. Meaning is given by you the programmer with the logic of your code. BONUS Question 2: Is the sign-magnitude format an Enumeration (Lesson 2) or a code (Lesson3), and why? It is a code, because enumerations represent only positive values from 0 to N. I just thought of another valuable piece of information I forgot to include in this lesson. Please note that the LSB of a binary number indicates whether the number is odd or even. If the LSB is 1 then the number is odd. If the LSB is zero, then the number is even. In your code you may wish to take an action only on odd or even scanlines or frames. You will know if the scanline or frame is even or odd by examining the LSB of the scanline or frame counter.[/code] Quote Link to comment Share on other sites More sharing options...
Gateway Posted January 6, 2004 Share Posted January 6, 2004 ... 4. Convert %1000010100011110 to decimal | | | |||| | | | |||+---- 1 * 2^1 = 2 | | | ||+----- 1 * 2^2 = 4 | | | |+------ 1 * 2^3 = 8 | | | +------- 1 * 2^4 = 16 | | +----------- 1 * 2^8 = 256 | +------------- 1 * 2^10 = 1024 +------------------ 1 * 2^15 = 32768 2+4+8+16+1024+32768 = 33822 decimal Did you mean: 2+4+8+16+256+1024+32768 = 34068 decimal? Keep up the lessons! I'm stretching the left-side of my brain passed its limits now! Quote Link to comment Share on other sites More sharing options...
Nukey Shay Posted January 6, 2004 Share Posted January 6, 2004 Math nazi Quote Link to comment Share on other sites More sharing options...
Robert M Posted January 6, 2004 Author Share Posted January 6, 2004 ... 4. Convert %1000010100011110 to decimal | | | |||| | | | |||+---- 1 * 2^1 = 2 | | | ||+----- 1 * 2^2 = 4 | | | |+------ 1 * 2^3 = 8 | | | +------- 1 * 2^4 = 16 | | +----------- 1 * 2^8 = 256 | +------------- 1 * 2^10 = 1024 +------------------ 1 * 2^15 = 32768 2+4+8+16+1024+32768 = 33822 decimal Did you mean: 2+4+8+16+256+1024+32768 = 34068 decimal? Keep up the lessons! I'm stretching the left-side of my brain passed its limits now! Yes, Thanks for catching that. I will edit the original post. Quote Link to comment Share on other sites More sharing options...
Like us on Facebook
Follow us on Twitter
AtariAge on Instagram
Watch us on YouTube
Chat on Discord
Recommended Posts
Join the conversation
You can post now and register later. If you have an account, sign in now to post with your account.
Note: Your post will require moderator approval before it will be visible.