Before we get too technical, let's start with the following joke:
There are 10 types of people, those who understand binary, and those who don't.
For those of you who didn't understand the joke, please keep reading. I am sure it will make sense to you before this article comes to a close.
First, let's start with a little background on the topic of decimal and binary numbers. We are all familiar with the decimal number system (Also known as the base ten number system). Decimal numbers simply use the numbers in the set {0,1,2,3,4,5,6,7,8,9}. Every integer can be represented in the decimal number system as some combination of the numbers from 0 to 9. On the other hand we can also represent all integers in the binary number system. However, the binary number system is constructed entirely from the set {0,1}. Therefore if we are going to represent integers in binary, we can only use the numbers 1 and 0. As a result the decimal number 2 is represented as 10 in the binary number system (Now that you have made it to this point in the article, the joke in the beginning of this post should start to make sense).
The goal of this post is to show you how we can write a C++ program that we can give decimal numbers to, and in response, our program will convert the decimal number into it's binary representation.
Before we start writing code, let's develop a plan of attack. For our attack we will be using an algorithm that divides our decimal number by two. Each time we divide our decimal number in two, we will save the remainder in a list. Then we will perform the division on the remaining decimal number, until our remaining decimal number equals 0. If that was a little unclear, don't worry, this will make more sense with the following example:
Let's start with the number 23.
First we will divide our number by two, then stick the remainder in the front of a list. Let's do it.
23 / 2 = 11 Remainder 1
We will set the 11 aside, and stick the remainder in the front of a list. Since this is our first time, our remainder will be the only item in the list. Thus our list looks like this: [ 1 ].
Next we we will take the 11 from the first division, then once again divide by two, and stick the remainder in the front of our list.
11 / 2 = 5 Remainder 1
We once again got a remainder of 1, now lets put it in the front of our list with the remainder from the first step. Our list now looks like this [ 1, 1 ].
Now lets continue the same process with the left over 5 from the last step.
5 / 2 = 2 remainder 1.
Adding this remainder to the front of the list, we now get [ 1, 1, 1 ]
Now we perform the operation again on the remaining 2.
2 / 2 = 1 Remainder 0.
Now we add the remainder to the front of the list. Our list now looks like this [ 0 , 1, 1, 1 ].
Next, we will repeat the process on the remaining 1
1 / 2 = 0 Remainder 1
Great! The marks the end of the process. When we get to 0 Remainder 1, we add the remainder to the front of the list, and then we are done with the conversion. So adding our remainder of 1 to the front of the list we get [ 1, 0, 1, 1, 1 ]. Now, removing the commas and the brackets, our list is 10111. Therefore, the decimal number 23 is 10111 when converted to binary.
Let's try this again real quick with the number 13, but without all the dialog.
13 / 2 = 6 Remainder 1 -----> [ 1 ]
6 / 2 = 3 Remainder 0 ------> [ 0, 1 ]
3 / 2 = 1 Remainder 1 ------> [ 1, 0, 1]
1 / 2 = 0 Remainder 1 ------> [ 1, 1, 0, 1 ]
Now that we have reached 0 Remainder 1, we remove the brackets and get 1101. Thus, 13 in decimal has the form 1101 in binary.
Ok great! Now that we understand how to solve our problem, let's write some code that will perform this conversion for us for any positive integer that we give it.
Here is a screenshot of the C++ code that I wrote to solve this problem. I will explain how it is implementing the decimal to binary conversion algorithm below.
Also I have include the code in text form here for your convenience.
#include
#include
using namespace std;
void binaryConvert(int input);
int main()
{
for(int i = 0; i < 17; ++i)
{
cout << i << ":\t";
binaryConvert(i);
}
return 0;
}
void binaryConvert(int input)
{
list<int> binary;
int rem;
do{
rem = input % 2;
binary.push_front(rem);
input /= 2;
}while(input != 0);
for(auto it = binary.begin(); it != binary.end(); ++it){
cout << *it;
}
cout << endl;
}
Ok, now let's explain how the code works.
This section tells the preprocessor, that we will be needing to use the iostream and list libraries. If we didn't include these libraries, we wouldn't be able to use the "cout" or the "list" functionality that is written in our code. Including these libraries at the top, is a lot like adding all the code from the iostream and list libraries to our file, but without the clutter.
#include
#include
Next, we specify that our code is using the standard namespace using namespace std;. If we did not include this, we woud need to replace all or our cout and list statements with std::coutand std::list.
Now let's look at the main function.
int main()
{
for(int i = 0; i < 17; ++i)
{
cout << i << ":\t";
binaryConvert(i);
}
return 0;
}
The line void binaryConvert(int input); is a function prototype. It it a lot like saying, I will be using the following function in my code, but I am not going to define it until after I use it. If we call the function before defining it, we will get an error when compiling unless we include the prototype here first. Additionally, void says that the function does not return a value. binaryConvert is the name that I chose to call the function. I just as well could have called it "CrabNebula" if I wanted, but that wouldn't have made any sense so "binaryConvert" it is. Then inside the parentheses, (int input) says that the function will be given an integer when it is called, and to put the integer in a variable that is named "input". (Tip: You can think of a variable as a box that holds stuff for your program to use later).
The next part is the main function. It tells the program where to start. The int here says that the main function will return an integer value to the operating system when it is done.
int main()
{
Next we have a "for loop".
for(int i = 0; i < 17; ++i)
{
cout << i << ":\t";
binaryConvert(i);
}
The first part of the "for loop", for(int i = 0; i < 17; ++i) says we are about to repeat something. More specifically, the for loop is going to create an integer variable named "i" and initially give it a value of 0 (Think of a zero being placed in the "i" box). Then as long as the value stored in "i" is less than 17, repeat the loop. The ++i says to add 1 to the value stored in "i" at the end of each loop. Thus, we are setting up a loop that will repeat with the values 1,2,3, ... all the way up to 16.
Next, we have the instructions for the loop. This explains exactly what will happen each time the loop runs.
{
cout << i << ":\t";
binaryConvert(i);
}
The part of the loop that sayscout << i << ":\t"; is telling our program to print the value stored in "i", followed by a ":" and one tab of whitespace. The next line, binaryConvert(i); tells our program to call the "binaryConvert" function, (Which has not yet been defined) and provide it with the value that is stored inside of "i".
Finally, the program exits and returns a value of 0 to the operating system.
return 0;
}
Now the only thing remaining is to tell our program what the "binaryConvert" function does.
void binaryConvert(int input)
{
list<int> binary;
int rem;
do{
rem = input % 2;
binary.push_front(rem);
input /= 2;
}while(input != 0);
for(auto it = binary.begin(); it != binary.end(); ++it){
cout << *it;
}
cout << endl;
}
Once again, as I described above in the prototype, void binaryConvert(int input) says we are defining a function named "binaryConvert". The function will not return a value, and the function needs to be provided an integer value, which is to be stored in a variable named "input".
Next, we declare a list to hold our binary number.
The code list<int> binary;, says to go ahead and create a list that can hold integer values. Additionally, we are naming this list "binary".
Then, int rem; creates a new integer variable called "rem". The "rem" variable is where we will be temporarily storing our remainders.
Next, we have a do-while loop.
do{
rem = input % 2;
binary.push_front(rem);
input /= 2;
}while(input != 0);
A do-while loop tells our program to do the instructions at least one time, but to continue doing these instructions as long as the while argument is true. In our case our while argument is input != 0. This tells the program to continue repeating the instructions in the do section as long as the value in the input variable is not equal to 0. (Note: This is the dividing by 2 algorithm that I presented earlier in the article. When "input" equals zero, we are essentially at the 0 Remainder 1 step of the algorithm).
Ok, now we just need to discuss what is happening inside of this do-while loop. The first instruction in the loop is rem = input % 2; This says to divide the input variable by 2 and store the remainder in the variable "rem" (Note: % is called the modulus operator). Then the code binary.push_front(rem); is telling our list (which we named binary) to add the remainder to the front of the list. This is exactly what we were doing in our example towards the top of this article. Next, input /= 2; says to replace the input with the new value, just as we did in the example. (Clarification: if "input" was 45, then input /= 2; would be be the same as performing 45 / 2, which is 22 Remainder 1, but then throwing everything away except for the 22 and then replacing the old "input" value of 45 with the new "input" value of 22).
Once again, as previously mentioned while(input != 0); says to repeat the instructions in the do-while loop as long as "input" does not equal 0. (Note: Another way to think about this is that while(input != 0);says to quit the do-while loop when "input" equals 0).
Next we print the contents of the list to the terminal.
for(auto it = binary.begin(); it != binary.end(); ++it){
cout << *it;
}
The code for(auto it = binary.begin(); it != binary.end(); ++it) says to create an iterator named "it" and point it to the beginning of our list that we named "binary". (You can think of an iterator as an arrow that marks the item that we are looking at the list). Then as long as our iterator named "it" is not marking the end of our list, go ahead and repeat the instructions inside of the for loop. Also the ++i says to move the iterator one item forward at the end of the loop.
Each time we run through the loop we are simply running this code cout << *it;. This code says to print out the value of the item in our list that is currently being marked by our iterator. So essentially, what this for loop is doing, is printing out the digits of the remainders that we added to the front of our "binary" list. This is the binary representation of our decimal number passed into the "binaryConvert" function!
The last thing we do in our function is cout << endl; which just prints a new line to the terminal. (That way, each time our "binaryConvert" function is called, it prints on a new line).
Ok now the code has been explained. Let's give it a test run.
Here I have a Bash terminal open and typing the ls command shows me that my program convert.cpp is in my working directory.
Now let's compile the code with the command g++ -std=c++11 convert.cpp -o convert. This command says to compile the file named "convert.cpp" as C++11 and to name the executable that it produces "convert".
The command causes our prompt to drop down to the next line without any errors. Therefore, compiling is successful!
Now if we run the ls command one more time we can see our new executable named "convert" displayed in red below.
Now let's run the executable by entering ./convert.
On the left hand side we can see the numbers from 0 through 16, and on the right hand side we can see the binary representation of each of these numbers. Mission Accomplished! Freaking Awesome! I love Programming!
If you enjoyed this article, please share, and come back for more great content!
I'll be back soon with more awesome, math, science and programming content! See you then!