Will someone please explain to me how I get to this algorithm?

Question

public class Binary 
{ 
   public static void main(String[] args) 
   {  
// Print binary representation of n.
      int n = Integer.parseInt(args[0]); 
      int power = 1; 
      while (power <= n/2) 
         power *= 2; 
// Now power is the largest power of 2 <= n.
      while (power > 0) 
      {  
// Cast out powers of 2 in decreasing order.
         if (n < power) { System.out.print(0);             } 
         else           { System.out.print(1); n -= power; } 
         power /= 2; 
      } 
      System.out.println(); 
   } 
}

This algorithm takes a numerical argument from the user and returns the binary value of the user. I understood the code and everything, but I’d like to know how this algorithm works, because if I had to do it I wouldn’t know how to get/think about it. And if possible, I want to know which other algorithm can do the same (go from decimal to binary), explaining to me how and why it works, how I get/think about this algorithm, step by step.

Answer 1

First, as I mentioned in the commentary, binary numbers are composed by base 2.

This particular code I found very interesting the way it was made. I am not the best guy to make an explanation but I will try.

Binary numbers are composed of 1s and 0s. Each digit of a binary number represents "on" and "off". Each connected digite, the sum value increases by 1x2 n. That is, for a grouping of 4 digits we have the value of, up to, 15 in decimal.

1111 = 1x2 3 + 1x2 2 + 1x2 1 + 1x2 0 = 15

For the value of 1001, for example:

1001 = 1x2 3 + 0x2 2 + 0x2 1 + 1x2 0 = 9

Note that when the value is 0, we multiply by 2 n by 0.

So, what the algorithm you brought in does is the opposite.

In the first loop, which is the following:

int power = 1;
while (power <= n/2) 
   power *= 2; 

The goal of this loop is to discover the highest active bit value we can have. It already assumes that the entire input value is at least one digit. That is, at least the first digit will be 0 or 1, so the power = 1.

Every passage through power *= 2 means a digit to the left.

Imagine entry 18 in your program.

  0001 = 1 - ignorado pois sempre teremos uma iteração.
  0010 = 2 
  0100 = 4 
  1000 = 8
 10000 = 16
100000 = 32

In this case, we do not want the value of 32 because it is greater than our decimal value, that is, if this digit turned 1 (or was connected) it would be added 32 to our amount, resulting in an incorrect value.

As of this moment, we know that we will have to make 4 iterations to find the value 18.

• Checks if power value > 0
• Check the current value is less than the corresponding digit value
  • If true, it means the bit is off
    • We wrote 0
  • If it’s fake, it means the bit is on
    • We wrote 1
    • We decrease the value of the corresponding digit from the total value
  • Divide the value of the corresponding digit by 2.
• Repeats

Imagine now the algorithm running with the value 5 (the repetition is smaller).

• Arrow power=1
• Checks whether power=1 is less than or equal to 5 / 2 = 2 (remember that you are working with integers)
  • Multiplies power=1 by 2. We have power=2.
• Checks whether power=2 is less than or equal to 5 / 2 = 2
  • Multiplies power=2 by 2. We have power=4.
• Checks whether power=4 is less than or equal to 5 / 2 = 2
• Step out of the loop

In this case, we have 3 iterations

