Problem

As 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?

• Instead of having digits 0,1,...,9, in binary, we only have digits 0 and 1.
• So zero is 0, and the next number is represented by 1, but after that, we have no digit 2, so we have to represent the next number in the same way we do after we go past 9 in the decimal system: by 10.
• We continue in this way: 3 in binary is 11.
• Now what about 4? We can’t write 4 as 12 (because we only have 1 and 0 to work with, not 2). So we put a zero in the last position, and carry the 1. This would give 20, but again, we don’t have a digit 2, so we again carry the 1 and get 100 as the binary representation of 4.

Here are the first few numbers written in both decimal (normal) notation and binary:

Suppose we have a binary number (a sequence of zeroes and ones) and we want to convert it to a decimal number. To do this, we multiply the digit (0 or 1) in each position of the number by an increasing power of two the further we move left. So the value of the binary number 1011001 is

1 * 2^6 + 0 * 2^5 + 1 * 2^4 + 1 * 2^3 + 0 * 2^2 + 0 * 2^1 + 1 * 2^0 = 89

Program Specifications

• Write a program that takes input as an integer, interprets it as a binary number, and prints out its value as a decimal number.
• Get input using Scanner.
• Use integer division and remainder to extract digits from the input binary number.
• Assume the user only inputs numbers with digits 0 and 1.
• Use a loop so the user can continue to input binary numbers until they input -1 , then exit.
• Here is a sample run of the program:

  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.
  

Output

Use 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()).

Solution

The 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 Numbers

On 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. Anything multiplied by zero is zero, so we can remove the if-statement. Let's also add variables for clarity.

 exponent = 0
 sum = 0

 Take the rightmost digit ''d''. 
 sum = sum + d * 2^exponent
 Do the same with digits to the left of the rightmost digit.

Convert to Java-like Pseudocode

The 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 Modulus

In 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 Division

In 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 Code

You 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.

 exponent = 0
 sum = 0
 
 while (binaryNum!= 0)
 {
     rightmost = binaryNum % 10  //right most digit 
     sum = sum + rightmost * 2^exponent
     binaryNum = binaryNum / 10 //do the same with the digits to the left of the rightmost digit
 }

Now that you have some code, let's make sure that it is sound. Let's run it through the compiler.

Create the Structure of the Program

Now create 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 Code

Take 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 exponent = 0;
    int sum = 0;
 
    while (binaryNum!= 0)
    {
      rightmost = binaryNum % 10  //right most digit 
      sum = sum + rightmost * 2^exponent;
      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 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.

After fixing my code I had the following:

  public static void main(String[] args)
  {
    int binaryNum = 101;  //hardcoded input
    int exponent = 0;
    int sum = 0;
    int rightmost;
    int copyOfBinNum = binaryNum;

    while (copyOfBinNum!= 0)
    {
      rightmost = copyOfBinNum % 10;  //right most digit
      sum = sum + rightmost * 2^exponent;
      copyOfBinNum = copyOfBinNum / 10; //do the same with the digits to the left of the rightmost digit
    }
    System.out.println(binaryNum + " in decimal is " + sum);
  }

Now test your code with different values for binaryNum. Be sure to recompile after changing your code. Once you are satisfied, that your code correctly converts binary numbers to decimal numbers move to the next step.

Handling Input

Store the 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.

Import the Scanner Class

Include the following line at the top of the Java file, before the class definition.

import java.util.Scanner;

Declare and Instantiate the Scanner Class

Because 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 Method

Use nextLong() method in order to read in a long from the terminal.

binaryNumber = kbd.nextLong();

Replace Hardcoded Input

The 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 Loop

From 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 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.

while(/* Put termination condition here */)
{
} 

Determine the Termination Condition

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)
{
}

==Put

Solution to Exercises

101 = 5, 1000 = 8, 1101 = 13, 10101 = 21.

Code

Solution Code

import java.util.Scanner;

/**
 * PURPOSE: calculates the decimal version of a binary number.
 */
public class BinaryNum{


	public static void main(String[] args) {
		Scanner kbd = new Scanner(System.in);

		long binaryNumber, copyOfBinNum;	// input from the user.
		int decimalNumber; 		 	// output value.
		final int BASE = 2;			// binary base.
		int currDigit, currPower;		// values used in loops.

		// get input from the user.
		System.out.print("Enter a binary number:");
		binaryNumber = kbd.nextLong();

		// keep looping until -1 is encountered.
		while (binaryNumber != -1) {

			// reset values to 0, use copyOfBinNum for calculations.
			decimalNumber = 0;
			currPower = 0;
			copyOfBinNum = binaryNumber;

			// keep looping until all digits of copyOfBinNum are removed.
			while (copyOfBinNum > 0) {

				// get last digit and strip it off copyOfBinNum
				currDigit = (int) copyOfBinNum % 10;
				copyOfBinNum /= 10;

				// add to the running total if the digit is one
				if (currDigit == 1) {
					decimalNumber += Math.pow(BASE,currPower);
				}

				// increment the power of two for next loop.
				currPower++;
			}

			// output the right decimal value.
			System.out.println(binaryNumber + " in decimal is " + decimalNumber + ".");

			// get ready for next iteration of the loop.
			System.out.print("Enter a binary number:");
			binaryNumber=kbd.nextLong();
		}
		System.out.println("Programmed by [your name here].");
		System.out.println("End of processing.");


	}

}