---
tags: leetcode
---

# [191. Number of 1 Bits](https://leetcode.com/problems/number-of-1-bits/)
---
# My Solution
## Solution 1: Loop and Bitwise-Shift Mask
### The Key Idea for Solving This Coding Question
### C++ Code

class Solution {
public:
    int hammingWeight(uint32_t n) {
        int cnt = 0;
        uint32_t mask = 0x1;

        for (int i = 0; i < 32; ++i) {
            if (n & mask) {
                ++cnt;
            }
            mask = mask << 1;
        }
        return cnt;
    }
};

### Time Complexity
$O(1)$
### Space Complexity
$O(1)$
## Solution 2: Bit Maniputation
### The Key Idea for Solving This Coding Question
We can repeatedly flip the least-significant `1`-bit of the number (`n`) to `0`-bit, and add `1` to the our counter (`numOnes`). As soon as the number (`n`) becomes `0`, we know that it does not have any more `1`-bits, and we return the counter (`numOnes`).
The key idea is to understand that for any number `n`, doing a bit-wise AND of `n` and `n−1` flips the least-significant `1`-bit of `n` to `0`.

n           = 01101000
n - 1       = 01100111
n & (n - 1) = 01100000
                  ^ The least significant 1-bit of n is flipped to 0.

### C++ Code

class Solution {
public:
    int hammingWeight(uint32_t n) {
        int numOnes = 0;

        while (n != 0) {
            n = n & (n - 1);
            ++numOnes;
        }
        return numOnes;
    }
};

### Time Complexity:
O(1)
### Space Complexity:
O(1)
# Miscellaneous
<!--
# Test Cases

00000000000000000000000000001011

00000000000000000000000010000000

11111111111111111111111111111101

-->