---
title: 'LeetCode 191. Number of 1 Bits'
disqus: hackmd
---

# LeetCode 191. Number of 1 Bits

## Description

Write a function that takes an unsigned integer and returns the number of '1' bits it has (also known as the Hamming weight).

Note:

Note that in some languages, such as Java, there is no unsigned integer type. In this case, the input will be given as a signed integer type. It should not affect your implementation, as the integer's internal binary representation is the same, whether it is signed or unsigned.

## Example

Input: n = 00000000000000000000000000001011
Output: 3
Explanation: The input binary string 00000000000000000000000000001011 has a total of three '1' bits.

## Constraints

The input must be a binary string of length 32.

## Answer

此題可while一個一個bit往下推做檢查，若為1就cnt++。

int hammingWeight(uint32_t n){
    int cnt = 0;
    while(n){
        if(n&1){cnt++;}
        n>>=1;
    }
    return cnt;
}

若要加快效率，就可用 n & (n-1)，來將為1的bit消除。

int hammingWeight(uint32_t n){
    int cnt = 0;
    while(n){
        cnt++;
        n &= (n-1);
    }
    return cnt;
}

最後也可操作bit來做計算。

int hammingWeight(uint32_t n){
    n = (n & 0x55555555) + ((n>>1) & 0x55555555);
    n = (n & 0x33333333) + ((n>>2) & 0x33333333);
    n = (n & 0x0f0f0f0f) + ((n>>4) & 0x0f0f0f0f);
    n = (n & 0x00ff00ff) + ((n>>8) & 0x00ff00ff);
    n = (n & 0x0000ffff) + ((n>>16) & 0x0000ffff);
    return n;
}

## Link
https://leetcode.com/problems/number-of-1-bits/
###### tags: `Leetcode`