Binary representation of integers

Recently I hacked away at this algorithm: entering an integer and outputting the binary representation of the integer.

For the sake of this example, let’s only work with positive integers.

Next, how do we break this down? Well, one thing I noticed about binary representation is the far right digit. Whether or not the integer we are trying to represent is even or odd will determine whether or not that far right digit is 0 or 1.

Each 0 or 1 in the binary representation represents a power of 2. I think of it as 1-yes or 0-no to adding that power of 2 to equate the integer we’re trying to represent.

From right to left, each 0 or 1 represents 2 to the nth power, where n starts from 0. Starting from the most far right digit, is 2 to the 0 power. 2^0 (2 to the power of 0) is equal to 1. (Any positive integer to the power of 0 will always equal 1)

2^0 = 1
2^1 = 2
2^2 = 4
2^3 = 8
2^4 = 16
2^5 = 32

Do you see the pattern?

So the binary representation of 5 is 101:

2^2 + 0 + 2^0 = 4 + 0 + 1 = 5

The binary representation of 4 is 100:

2^2 + 0 + 0 = 4 + 0 + 0 = 4

The binary representation of 11 is 1011:

2^3 + 0 + 2^1 + 2^0 = 8 + 0 + 2 + 1 = 11

Let’s look at basic arithmetic. Every even integer is divisible by 2. Every odd integer can be made even if you subtract 1 from it. The far right digit in binary representation is the only odd number, the 2^0 = 1. So this is the digit that will tell you if the integer being represented is even or odd. The far right digit will be 1 if it is odd, and it will be 0 if it is even. Look at my examples above. So let’s use this in the code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
var binary = function(n){
  if (n % 1 !== 0 || n < 0) {
    return 'Please enter a positive integer!';
  }
  var output = '';
  while (n > 0) {
    if (n % 2 === 0) {
      // insert a '0' in the far right place of the binary representation
      output = '0'.concat(output);
    } else {
      // insert a '1' in the far right place of the binary representation
      output = '1'.concat(output);
    }
    // somehow work with the other digits
  }
  return output;
}

I used the .concat() method because it keeps the order of strings I am gluing together in the correct order, right to left. At first I was making the mistake of adding the digit to the output:

output += '1';
output += '0';

but that appends the digit to the right of the string, so the representation would come out backwards. 11 would be represented as ‘1101’ instead of ‘1011’.

How do we get the rest of the digits though? A peculiar thing about binary is that for the digits that represent 2^1, 2^2, 2^3 and so forth, you can divide the number in half and floor the decimal (forcing it to round down regardless of the decimal value), and check if the halved and rounded down number is even or odd, deciphering if another 0 or 1 is needed. Let’s explore with 11:

Power of 2  | number  | number/2  | Math.floor(number/2)  | even/odd? | Binary Representation
2^0         | 11      | n/a       | n/a                   | odd       | '1'
2^1         | 11      | 5.5       | 5                     | odd       | '11'
2^2         | 5       | 2.5       | 2                     | even      | '011'
2^3         | 2       | 1         | 1                     | odd       | '1011'
2^4         | 1       | 0.5       | 0                     | neither   | we're done!

So let’s code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
var binary = function(n){
  if (n % 1 !== 0 || n < 0) {
    return 'Please enter a positive integer!';
  }
  var output = '';
  while (n > 0) {
    if (n % 2 === 0) {
      output = '0'.concat(output);
    } else {
      output = '1'.concat(output);
    }
    n = Math.floor(n/2);
  }
  return output;
}