Coding challenge solution: Counting the number of bits equal to one in a binary representation of a number

August 1, 2020

algorithm

I am a big fan of coding challenges, so for the past year or so I have been a member of codewars and whenever possible I tend to stop by their site to solve one or two challenges presented to me.

Given this fact, I have chosen to be sharing some of my solutions, so that maybe somebody out there can get a helping hand, gain better insight or just see how the same problem they probably solved could have been done differently.

To the challenge.

Challenge

Write a function that takes an integer as input and returns the number of bits that are equal to one in the binary representation of that number. You can guarantee that input is non-negative.

Example: The binary representation of `1234` is `10011010010`, so the function should return `5` in this case

Solution

For this challenge, I will be using the JavaScript programming language, but before we write any code, I think it is better to break down how to solve this problem.

1. Convert the number given to its binary representation
2. Count the number of bits equal to one in the binary representation of the number given

Converting to binary

We shall be following the steps shown in this guide on how to convert to binary.

``````const divMod = function (dividend, divisor) {
return [Math.floor(dividend / divisor), dividend % divisor];
};

const toBinary = function (n) {
let [quotient, remainder] = divMod(n, 2);

if (quotient < 2) {
return quotient + '' + remainder;
}

const bits = [remainder];
while (quotient) {
[quotient, remainder] = divMod(quotient, 2);
bits.push(remainder);
}

return bits.reverse().join('');
};
``````

From the above code, we have two functions, each performing a unique role.
Let's first look at the `divMod` function. This function takes two parameters i.e. dividend and divisor and returns an array with the quotient and remainder.

``````divMod(8, 2); // [4, 0]
divMod(8, 3); // [2, 2]
divMod(10, 2); // [5, 0]
``````

Now the `toBinary` function, well, takes a decimal number and converts its binary representation as a string.

``````toBinary(2); // 10
toBinary(15); // 1111
toBinary(1234); // 10011010010
``````

Counting the number of bits

``````const countBits = function (n) {
.split('') // convert str to array e.g '1010' => ['1', '0', '1', '0']
.filter((bit) => bit === '1') // ['1', '0', '1', '0'] => ['1', '1']
.length; // size of returned array
};
``````

Finally, the `countBits` function that does the actual counting of `1` bits. Hopefully, the comments, convey what the function accomplishes.

``````countBits(0); // 0
countBits(2); // 1
countBits(3); // 2
countBits(7); // 3
countBits(15); // 4
countBits(1234); // 5
``````

You must be thinking, surely there must be a simpler way to convert a decimal number to a binary in JavaScript natively; well, there is, you could do the following:

``````// variable
const n = 10;
n.toString(2); // 1010
// literal number
10..toString(2); // OR (10).toString(2)
``````

The advantage with the native way of doing it in JavaScript is that you can use the same method to convert to octal, hexadecimal, and any other bases.

Alternative languages

PHP solution

``````function count_bits(\$num)
{
\$binary = decbin(\$num);

return count(array_filter(str_split(\$binary), function (\$bit) {
return \$bit === "1";
}));
}
``````

Python solution

``````def count_bits(num):
bits = list(bin(num)[2:])

return len(list(bit for bit in bits if bit == '1'))
``````

You can check out this github repository I created to host my solutions.

Thank you for reading and God bless.