Difference between revisions of "Binary Nums"
ElsanussiM (Talk | contribs) m (pseudocode edit) |
ElsanussiM (Talk | contribs) m (made variable names in code segments consistent) |
||
Line 104: | Line 104: | ||
<pre> | <pre> | ||
− | + | currPower = 0 | |
sum = 0 | sum = 0 | ||
− | Take the rightmost digit | + | Take the rightmost digit currDigit. |
if d == 1 | if d == 1 | ||
− | sum = sum + | + | sum = sum + currDigit * 2 ^ currPower |
Do the same with digits to the left of the rightmost digit. | Do the same with digits to the left of the rightmost digit. | ||
</pre> | </pre> | ||
Line 142: | Line 142: | ||
Here is an example of my result. | Here is an example of my result. | ||
− | + | currPower = 0 | |
− | + | ||
sum = 0 | sum = 0 | ||
while (binaryNum!= 0) | while (binaryNum!= 0) | ||
{ | { | ||
− | + | currDigit = binaryNum % 10 //right most digit | |
− | sum = sum + | + | sum = sum + currDigit * 2 ^ currPower |
binaryNum = binaryNum / 10 //do the same with the digits to the left of the rightmost digit | 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. | Now that you have some code, let's make sure that it is sound. Let's compile it. | ||
Line 183: | Line 182: | ||
As for input, just set the binaryNum variable in the code for now (this is called '''hardcoded input'''). | As for input, just set the binaryNum variable in the code for now (this is called '''hardcoded input'''). | ||
− | + | ||
− | public class BinaryNum | + | public class BinaryNum |
− | { | + | { |
public static void main(String[] args) | public static void main(String[] args) | ||
{ | { | ||
int binaryNum = 101; //hardcoded input | int binaryNum = 101; //hardcoded input | ||
− | int | + | int currPower = 0; |
int sum = 0; | int sum = 0; | ||
while (binaryNum!= 0) | while (binaryNum!= 0) | ||
{ | { | ||
− | + | currDigit= binaryNum % 10 //right most digit | |
− | if ( | + | if (currDigit == 1) |
{ | { | ||
− | sum = sum + | + | sum = sum + currDigit* 2 ^ currPower; |
} | } | ||
binaryNum = binaryNum / 10; //do the same with the digits to the left of the rightmost digit | binaryNum = binaryNum / 10; //do the same with the digits to the left of the rightmost digit | ||
Line 203: | Line 202: | ||
System.out.println(binaryNum + "in decimal is " + sum); | System.out.println(binaryNum + "in decimal is " + sum); | ||
} | } | ||
− | } | + | } |
− | + | ||
==Fix your Code== | ==Fix your Code== | ||
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. | 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 | + | 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); | ||
+ | } | ||
− | |||
− | Now test your code with different values | + | Now test your code with different values of binaryNum. Be sure to recompile after changing your code and before testing it. Once you are satisfied, that your code correctly converts binary numbers to decimal numbers move to the next step. |
− | that your code correctly converts binary numbers to decimal numbers move to the next step. | + | |
==Handling Input== | ==Handling Input== | ||
− | + | ||
Line 250: | Line 244: | ||
===Use the Appropriate Method=== | ===Use the Appropriate Method=== | ||
+ | You will want to store the inputted number as a long. A long is a primitive type for storing integers with twice as much storage space as int. It can store larger integers than regular int. By storing, the number as a long we are less likely to encounter the horrible problem of '''overflow'''. | ||
+ | |||
+ | You will have to declare the variable that stores the input as a long instead of an int, thus: | ||
+ | long binaryNumber | ||
Use nextLong() method in order to read in a long from the terminal. | Use nextLong() method in order to read in a long from the terminal. | ||
binaryNumber = kbd.nextLong(); | binaryNumber = kbd.nextLong(); |
Revision as of 12:33, 31 March 2011
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
OutputUse System.out for output. Follow the format of the output shown above. 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()). |
| |||||||||||||||||||||||||
---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
SolutionThe greatest ways 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. 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 anything simpler. We can draw diagrams, write equations, and write pseudocode. We can always write Java code once we understand how to solve the problem. After reading the problem specifications, we have an idea about how to convert binary numbers to decimal numbers. By analyzing the formula in the problem specification, we get an even better idea. 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 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 d == 1 sum = sum + currDigit * 2 ^ currPower Do the same with digits to the left of the rightmost digit.
Convert to Java-like PseudocodeThe problem specification tells us vaguely how to process the input number: Use integer division and remainder to extract digits from the input binary number. The following is a thorough explanation of how to do that. 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, I'm willing to tell you the trick. 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, which is 26 ignoring the rightmost digit.
Transform the Pseudocode into Java CodeYou can continue improving the pseudocode slightly until you have replaced much of the English instructions with Java-like code. Here is an example of my result. 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. Create the Structure of the ProgramCreate a Java file. 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) { } } Test your CodeTake the code for converting numbers, and paste it into the main method. Then compile it and fix any errors. You may need to add semicolons, and declare variables. You will need to add an output statement so you can test your 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); } }
Fix your CodeYou 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); }
Handling InputImport the Scanner ClassInclude the following line at the top of the Java file, before the class definition. import java.util.Scanner; Declare and Instantiate the Scanner ClassBecause we want to read from the terminal, instantiate the scanner class with System.in as a parameter. Scanner kbd = new Scanner(System.in); Use the Appropriate MethodYou will want to store the inputted number as a long. A long is a primitive type for storing integers with twice as much storage space as int. It can store larger integers than regular int. By storing, the number as a long we are less likely to encounter the horrible problem of overflow. You will have to declare the variable that stores the input as a long instead of an int, thus: long binaryNumber Use nextLong() method in order to read in a long from the terminal. binaryNumber = kbd.nextLong(); Replace Hardcoded InputThe only reason we used hardcoded input, is to test our program without 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. Instead of: int binaryNum = 101; //hardcoded input Use: binaryNum = kbd.nextLong(); Add a LoopFrom the program specification, we know that we need a loop: Use a loop so the user can continue to input binary numbers until they input -1 , then exit. Determine the Kind of LoopThe 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. Determine the Termination ConditionFrom 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 |