This is a bit operation problem, the first time is a bit difficult for people who are not trained in science. The process of mastering basic knowledge is omitted here. Because the process itself might be a little bit harder than doing this. However, my purpose in writing this article is to introduce you, without any baggage!

Topic describes

Write a function that takes an unsigned integer as an input (in the form of a binary string) and returns the number of digits ‘1’ in its binary expression (also known as hamming weight).

Tip:

  • Note that in some languages, such as Java, there are no unsigned integer types. In this case, both input and output will be specified as signed integer types, and should not affect your implementation, because the internal binary representation of an integer is the same whether it is signed or unsigned.
  • In Java, the compiler uses binary complement notation to represent signed integers. Therefore, in example 3 above, the input represents the signed integer -3.

Example 1:

Input: 00000000000000000000000000001011 output: 3: input binary string in 00000000000000000000000000001011, a total of three for the '1'.Copy the code

Example 2:

Input: 00000000000000000000000010000000 output: 1: input binary string in 00000000000000000000000010000000, a total of a '1'.Copy the code

Example 3:

Input: 11111111111111111111111111111101 output: 31 explanation: input binary string in 11111111111111111111111111111101, a total of 31 as' 1 '.Copy the code

Tip:

  • The input must be a binary string of length 32.

Advanced:

  • How would you optimize your algorithm if you called this function multiple times?

Answer key

Because ampersand is only going to get zero in this case, just like this 11&00, 01&10, 01&00, they all get zero. That is, the digits of both sides of the ampersand must be 1 in order for the new binary to be 1, otherwise it will be 0. For a binary, if each digit is 0, the result will be a decimal 0!

With that in mind, we define a 32-bit binary number x with all zeros, and then place a cursor of 1 anywhere on it, and (&) with the input parameter n. The binary bits of the input parameter n may itself have at least one 1 or all zeros, depending on the description. Going back again, just to review the ampersand mechanism, the binary number x with a cursor (there is only one 1), the only case in which the and with n cannot be 0 is the binary number n with the cursor position of x, both of which happen to be 1.

So, based on the above analysis, the complete code comes out:

/ * * *@param {number} n - a positive integer
 * @return {number}* /
var hammingWeight = function(n) {
    let ret = 0;
    for (let i = 0; i < 32; i++) {
        if ((n & (1<< i)) ! = =0) { ret++; }}return ret;
};
Copy the code

Notice, there’s another point here.

1 << 0 = 1 / / 00001
1 << 1 = 2 / / 00010
1 << 2 = 4 / / 00100
Copy the code

<< is also a bit operation that moves binary data to the left. This direction is easy to remember, and you can visualize Angle brackets as arrows. The left side is the current value, the right side is the number of moves, it is relatively easy to calculate, you directly convert the value into binary form, and then according to the number of moves to the specified position, and then convert to decimal.

Complexity analysis

Time complexity: O(32), 32 bits of binary number, traversal 32 times.

Space complexity: O(1), the number of variables is constant.

Link: leetcode-cn.com/problems/nu…