• Checks whether power=4 and greater than 0

  • Checks whether value=5 is less than `power=4'
    • Not true, in this case, the bit is not connected
  • Write 1 on screen (bit on)
  • Decrease of value=5 the value of power=4 resulting in value=1.
  • Divides the value of power=4 by 2 resulting in power=2 (we want the right bit)

• Checks whether power=2 and greater than 0

  • Checks whether value=1 is less than power=4
    • Write 0 because this bit is not connected
  • Divides the value of power=2 by 2 resulting in power=1

• Checks whether power=1 and greater than 0

  • Checks whether value=1 is less than power=1
    • Not true, in this case, the bit is not connected
  • Write 1 on screen (bit on)
  • Decrease of value=1 the value of power=1 resulting in value=0.
  • Divides the value of power=1 by 2 resulting in power=0

• Checks whether power=0 is greater than 0

• Step out of the loop

In this case, each writing resulted in 101 which means number 5, as we wish.

---

In short

See that the iteration starts by checking each bit from left to right.

If the number is 5, through the first loop you find that there will be at most 3 digits that participate in this number, because if the 4 digit is turned on it would result in a number greater than 5 (since its corresponding value is 8).

Then, check the 3° bit that has as value 4. If it is greater than or equal to the desired value, it is turned on, ie, composing the number 5. As the number is part, it is turned on (typing 1 on screen) and we decrease the value 5 the corresponding value, with 1 remaining.

Checks the 2° bit that has as value 2. If it is greater than or equal to the desired value, it is on, that is, composing the number 5. In this case, it is smaller (since the remainder was 1), then the bit is not on and does not compose the number.

Checks the 1° bit that has as value 1. If it is greater than or equal to the desired value, it is connected, that is, composing the number 5. In this case, it is equal, that is, the value corresponding to that bit composes the number 5. We decrease from the value 1 that we currently have by the corresponding value, remaining 0.

So we have the value of 4 + 1 forming the number 5.

---

If you’re familiar with C#, take a look at this running code.

static void Main(string[] args)
{
    int value = Int32.Parse(Console.ReadLine());

    StringBuilder binary = new StringBuilder();

    int totalBit = 1;
    int power = 1;
    while (power <= (value / 2))
    {
        power *= 2;

        Console.WriteLine($"{ power } pode fazer parte de { value }");
        totalBit++;
    }

    int total = 0;
    int bit = totalBit;
    while (power > 0)
    {
        if (value < power)
        {
            binary.Append("0");

            Console.WriteLine($"O bit { bit } ({ Math.Pow(2, bit) }) nao faz parte do numero");
        }
        else
        {
            binary.Append("1");

            total += power;
            value -= power;

            Console.WriteLine($"O bit de numero { bit } ({ Math.Pow(2, bit) }) faz parte do numero. Temos ate agora { total }");
        }

        power /= 2;
        bit--;
    }

    Console.WriteLine(binary.ToString());
    Console.ReadLine();
}

Available on .NET Fiddle if you want to test.

In this case, you have a little more detail about what is occurring. [

---

In fact, of course there are other ways of doing the same thing and in a simpler way but the explanation about the specific algorithm is this.

Probably my explanation was not very good since it is not my strong suit but I tried to clarify a little the ideas for you. If it’s not useful to someone, I can try to improve it or delete it.

Answer 2

You just need to understand how binary numbers work, then you assemble your algorithm in the best way independent of language, I for example program more in C#, I did an example like this:

    private static string DecimalToBinario(int numero)
    {
        string binario = ""; //VARIÁVEL DE AGREGAÇÃO QUE RECEBERÁ O BINÁRIO FINAL
        int dividendo = numero; //NESSE CASO A VARIÁVEL RECEBE UM VALOR COMOPARÂMETRO
        int resto; // NESSA ARMAZENO O RESTO QUE SERÁ AGREGADA NA VARIÁVEL BINÁRIO

        for (int i = dividendo; i > 0; i=dividendo) //LAÇO FOR QUE FAZ OS CALCULOS DE DIVISÃO POR 2
        {
            if (i == 1)                  //AQUI VERIFICO SE É
                resto = i;               //A ÚLTIMA DIVISÃO
            else                         //SE VERDADE 1 / 2 = 0,5 == 0 E 1
                resto = i % 2;           // PEGANDO O RESTO
            binario += resto.ToString(); // AGREGANDO RESTO NA VARIÁVEL BINÁRIO
            dividendo = i / 2;           // FAZENDO A DIVISÃO
        }
        return new string(binario.Reverse().ToArray());//AQUI EU INVERTO O STRING
    }

I created a method that takes an integer parameter and returns a string that can be used in the best way. I worked with three variables, then just analyze the code, as its is in java, the syntax is practically the same as C#, I can understand perfectly.

I will explain based on this user question: Quote. "This algorithm takes a numerical argument from the user and returns the binary value of the user. I understood the code and everything, but I’d like to know how this algorithm works, because if I had to do it I wouldn’t know how to get/think about it. And if possible, I want to know which other algorithm can do the same (go from decimal to binary), explaining to me how and why it works, how I get/think about this algorithm, step by step."

Here we see: How it works?

1. To know how it works you have really know this one way
   primitive with a calculator, I don’t know, you arrive at the answer.

*How to think/reach it? *

2. This step depends on the previous one, because your need to solve this problem would require of you this prerequisite. Certainly you would do a search to find out how to convert Decimal to binary!

And if possible, I want to know which other algorithm can do the same (go from decimal to binary)

3. This part to be made depends on the previous ones as well. In my case made simple algorithm that makes it. Here my friend you use your domain in the programming language you are using.

But look at my logic, in my case I thought so:

4. I need a decimal number;
5. In C# with a "for" loop;
6. store the rest by aggregating into a variable
7. store the result in another variable that will be used in the next division
8. I finally used the Reverse function to invert the step variable 3
9. ready the result will be used in the best way.