Count Bits Set to 1

EasyPython00:00

Practice interviewer

In session

5 left

00:00

Your question is Count Bits Set to 1. Start with the requirements on the right.

Run and submit as often as you like. When you're ready, talk me through your approach or go straight to the code.

You need to log in / sign up to run or submit.

Problem

Dropbox sync metadata can represent several file properties as individual bits in a nonnegative integer. Given an integer n, return the number of set bits, meaning the number of 1 values in its binary representation.

Implement the function without converting the number to a string or iterating through every position in a fixed-width representation. Aim for runtime proportional to the number of set bits rather than the total bit width.

Formal Specification

Input: A nonnegative integer n.
Output: An integer equal to the number of set bits in n.
The value 0 has zero set bits.
Treat n as an unsigned value. Inputs do not contain negative numbers.

Constraints

0 <= n <= 2^63 - 1
Do not convert n to a string
Do not use a built-in population-count operation
The preferred runtime is O(k), where k is the number of set bits

Function Signature

def count_set_bits(n):

Your solutionPython 3

You need to log in / sign up to run or submit.

Run your code to see test output