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.

Example

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

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

Input/Output

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

    Constraints:
    0 ≤ n ≤ 231 - 1.

  • [output] integer

The Solution

Capture.PNG

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.

Advertisements

Leave a Reply

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

WordPress.com Logo

You are commenting using your WordPress.com 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 )

Google+ photo

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

Connecting to %s