Hamming Weight

Hamming Weight

·

2 min read

According to wiki:

The Hamming weight of a string is the number of symbols that are different from the zero-symbol of the alphabet used.

The leetcode problem Number of 1 Bits is one type of Hamming weight problem. Let's see how to solve this.

Count char 1

In JavaScript, we can just convert the number into binary form, and count the number of 1.

function hammingWeight(n: number): number {
    return [...n.toString(2)].reduce((pre, cur) => cur === "1" ? pre + 1 : pre, 0);
}

Convert 10 base to 2 base

We can convert this 10 based number into 2 based number, and we can count the number of 1 in the process.

function hammingWeight(n: number): number {
    let count = 0;
    while (n > 0) {
        if ((n % 2) === 1) count++;
        n = ~~(n / 2);
    }
    return count;
};

Use mask

We could also shift the number right and test if the lease significant bit is 1.

function hammingWeight(n: number): number {
    let count = 0;
    for (let i = 0; i < 32; i++) {
        if ((n >> i) & 1) count++;
    }
    return count;
};

Bit-wise AND of n and n-1

For any number n, doing a bit-wise AND of n and n-1 flips the least-significant 1-bit in n to 0. We could use this technique.

function hammingWeight(n: number): number {
    let count = 0;
    while (n) {
        n &= n - 1;
        count++;
    }
    return count;
}