How to Solve ‘numberof1Bits’ in CodeFights

The Problem

Note: Avoid using built-in functions that convert integers to their binary representations. Write the solution that uses O(k)operations per test, where k is the number of bits set to 1.

Write a function that takes an unsigned (positive) integer and returns the number of 1 bits its binary representation contains. This value is also known as the integer’s Hamming weight.


For n = 13, the output should be
numberOf1Bits(n) = 3.

13 is represented in binary as 1101, so the function should return 3.


  • [time limit] 4000ms (py)
  • [input] integer n

    0 ≤ n ≤ 231 - 1.

  • [output] integer

The Solution


The Explanation

The first line goes to the leftmost bit of an integer (integers are usually 4-bytes=32 bits) then every time there is a 1 bit in n (we check this by bitwise AND operation between n and j = 00….1 .. 00000 that has only one 1 in it) we count it. Then, return the count.


Leave a Reply

Fill in your details below or click an icon to log in: Logo

You are commenting using your account. Log Out /  Change )

Google+ photo

You are commenting using your Google+ account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )


Connecting to %s