By Long Luo

Here shows 6 Approaches to slove this problem: Cycle, Divide and Conquer, LowBit, Bit Set, Recursion.

# Brute Force: Cycle

Juse use a Loop to check if each bit of the binary bits of the given integer $n$ is $1$.

## Analysis

• Time Complexity: $O(k)$.
• Space Complexity: $O(1)$.

# API

Use API: $\texttt{Integer.bitCount}$.

## Analysis

• Time Complexity: $O(logk)$.
• Space Complexity: $O(1)$.

# Divide and Conquer

In fact, the API $\texttt{Integer.bitCount}$ is use the divide and conquer method.

## Analysis

• Time Complexity: $O(logk)$.
• Space Complexity: $O(1)$.

# LowBit

We can get the Low Bit $1$ by x & -x.

## Analysis

• Time Complexity: $O(k)$.
• Space Complexity: $O(1)$.

# BitSet

We can change the lowest $1$ of the binary bits of $n$ to $0$ by using x &= (x - 1).

## Analysis

• Time Complexity: $O(logn)$.
• Space Complexity: $O(1)$.

# Recursion

A recursion version of the previous method.

## Analysis

• Time Complexity: $O(logn)$.
• Space Complexity: $O(1)$.

All suggestions are welcome.
If you have any query or suggestion please comment below.
Please upvote👍 if you like💗 it. Thank you:-)

Explore More Leetcode Solutions. 😉😃💗