Count Bits Set to 1 | Dataford Interview Questions

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 question is Count Bits Set to 1. Start with the requirements in the Question tab.

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

Problem

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 question is Count Bits Set to 1. Start with the requirements in the Question tab.

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