In order to prepare for teaching computing, I’ve been reading Introduction to Computing by David Evans.
In the first chapter there is an excellent explanation of binary numbers using binary search trees. You can build a bitstring for the binary representation of a number by starting at the root (highest node on the tree) and comparing the number to the midpoints of a range of numbers that you are searching. If you answer a question with “yes” append “1″ to your bitstring, otherwise append “0″.
The number 6 would be “Yes”, “Yes”, “No” or 110.
I decided to implement the logic of this binary tree in Java.
private static String decimalToBinary(int input) {
if (input < 0 || input > 7) {
throw new IllegalArgumentException();
}
StringBuilder result = new StringBuilder();
if (input >= 4) {
result.append('1');
if (input >= 6) {
result.append('1');
if (input == 7) {
result.append('1');
} else {
result.append('0');
}
} else {
result.append('0');
if (input == 5) {
result.append('1');
} else {
result.append('0');
}
}
} else {
result.append('0');
if (input >= 2) {
result.append('1');
if (input == 3) {
result.append('1');
} else {
result.append('0');
}
} else {
result.append('0');
if (input == 1) {
result.append('1');
} else {
result.append('0');
}
}
}
return result.toString();
}This works for converting decimal numbers to binary strings. I think that writing a program like this might work as an exercise for secondary school students for learning about conditional statements in programming and binary numbers.
However, the range of inputs is severely limited (0 to 7 inclusive). I wrote another method and a recursive helper method that can take arbitrary non-negative decimals in the range of Java ints and return the corresponding binary number:
private static String decimalToBinaryRecursive(int input) {
if (input < 0) {
throw new IllegalArgumentException();
}
if (input == 0) {
return "0";
}
if (input == 1) {
return "1";
}
// Find how many bits we need.
int bits = (int)(Math.log(input) / Math.log(2)) + 1;
// Find the greatest number that can be represented with this many bits.
int max = (int)Math.pow(2, bits);
// We want to know how much to change this value by to search from the mid point.
int delta = max / -2;
StringBuilder result = new StringBuilder();
return decimalToBinaryRecursiveHelper(input, max, delta, result);
}
private static String decimalToBinaryRecursiveHelper(int input, int previousMidpoint, int delta, StringBuilder result) {
if (delta == 0) {
return result.toString();
}
int midpoint = previousMidpoint + delta;
if (input >= midpoint) {
result.append('1');
return decimalToBinaryRecursiveHelper(input, midpoint, Math.abs(delta) / 2, result);
} else {
result.append('0');
return decimalToBinaryRecursiveHelper(input, midpoint, Math.abs(delta) / -2, result);
}
}The recursive method is considerably more complex and would be much harder for a secondary school student to write. The mathematics might be unfamiliar for most secondary school students, particularly the code to do with logarithms. You could simplify the mathematics of that code with a while loop that compared increasing powers of 2 to the input. It might be a possible extension task for a gifted and talented student. It could also be a task for a lesson on recursive methods.
I can see that teaching computing will present challenges. There are an enormous number of toy programs that we can get students to create in order to learn about programming. However, in order to extend any of these tasks to make them more practical and interesting, it is very easy to set challenges that are rely on outside skills, knowledge and understanding that many secondary school students do not have.
The whole program with a main method for testing looks like this:
package decimaltobinary;
/**
* @author Robert Impey
*/
public class DecimalToBinary {
public static void main(String[] args) {
System.out.println("Simple Approach");
for (int i = 0; i <= 7; i++) {
System.out.printf("%d\t%s\n", i, decimalToBinary(i));
}
System.out.println("Recursive Approach");
int bits = 8;
for (int i = 0; i <= Math.pow(2, bits) - 1; i++) {
System.out.printf("%d\t%s\n", i, decimalToBinaryRecursive(i));
}
}
private static String decimalToBinary(int input) {
if (input < 0 || input > 7) {
throw new IllegalArgumentException();
}
StringBuilder result = new StringBuilder();
if (input >= 4) {
result.append('1');
if (input >= 6) {
result.append('1');
if (input == 7) {
result.append('1');
} else {
result.append('0');
}
} else {
result.append('0');
if (input == 5) {
result.append('1');
} else {
result.append('0');
}
}
} else {
result.append('0');
if (input >= 2) {
result.append('1');
if (input == 3) {
result.append('1');
} else {
result.append('0');
}
} else {
result.append('0');
if (input == 1) {
result.append('1');
} else {
result.append('0');
}
}
}
return result.toString();
}
private static String decimalToBinaryRecursive(int input) {
if (input < 0) {
throw new IllegalArgumentException();
}
if (input == 0) {
return "0";
}
if (input == 1) {
return "1";
}
// Find how many bits we need.
int bits = (int)(Math.log(input) / Math.log(2)) + 1;
// Find the greatest number that can be represented with this many bits.
int max = (int)Math.pow(2, bits);
// We want to know how much to change this value by to search from the mid point.
int delta = max / -2;
StringBuilder result = new StringBuilder();
return decimalToBinaryRecursiveHelper(input, max, delta, result);
}
private static String decimalToBinaryRecursiveHelper(int input, int previousMidpoint, int delta, StringBuilder result) {
if (delta == 0) {
return result.toString();
}
int midpoint = previousMidpoint + delta;
if (input >= midpoint) {
result.append('1');
return decimalToBinaryRecursiveHelper(input, midpoint, Math.abs(delta) / 2, result);
} else {
result.append('0');
return decimalToBinaryRecursiveHelper(input, midpoint, Math.abs(delta) / -2, result);
}
}
}This post contains content that was released with the following license:
http://creativecommons.org/licenses/by-nc-sa/3.0/us/
and is published with the same license.
