Binary Nums
Back to the Case Studies homepage
ProblemAs you may know, computers work on the binary system. In this system, numbers are written using only 0s and 1s. In this question, you’ll write a program to convert binary numbers to normal (decimal) numbers. How are all numbers represented in 0s and 1s?
1 * 2^6 + 0 * 2^5 + 1 * 2^4 + 1 * 2^3 + 0 * 2^2 + 0 * 2^1 + 1 * 2^0 = 89
Program Specifications
Enter a binary number:1001010 1001010 in decimal is 74. Enter a binary number:1001111 1001111 in decimal is 79. Enter a binary number:10000111 10000111 in decimal is 135. Enter a binary number:-1 Programmed by [your name here]. End of processing. OutputUse System.out.println() for output. Follow the format of the output shown above. Note for further development: You may notice that your program fails for large numbers. That's because of integer overflow. If you would like to get your program to work for larger binary numbers, replace int with long in your program (including using the Scanner method nextLong()). |
Numbers | |||||||||||||||||||||||||
---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
SolutionThe greatest way to start a problem is to divide it into smaller problems. Clearly, the main problem to solve is converting binary numbers to decimal numbers. Think of input using the scanner class and looping for more input as the other two sub-problems. You can divide a problem any way you see fit; I've decided to break this problem into three parts:
The first part of the solution shows how to convert from binary numbers to decimal numbers going from pseudocode to working Java code. The second part shows how to use the scanner class to obtain input from the terminal. The third part shows how to add a loop to your code in order to keep prompting the user for input. Let's start by solving the main problem.
Convert from Binary Numbers to Decimal NumbersOn our road to a solution, we will take a detour and forget about writing Java code. Instead we will use something simpler. We can draw diagrams, write equations, and write pseudocode. We can always write Java code once we understand how to solve the problem. However, let’s go completely off track, and make sure we understand what binary numbers and decimal numbers are. Numbers are not all the same. Human beings have used many different number systems throughout the ages. People today are used to decimal numbers, but this wasn’t always so. Decimal numbers are base 10, and some people may say it makes sense because we usually count with 10 fingers. However, we have 12 months in a year rather than 10, and 7 days in a week not 10. Decimal numbers are the numbers you are used to. We use 1,2,3,4,5,6,7,8,9, to represent values and 0 as a place-holder and to represent no amount. Before we can understand the binary system, let’s understand how the decimal system works. You know intuitively that 123 is one-hundred and twenty-three, and you have a good idea of what that means. However, to understand decimal in depth, you’ll want to be able to explain it mathematically. 123 = 3 + 2* 10 + 1 * 100 This is better represented as: 123 = 3 * 10^0 + 2* 10^1 + 1 * 10^2 Now that we have explained how decimal numbers work, it is time to explain binary numbers. Binary numbers work exactly as decimal works except instead of 10, we use 2. And we only use the digits 0 and 1. The binary number 100 means: 100 = 0 + 0* 2 + 1 * 4 This is better represented as: 100 = 0 * 2^0 + 0* 2^1 + 1 * 2^2 However, the best way to be sure we know how to convert the binary numbers to decimal numbers is to do it. Let's check that we understand by converting some numbers from binary to decimal on paper. By solving the problem on paper, we can more easily see the steps. Convert the following numbers from binary to decimal on paper: 101, 1000, 1101, 10101. When you are done, check for the solution at the end of this case study (in Solutions to Exercises). The solution to the first number follows:
100 Convert to decimal. Start at rightmost digit. 0 * 2^0 = 0 0 * 2^1 = 0 1 * 2^2 = 4 answer: 0 + 0 + 4 = 4. 100 in binary is 4 in decimal. The next step is to describe the steps you used. This will be your pseudocode. Do not focus on writing Java-like pseudocode, start by writing it out in English. I started with the following pseudocode:
1. Take the rightmost digit, if it is a 1, multiply it by 2 to the power of the current exponent and add it to the sum. 2. Do the same with digits to the left of the rightmost digit. More thinking shows we need to tell what sum, and what exponent to start at. Let's also add variables for clarity. currPower = 0 sum = 0 Take the rightmost digit currDigit. if currDigit == 1 sum = sum + currDigit * 2 ^ currPower Do the same with digits to the left of the rightmost digit.
Use ModulusIn Java, you can use some basic arithmetic operators, you can multiply, divide, add, subtract, and obtain the remainder. Perhaps you expect me to teach about the extract-rightmost-digit operator. Unfortunately, it does not exist. We need to use the basic arithmetic operators to do our bidding. Fortunately, there's a solution for that. The rightmost digit of a number is the exact same thing as the remainder of a number divided by 10. For example, the remainder of 26 divided by 10 is 6. In Java, we would write 26 % 10 to do the same operation. Use Integer DivisionIn order to go through the number digit-by-digit, from right to left, you will want to ignore the rightmost digit. How do we do this? Recall that Java allows for integer division. This means the division of two integers ignores any fractions. So 3/2 evaluates to 1 in Java although it equals 1.5 in regular math. To chop off the rightmost digit, we simply divide by 10. In Java, we would write 26 /10 and the result would be 2, not 2.6.
currPower = 0 sum = 0 while (binaryNum!= 0) { currDigit = binaryNum % 10 //right most digit sum = sum + currDigit * 2 ^ currPower binaryNum = binaryNum / 10 //do the same with the digits to the left of the rightmost digit } //This code has syntax errors Now that you have some code, let's make sure that it is sound. Let's compile it.
Define the class in a Java file. Name the file the same name as the class name plus the ".java" extension. Define the main method. The following code shows the result of these steps. public class BinaryNum { public static void main(String[] args) { } }
You will need to add an output statement so you can see the results. As for input, just set the binaryNum variable in the code for now (this is called hardcoded input). public class BinaryNum { public static void main(String[] args) { int binaryNum = 101; //hardcoded input int currPower = 0; int sum = 0; while (binaryNum!= 0) { currDigit= binaryNum % 10 //right most digit if (currDigit == 1) { sum = sum + currDigit* 2 ^ currPower; } binaryNum = binaryNum / 10; //do the same with the digits to the left of the rightmost digit } System.out.println(binaryNum + "in decimal is " + sum); } }
You are likely to discover small syntactical errors when you try to compile your code. After successfully compiling, you might find that the program gives incorrect output. Then, you will need to accept that your code is incorrect, and try to determine the problem. However, it can be difficult to see the mistake if the same type of thinking that produced the error is used to see the error. You need to think like the machine to see the error. Go through your code line by line, and determine what went wrong. After fixing my code I had the following main method: public static void main(String[] args) { int binaryNum = 101; //hardcoded input int currPower = 0; int sum = 0; int currDigit; int copyOfBinNum = binaryNum; while (copyOfBinNum!= 0) { currDigit = copyOfBinNum % 10; //right most digit sum = (int) (sum + currDigit * Math.pow(2, currPower)); copyOfBinNum = copyOfBinNum / 10; currPower = currPower + 1; } System.out.println(binaryNum + " in decimal is " + sum); }
Handle InputTo handle input, we are going to use the scanner class. To use the scanner class we have to import it first. Classes often provide useful methods. By importing a class, we gain access to these methods. For a more detailed instructions on how to use the scanner class read Input_using_Scanner . Import the scanner class. Do this by including the following line at the top of the Java file, before the class definition. The line tells the compiler where to find the scanner class. import java.util.Scanner; Declare and instantiate the scanner class. Because we want to read from the terminal as opposed to a file, instantiate the scanner class with System.in as a parameter. System.in represents the terminal. You can give the scanner class any name that is a valid identifier; you don’t have to use “aScanner”. Scanner aScanner = new Scanner(System.in); Now that we have an instance of the scanner in the code we need to decide how to use it. Before we can choose which method to use, we need to decide how we want to store our input. Storing the numbers as a string would prevent us from being able to use remainder and integer division to convert the number to binary. We must store the number as an integer. However, there are two types of primitive integer types: int and long. A long is a primitive type for storing integers with twice as much storage space (from -2^64 to (2^64)-1), where as an int goes from -2^32 to (2^32)-1). Longs store larger integer values than int. For this example, you should store the inputted number as a long. By storing the number as a long we are less likely to encounter the problem of overflow. Overflow is exactly like it sounds, the number is too big for the variable to store. You will have to declare the variable that stores the input as a long instead of an int, thus: long binaryNumber Once you have chosen what type of variable to store the input in, choosing the appropriate input method is trivial. If you decided to store the input as a long, use the nextLong() method in order to read in a long from the terminal. If you decided to store the input as an int, use the nextInt() method. The following line shows how to store the input in your input variable using the Scanner class. binaryNumber = aScanner.nextLong(); Finally, we need to replace the hardcoded input with actual input. The only reason we used hardcoded input is to allow us to test our program before we implement input. In this case, hardcoded input is a form of scaffolding, a part of the code you use when developing, but that is not part of the final product. So get rid of the hardcoded input. Replace the following line: int binaryNumber = 101; //hardcoded input with binaryNumber = aScanner.nextLong();
Add a LoopFrom the program specification, we know that we need a loop. Determine the kind of loop. The two types of loops are for-loops and while-loops. Use a for-loop if you can determine in advance, how many times the loop will run. For example, if you need to print out each element in an array then use a for-loop. In this case, we do not know how many times the user will input binary numbers. Therefore, use a while-loop. Specify the termination condition of the loop. From the program specification, we know we need to stop when the user inputs -1. Expressed using the word while, we need to continue prompting for input while the input is not -1. while(binaryNumber != -1) { //place code to repeat here }
Solution to Exercises101 = 5, 1000 = 8, 1101 = 13, 10101 = 21. | ||||||||||||||||||||||||||
Code |