---
comments: true
difficulty: 简单
edit_url: https://github.com/doocs/leetcode/edit/main/solution/0100-0199/0191.Number%20of%201%20Bits/README.md
tags:
- 位运算
- 分治
---
# [191. 位1的个数](https://leetcode.cn/problems/number-of-1-bits)
[English Version](/solution/0100-0199/0191.Number%20of%201%20Bits/README_EN.md)
## 题目描述
编写一个函数，获取一个正整数的二进制形式并返回其二进制表达式中 设置位 的个数（也被称为汉明重量）。
示例 1：
输入：n = 11
输出：3
解释：输入的二进制串 1011 中，共有 3 个设置位。
示例 2：
输入：n = 128
输出：1
解释：输入的二进制串 10000000 中，共有 1 个设置位。
示例 3：
输入：n = 2147483645
输出：30
解释：输入的二进制串 11111111111111111111111111111101 中，共有 30 个设置位。
提示：
进阶：
## 解法
### 方法一：位运算
利用 `n & (n - 1)` 消除 `n` 中最后一位 1 这一特点，优化过程：
```txt
HAMMING-WEIGHT(n)
r = 0
while n != 0
n &= n - 1
r += 1
r
```
以 5 为例，演示推演过程：
```txt
[0, 1, 0, 1] // 5
[0, 1, 0, 0] // 5 - 1 = 4
[0, 1, 0, 0] // 5 & 4 = 4
[0, 1, 0, 0] // 4
[0, 0, 1, 1] // 4 - 1 = 3
[0, 0, 0, 0] // 4 & 3 = 0
```
#### Python3
```python
class Solution:
def hammingWeight(self, n: int) -> int:
ans = 0
while n:
n &= n - 1
ans += 1
return ans
```
#### Java
```java
public class Solution {
// you need to treat n as an unsigned value
public int hammingWeight(int n) {
int ans = 0;
while (n != 0) {
n &= n - 1;
++ans;
}
return ans;
}
}
```
#### C++
```cpp
class Solution {
public:
int hammingWeight(uint32_t n) {
int ans = 0;
while (n) {
n &= n - 1;
++ans;
}
return ans;
}
};
```
#### Go
```go
func hammingWeight(num uint32) int {
ans := 0
for num != 0 {
num &= num - 1
ans++
}
return ans
}
```
#### TypeScript
```ts
function hammingWeight(n: number): number {
let ans: number = 0;
while (n !== 0) {
ans++;
n &= n - 1;
}
return ans;
}
```
#### Rust
```rust
impl Solution {
pub fn hammingWeight(n: u32) -> i32 {
n.count_ones() as i32
}
}
```
#### JavaScript
```js
/**
* @param {number} n - a positive integer
* @return {number}
*/
var hammingWeight = function (n) {
let ans = 0;
while (n) {
n &= n - 1;
++ans;
}
return ans;
};
```
#### C
```c
int hammingWeight(uint32_t n) {
int ans = 0;
while (n) {
n &= n - 1;
ans++;
}
return ans;
}
```
#### Kotlin
```kotlin
class Solution {
fun hammingWeight(n: Int): Int {
var count = 0
var num = n
while (num != 0) {
num = num and (num - 1)
count++
}
return count
}
}
```
### 方法二：lowbit
`x -= (x & -x)` 可以消除二进制形式的最后一位 1。
同 [剑指 Offer 15. 二进制中 1 的个数](https://github.com/doocs/leetcode/blob/main/lcof/面试题15.%20二进制中1的个数/README.md)
#### Python3
```python
class Solution:
def hammingWeight(self, n: int) -> int:
ans = 0
while n:
n -= n & -n
ans += 1
return ans
```
#### Java
```java
public class Solution {
// you need to treat n as an unsigned value
public int hammingWeight(int n) {
int ans = 0;
while (n != 0) {
n -= (n & -n);
++ans;
}
return ans;
}
}
```
#### C++
```cpp
class Solution {
public:
int hammingWeight(uint32_t n) {
int ans = 0;
while (n) {
n -= (n & -n);
++ans;
}
return ans;
}
};
```
#### Go
```go
func hammingWeight(num uint32) int {
ans := 0
for num != 0 {
num -= (num & -num)
ans++
}
return ans
}
```
#### TypeScript
```ts
function hammingWeight(n: number): number {
let count = 0;
while (n) {
n -= n & -n;
count++;
}
return count;
}
```
#### Rust
```rust
impl Solution {
pub fn hammingWeight(mut n: u32) -> i32 {
let mut res = 0;
while n != 0 {
n &= n - 1;
res += 1;
}
res
}
}
```
#### JavaScript
```js
/**
* @param {number} n
* @return {number}
*/
var hammingWeight = function (n) {
let count = 0;
while (n) {
n -= n & -n;
count++;
}
return count;
};
```
#### Kotlin
```kotlin
class Solution {
fun hammingWeight(n: Int): Int {
var count = 0
var num = n
while (num != 0) {
num -= num and (-num)
count++
}
return count
}
}
```