As I wrote here before, I do a lot of professional interviews, and I discovered that the best questions have more than one solution to them. While having an ideal solution to a problem, you can still ask the interviewees for other ways for the solution and putting extra constraints that can help guide them in either direction (maybe to check their creativity, or if they knew the question beforehand). One of the questions that fit this requirement is the “count the 1’s in the binary representation of an integer”.

This question has multiple answers, and I will point 3 of them here.

  1. Convert the number into a binary, and on the way, count the 1’s. In order to convert an integer into a binary, you divide the number by 2, write the reminder and so on. Each iteration, you add an if clause that checks whether it’s 1 or 0. This solution will work for practically all programming languages and scripts. Check out the binary conversion algorithm here.
  2. A one-liner solution, in a higher level language like Java:  int count = StringUtils.countMatches(Integer.toBinaryString(int i), "1");
  3. Last, but not least, Bitwise operations. As the question is actually counting the bits of the number, Bitwise operations are called for. In this solution, we use the operator & to check whether the last bit of the number is 1, (i.e 10101101 & 1 returns 1, you may think of it as 10101101 & 0000001 and because only the last bit is 1, the result of this is just 1). The concept is to move the bits each time 1 to the right and count the result of the & operation, and keep doing this until our main number, that we’re shifting to the right is bigger than 0.
    An example of it in Java:

Hope you enjoyed this post, let me know in the comments below if there are more recommended ways of achieving this.

Leave a comment