Coding challenge solution: Counting the number of bits equal to one in a binary representation of a number
August 1, 2020
algorithmI 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.
- Convert the number given to its binary representation
- 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) {
return toBinary(n) // convert to binary e.g 10 => '1010'
.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.