Practice/Google/Leetcode 191. Number of 1 Bits

Leetcode 191. Number of 1 Bits

CodingOptional

Problem

Write a function that takes a non-negative 32-bit unsigned integer and returns the count of bits set to 1 in its binary representation. This count is also known as the population count or Hamming weight.

For instance, the number 11 in decimal is represented as 1011 in binary, which contains three 1 bits.

Requirements

1. Your function must accept a non-negative integer within the range [0, 2^32 - 1]
2. Return an integer representing the total count of 1 bits
3. The solution should handle the full 32-bit unsigned integer range
4. Consider optimization techniques for scenarios involving repeated function calls

Constraints

• 0 ≤ n ≤ 2^32 - 1
• The input is always a valid 32-bit unsigned integer
• Aim for O(k) time complexity where k is the number of 1 bits, or O(1) using lookup tables
• Space complexity should be O(1) for basic solutions

Examples

Example 1:

Input: n = 7 Output: 3 Explanation: 7 in binary is 0b00000111, which has three 1 bits

Example 2:

Input: n = 128 Output: 1 Explanation: 128 in binary is 0b10000000, which has one 1 bit

Example 3:

Input: n = 255 Output: 8 Explanation: 255 in binary is 0b11111111, which has eight 1 bits