By Long Luo

This article is the solution 6 Approaches: Cycle, API, Divide and Conquer, Low Bit, Bit Set, Recursion of Problem 191. Number of 1 Bits.

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. 😉😃💗