An algorithm can be seen as a roadmap or a set of instructions to accomplish a well-defined task. In this section, we will build a simple example of one such algorithm to help us get started.
Number systems have different bases. Decimals numbers with a base of ten are what most of us are familiar with. Computers, on the other hand, use only ones and zeros (binary). Let's try to write some code that converts binary numbers to decimals.
Specifically, we want to develop an algorithm that accepts a string containing ones and zeros and returns an integer.
We can convert the binary string by following these steps:
- Start from the end of the string and process each character at a time. The position of each digit in the binary string corresponds to a decimal number in a sequence.
- To generate this sequence, you start from one and multiply by two every time, so one, two, four, eight, and so on (see Conversion Sequence row of Table 1.1). More formally, the sequence is a geometric progression that starts at one and progresses in a common ratio of two.
- We then apply the binary string as a mask on this sequence (seethe Binary String (Mask) row of Table 1.1).
- The result is a new sequence where the values are only kept if the corresponding position in the binary string has a value of one (see the Result row of Table 1.1).
- After applying the mask, we just need to sum up the resulting numbers together.
Conversion Sequence | 16 | 8 | 4 | 2 | 1 |
Binary String (Mask) | 1 | 0 | 1 | 1 | 0 |
Result | 16 | 0 | 4 | 2 | 0 |
Table 1.1: Binary to decimal masking
In the preceding example (Table 1.1), resulting total is 22. This is our decimal number corresponding to the binary number 10110.
Note
To design our algorithm, it's important to realize that we don't need to store the entire conversion sequence. Since we are processing one binary digit at a time (starting from the back), we only need to use the conversion number corresponding to the binary position we are processing.
Snippet 1.1 shows us how we can do this. We use a single conversion variable instead of a sequence and initialize this variable to the value of one. We then use a loop to iterate over the length of the binary string starting from the end. While iterating, if the digit at our current position is one, we add the current conversion variable to the final result. We then simply double the current conversion variable and repeat. The code snippet is as follows:
public int convertToDecimal(String binary) {
int conversion = 1;
int result = 0;
for (int i = 1; i <= binary.length(); i++) {
if (binary.charAt(binary.length() - i) == '1')
result += conversion;
conversion *= 2;
}
return result;
}Snippet 1.1: Binary to decimal. Source class name: BinaryToDecimal.
Note
Go tohttps://goo.gl/rETLfqto access the code.
Scenario
In aviation, the aircraft's transponders transmit a code so that they can identify one another. This code uses the octal system, a number system which has a base of 8. We have been asked to write a method to convert octal numbers into decimals. For example, the octal number 17 is represented as 15 in the decimal system.
Aim
To be able to adapt the algorithm shown in the previous section to be used in a different scenario.
Prerequisites
- Ensure that you have a class available on the following path:
- You will find the following method that needs implementing:
public int convertToDecimal (String octal)- If you have your project set up, you can run the unit test for this activity by running the following command:
gradlew test --tests com.packt.datastructuresandalg.
lesson1.activity.octaltodecimal*Steps for Completion
- The algorithms shown in Snippet 1.1 the preceding snippets of code can be adapted to work with octal numbers instead of binary.
- Change the base from two to eight. This can be done by changing the conversion multiplier variable inSnippet 1.1.
- Parse the digit being processed to convert it into an integer. This integer can then be multiplied by the conversion variable or result of the power function.
In this first section, we introduced the idea of algorithms by working on a simple example. It's important to note that for every problem multiple solutions exist. Choosing the right algorithm to solve your problem will depend on several metrics, such as performance and memory requirements.