The sample code in this article uses JavaScript, so you need basic knowledge of bit operations to read this article.

A, dry

Implement a function that takes an integer and outputs the number of 1s in the binary representation of that number. For example, 9 in binary is 1001 with two bits of 1. Therefore, if the input is 9, the function outputs 2.

Second, the solution

The easiest way to understand (which can cause an endless loop) :

The rightmost digit in the binary representation of an integer is 1. And then you move the whole number one to the right, so that the second rightmost integer is moved to the first rightmost integer, and then you determine if it’s a 1. We move it one bit at a time until this number becomes 0. For example, 9, or 1001, the design variable x=0, the last bit of 1001 is 1, x=x+1, so now x=1, when you move it right, it becomes 0100, the last bit is not 1, x stays the same, keep moving it right, it becomes 0010, x stays the same, then move it right again, x=x+1, x=x+1, then x=2, keep moving it right, 0000, then the integer is 0, So x ends up being 2.

So how do you tell if the rightmost part of an integer is 1? It’s easy, just bitwise and 1. Because the binary representation of the integer 1 is 0 except for the last digit, the value is 1 if the rightmost digit of the integer is 1, and 0 otherwise.

So we can write the following code:

function hanmingWeight(n) {
    let x = 0
    while(n) {
        if(1 & n) {
            x++
        }
         n = n >> 1
    }
    return x
}
Copy the code

This solution is stuck in an infinite loop for negative numbers, because when the input is negative, the highest complement after the right shift is 1, so n never becomes 0.

Conventional method

So to avoid getting stuck in an infinite loop, we can think of it the other way around, and since we have a problem with negative numbers moving to the right, we can move the 1 to the left, and then we can also compare each of the bits of n to.

function hanmingWeight(n) {
    let x = 0
    let flag = 1
    while(flag) {
        if(flag & n) {
            x++
        }
        flag = flag << 1
    }
    return x
}
Copy the code

This code terminates when flag overflows, that is, when flag moves to the left, it overflows the range of unsigned integers, truncates to 0, and the while loop terminates.

Try this yourself on the console:

Since bit 32nd is the sign bit, when bit 32nd is 1, the value generated after a << 2 becomes a large negative number, and a << 3 overflows, printing 0.

The bitwise operator requires that its operands be integers, represented as 32-bit integers rather than 64-bit floating-point types. The Definitive guide to JavaScript (original book, 6th edition)4.8.3

For integers that match, the first 31 of the 32 bits are used to represent the value of the integer. The 32nd bit is a numeric symbol: 0 for a positive number and 1 for a negative number. The bit that represents coincidence is called the sign bit. JavaScript Advanced Programming (3rd Ed.) 3.5.2

ideas

The third method requires something akin to a theorem, which is that subtracting 1 from an integer and doing a bitwise sum with it will turn the rightmost 1 in the binary representation of the integer into a 0. For example, 12, 1100, minus 1 from 1100, becomes 1011, and then the bitwise sum with 1100 becomes 1000, and then the bitwise sum with 1000 is 0111, and then the bitwise sum with 1000 is 0000. How many 1’s do I have in this number?

With this in mind we can write the following code:

function hanmingWeight(n) {
    let x = 0
    while(n) {
        n = n & (n -1)
        x++
    }
    return x
}
Copy the code

Iii. Reference materials

1. What is your job description

2. The Definitive JavaScript Guide (original book 6th edition)4.8.3

3. JavaScript Advanced Programming (3rd edition) 3.5.2

LeetCode link:Leetcode-cn.com/problems/er…

If you have any questions, please leave a message at ღ(´ ᴗ · ‘)