One Byte at a Time: Binary String to Int

Problem 

Binary Numbers from string to number, from in, from binary number to int, and from an int to binary.

Difficulty: Sophomore

The string example is the easiest so I recommend that one first. Assume the input is always in the format of a binary number “101”, “10101”, and so on. Taking that input returns the value of this number in binary. No negatives or anything like that are expected. 

Input/Output

Input :  “10111"
Output : 23

test cases

“10” : 2
“101” : 5
“10010101010” : 1194

Then take an int in the form of binary and translate its value

Input/Output

Input :  10111
Output : 23

test cases

10 : 2
101 : 5
10010101010 : 1194 //this wouldn't really work because it thinks its a long but I think you get the idea

Input/Output

Input :  “10111"
Output : 23

test cases

“10” : 2
“101” : 5
“10010101010” : 1194

Now that we understand the algorithm and how to write code with it we can try a harder example an int to binary

Input : 50
output : 110010

Testcase 

2: 10
101 : 5
10010101010 : 1194

Solution

For these problems it is encouraged to look at how you would solve the problem yourself and translate it into code. Know exactly what you are being asked and understand any background.

Background:

Binary this is simply 0s and 1s I think every student should be able to read a number in binary. I would love to go over this in a future article but for now just understand that binary is 1 for a value and 0 for no value. From 2 ^n-1 where n is the amount of ones and zeros. For example 101 says  2^2 + 2^1-1 4+1 5 100 is 4 and 1 is 5. 100 has three spaces and one has one. This formula makes it easy to translate any number, now we need to write our algorithm.

1. find the 1 or base value
2. Count the bases to that 1
3. Add that value to the next 1

This is clearly recursive by nature.

public static int BinaryString(string bi)
{
     // find index of one ^ 2 -1
     if (bi.Length <= 1)
     {
          if (bi.Equals("1")) { return 1; } else { return 0; }
     }
     int i = indexof1(bi);
     if (i == -1)
     {
          return ((int)Math.Pow(2, bi.Length - 1));
     }

     return (int)Math.Pow(2, bi.Length - 1) + BinaryString(bi.Substring(i));
}
Code language: C# (cs)

First I need a base case if the string is just one one or one zero then I know I return its value.

Next I find the index of the one after our current index if there is no one other one I just return the answer.

If there is a new one we recursively add our current answer to the value of the next one and so on to get a full answer. We cut the remaining string using our index variable from earlier and the substring function.

static int indexof1(string x)
{
     for (int i = 1; i < x.Length; i++)
     {
          if (x[i] == '1')
          {
          return i;
          }
     }
//loop past our first one and return the next one else return -1
Code language: C# (cs)

The code for the binary int as an input is almost identical

Input :10111
output : 23

Again assume the input is only 0s and 1s though they are integers

The only real difference is that ints do not have a length so we need a function to find the length of a number you could also turn it to a string and count. 

 static int Spaces(int x){
     if (x <= 0) {
          return 0;
     }

     return 1+ Spaces(x/10);
}

Code language: C# (cs)

public static int BinaryInt(int bi)
{
     // 100 = 4
     if (Spaces(bi) <= 1)
     {
          return bi;
     }
     //  x-(spaces(bi) ^ 10           110 - 100 
     return ((int)Math.Pow(2, Spaces(bi)-1)) + BinaryInt(bi - (int)Math.Pow(10, Spaces(bi) - 1));
}
Code language: JavaScript (javascript)

We can also just return the value as if bi is less than or equal 1 its only 1 or 0

Then it would be the same return.

The final problem taking a number and translating it to binary requires a reverse engineered approach to the original problem.

Taking 5 we don’t know much of anything besides its binary equivalent is 101. We know we are converting to decimal a base 10 instead of base 2, which  we said binary a base 2 was 2^n-1. I would assume that means to convert to base 10 we can do 10^n-1, but what is n. Its the length of this number but the binary number. We need to find the greatest number that easily reverts to binary that this number is greater then, this will give us the amount of bases.

For example : 5

We know 5 is greater than 4 and less than 8

4 is the 3 base in binary 

0    0    0    0    0    0    0    0    0    space in binary
256  128  64   32   16   8    4    2    1    base value
                         …    3    2    1    base

We can say 10^2 4 is in the third base -1 = 2

100 is 4 in binary 

We return 4 + IntTo Binary(original – highest base)

5 -4 = 1

1 in decimal = 1 in binary

Base case 1 and 0 

public static int IntToBinary(int bi) {

     if (bi <= 1)
     {
          return bi;
     }
     int[] bis = {1,2,4,8,16,32,64,128,256};
     // this can be updated so that  bis is a list where the items from bi - x > therefore x= 2^loops 
     // add each to a list to have a great range

     int max = 0;
     for (int i =1; i < bis.Length; i++) {
          if (bi - bis[i] > 0) {
          max = i;
          }
          else if (bi - bis[i] == 0) {
          return (int)Math.Pow(10, i);
          }
     }

     return ((int)Math.Pow(10,max)) + IntToBinary(bi-bis[max]);
}
Code language: C# (cs)

Once you figure this out, find more efficient methods. The bis array is limited; there is an easy way to populate it with the max value divisible using a while loop and a list. 

Other solutions

When I researched other solutions, I found some interesting approaches that go beyond my basic algorithm.

https://stackoverflow.com/a/48298917

Conclusion

If you have a better solution feel free to send it to me: [email protected]. Questions about anything discussed are encouraged. Binary is easy to grasp and fundamental to programming concepts.