Bit Manipulation Counting and shifting bits
116. Number of 1 Bits
You are given a 32-bit signed integer n. Return how many of its 32 bits are 1.
Count the bits the way a computer stores n: exactly 32 binary digits in two's complement. A
non-negative n is its usual binary form with zeros in front, so 5 is 00…00101 and has two 1 bits. A
negative n always has its top bit set. For example, −1 is stored as 32 ones, and −231 is a 1
followed by 31 zeros.
Every one of the 232 bit patterns is a possible input. In Python and JavaScript, n is an
ordinary number in the same range, and its bits are the same 32 bits.
Example 1
Input: n = 1000
6Explanation: 1000 = 512 + 256 + 128 + 64 + 32 + 8, so its binary form is 1111101000. Six of those digits are 1,
and the 22 zeros in front add nothing.
Example 2
Input: n = -8
29Explanation: −8 is stored as 29 ones followed by 000. The top bit is one of the 29, because −8 is negative.
Example 3
Input: n = -2147483648
1Explanation: The smallest 32-bit integer is a 1 followed by 31 zeros. Only the top bit is set.
Check your understanding
Work out the answer for this input before you write any code.
Constraints
-231 ≤ n ≤ 231 − 1
Clarifying questions
What you would ask an interviewer before writing any code.