# Number of 1 Bits
**Difficulty:** EASY
[External](https://leetcode.com/problems/number-of-1-bits)
Canonical: https://scaleengineer.com/dsa/problems/number-of-1-bits
**Patterns:** [Bit Manipulation](https://scaleengineer.com/dsa/patterns/bit-manipulation)
**Algorithms:** [Divide and Conquer](https://scaleengineer.com/algorithms/divide-and-conquer)
**Companies:** [AMD](https://scaleengineer.com/companies/amd), [Cisco](https://scaleengineer.com/companies/cisco), [Qualcomm](https://scaleengineer.com/companies/qualcomm), [Verkada](https://scaleengineer.com/companies/verkada), [Box](https://scaleengineer.com/companies/box)
---
## Problem
Given a positive integer `n`, write a function that returns the number of set bits in its binary representation (also known as the [Hamming weight](http://en.wikipedia.org/wiki/Hamming%5Fweight)).

**Example 1:**

**Input:** n = 11

**Output:** 3

**Explanation:**

The input binary string **1011** has a total of three set bits.

**Example 2:**

**Input:** n = 128

**Output:** 1

**Explanation:**

The input binary string **10000000** has a total of one set bit.

**Example 3:**

**Input:** n = 2147483645

**Output:** 30

**Explanation:**

The input binary string **1111111111111111111111111111101** has a total of thirty set bits.

**Constraints:**

* `1 <= n <= 231 - 1`

**Follow up:** If this function is called many times, how would you optimize it?

# Approaches
## Loop and Check
This is a straightforward approach where we iterate through each of the 32 bits of the integer. In each iteration, we check if the current bit is a '1' and shift the number to the right to process the next bit.
**Time:** O(k), where k is the number of bits in the integer (e.g., 32). Since k is a constant, this is technically O(1), but it performs a fixed number of iterations regardless of the input's properties. · **Space:** O(1)
**Pros:** Simple to understand and implement.
**Cons:** Performs a fixed number of iterations (32), which is inefficient for numbers with few set bits (e.g., n=1).
### Explanation
This approach iterates through all 32 bits of the integer. The algorithm is as follows:

*   Initialize a counter `count` to zero.
*   Loop 32 times. In each iteration, we check the least significant bit (LSB).
*   The check is done using a bitwise AND with 1: `(n & 1)`. If the result is 1, it means the LSB is a set bit, and we increment `count`.
*   After checking the bit, we shift the number `n` one position to the right (`n >>= 1`) to expose the next bit at the LSB position for the subsequent iteration.
*   After the loop completes, `count` holds the total number of set bits.

```java
public class Solution {
    // you need to treat n as an unsigned value
    public int hammingWeight(int n) {
        int count = 0;
        for (int i = 0; i < 32; i++) {
            if ((n & 1) == 1) {
                count++;
            }
            // Using unsigned right shift is safer for negative numbers,
            // but for the given constraints (positive n), >> is fine.
            n = n >> 1;
        }
        return count;
    }
}
```
### Algorithm
*   Initialize a counter `count` to zero.
*   Loop 32 times, as we are dealing with 32-bit integers.
*   Inside the loop, use a bitmask `1` to check the least significant bit (LSB) of the number `n`. The expression `(n & 1)` will be `1` if the LSB is `1`, and `0` otherwise.
*   Add the result of this check to `count`.
*   Right-shift the number `n` by one position (`n >>= 1`) to move the next bit into the LSB position for the next iteration.
*   After 32 iterations, `count` will hold the total number of set bits.

## Bit Manipulation Trick (Brian Kernighan's Algorithm)
This approach uses a clever bit manipulation trick, `n & (n - 1)`, which has the property of unsetting the rightmost '1' bit of a number. We can repeatedly apply this operation and count how many times it takes for the number to become zero. This count equals the number of set bits.
**Time:** O(m), where m is the number of set bits. This is highly efficient as the number of loop iterations is equal to the number of set bits, which is often much smaller than the total number of bits (32). · **Space:** O(1)
**Pros:** Very efficient, as the number of iterations equals the number of set bits.
**Cons:** The logic of `n & (n - 1)` can be less intuitive for beginners.
### Explanation
This highly efficient method relies on a specific bitwise operation: `n & (n - 1)`.

This operation cleverly unsets (turns off) the rightmost '1' bit in a number. Let's see how:
*   When we subtract 1 from a number `n`, all the bits from the rightmost '1' to the LSB are flipped.
*   For example, if `n = 12` (binary `1100`), then `n - 1 = 11` (binary `1011`).
*   Performing a bitwise AND (`&`) between `n` and `n - 1` will make the rightmost '1' and all bits to its right zero. `1100 & 1011` results in `1000`.

The algorithm repeatedly applies this trick until the number becomes 0. The number of times we perform the operation is exactly the number of set bits.

```java
public class Solution {
    public int hammingWeight(int n) {
        int count = 0;
        while (n != 0) {
            // This operation unsets the rightmost set bit
            n = n & (n - 1);
            count++;
        }
        return count;
    }
}
```
### Algorithm
*   Initialize `count = 0`.
*   Start a loop that continues as long as `n` is not equal to 0.
*   Inside the loop, apply the operation `n = n & (n - 1)` to unset the rightmost set bit.
*   Increment the `count` in each iteration.
*   Once `n` becomes 0, return `count`.

## Lookup Table (Caching for Follow-up)
This approach addresses the follow-up question: 'If this function is called many times, how would you optimize it?'. It involves pre-calculating the number of set bits for a smaller range of numbers (e.g., all 8-bit numbers) and storing them in a lookup table. A 32-bit integer is then processed by breaking it into four 8-bit chunks, looking up the count for each, and summing them up.
**Time:** O(1) per query, after a one-time preprocessing cost of O(L), where L is the size of the lookup table (e.g., 256). · **Space:** O(L), where L is the size of the lookup table (e.g., 256).
**Pros:** Extremely fast for repeated calls, achieving constant time performance per query.
**Cons:** Requires extra space for the lookup table.; Incurs a one-time setup cost for preprocessing.
### Explanation
This method, ideal for the follow-up question, trades space for time. It's extremely fast when the function is called frequently.

**1. Preprocessing (One-time Setup)**
First, we precompute the number of set bits for all possible 8-bit numbers (0 to 255) and store them in a lookup table (an array).

**2. Querying (Per Call)**
For any given 32-bit integer `n`, we can view it as four separate 8-bit chunks (bytes). We find the number of set bits in each chunk by looking up our precomputed table. The total count is the sum of the counts for these four chunks.

We can extract each 8-bit chunk using bitwise operations:
*   `n & 0xff`: Extracts the first byte (bits 0-7).
*   `(n >> 8) & 0xff`: Extracts the second byte (bits 8-15).
*   `(n >> 16) & 0xff`: Extracts the third byte (bits 16-23).
*   `(n >> 24) & 0xff`: Extracts the fourth byte (bits 24-31).

```java
public class Solution {
    // A static lookup table to store bit counts for numbers 0-255.
    private static final int[] BITS_IN_BYTE = new int[256];

    // A static initializer block to populate the table when the class is loaded.
    static {
        for (int i = 0; i < 256; i++) {
            // Using Brian Kernighan's algorithm to populate the table.
            int count = 0;
            int n = i;
            while (n != 0) {
                n &= (n - 1);
                count++;
            }
            BITS_IN_BYTE[i] = count;
        }
    }

    public int hammingWeight(int n) {
        // Sum the bit counts of the four bytes of the integer.
        return BITS_IN_BYTE[n & 0xff] +
               BITS_IN_BYTE[(n >> 8) & 0xff] +
               BITS_IN_BYTE[(n >> 16) & 0xff] +
               BITS_IN_BYTE[(n >> 24) & 0xff];
    }
}
```
### Algorithm
**Preprocessing:**
*   Create a table `cache` of size 256.
*   For each `i` from 0 to 255, calculate its Hamming weight and store it in `cache[i]`.

**Query:**
*   Given an integer `n`.
*   Extract the four 8-bit chunks of `n` using bitwise AND and shifts.
*   Return the sum of the cached Hamming weights for each of the four chunks.

# Solutions
### 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 ; } }
```

### JavaScript

```javascript
/** * @param {number} n - a positive integer * @return {number} */ var hammingWeight =
  function (n) {
    let ans = 0;
    while (n) {
      n &= n - 1;
      ++ans;
    }
    return ans;
  };

```

### Python

```python
class Solution:
    def hammingWeight(self, n: int) -> int: ans = 0 while n: n &= n - 1 ans += 1 return ans

```

### CPP

```cpp
class Solution {
public:
  int hammingWeight(uint32_t n) {
    int ans = 0;
    while (n) {
      n &= n - 1;
      ++ans;
    }
    return ans;
  }
};

```