Minimum Power-of-Two Steps to Zero

You are given a positive integer n. In one step you may either add a power of two to it or subtract a power of two from it: replace the current value v with v + 2^i or v - 2^i for any integer i >= 0.

Return the minimum number of steps required to make the value exactly 0.

Examples

Example 1

Input: n = 5
Output: 2
Explanation: 5 - 2^0 = 4, then 4 - 2^2 = 0. Two steps.

Example 2

Input: n = 21
Output: 3
Explanation: 21 - 2^0 = 20, 20 - 2^2 = 16, 16 - 2^4 = 0. Three steps.

Example 3

Input: n = 15
Output: 2
Explanation: Adding can beat subtracting: 15 + 2^0 = 16, then 16 - 2^4 = 0. Two steps.