“This is the 30th day of my participation in the First Challenge 2022. For details: First Challenge 2022.”

Day 52 2021.02.25

The number of ones

• Leetcode: leetcode-cn.com/problems/nu…
• Difficulty: Easy
• Method: bit operation

The title

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

The sample

• 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

prompt

• 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.

• The input must be of length32 的 Binary string 。

Conversion between bases

Change from non-decimal to decimal

• For example, converting an octal number to a decimal number is simply a weighted sum of each digit.
  • 645.3(8) = 6 * 10 ^ 2 + 4 * 10 ^ 1 + 5 * 10 ^ 0 + 3 * 10 ^ -1

Change from decimal to non-decimal

• Convert decimal toXBase number, you need to pairThe integer partandThe decimal partConvert separately.

The integer part

• Conversion mode: Divide the integer part of the decimal system each timeXUntil they become0, and record the remainder of each time, and reverse traverse the remainder of each time can be obtainedXBase representation.
• For example,

// Convert the decimal number 50 to binary
50 / 2 = 25 余 0
25 / 2 = 12 余 1
12 / 2 = 6  余 0
6  / 2 = 3  余 0
3  / 2 = 1  余 1
1  / 2 = 0  余 1
Copy the code

• Reverse traversal of the remainder each time, therefore decimal number50The binary number is zero110010 (2)
• Note ⚠ ️: Special attention is required0andA negative numberIn the case

The decimal part

• Conversion: Multiply the decimal part of a decimal number each timeXUntil they become0(decimal part), and record each integer part, positive order traversal each integer part can be obtainedXBase representation.
• For example,

// Convert the decimal number 0.6875 to binary
0.6875 * 2 = 1.375The integer part1
0.375  * 2 = 0.75The integer part0
0.75   * 2 = 1.5The integer part1
0.5    * 2 = 1The integer part1
Copy the code

• The positive order traversal is1011, hence the decimal number0.6875Convert to binary0.1011 (2)

Conversion between other bases

• Convert it to a decimal number, and then to the target base.
• Neverthness however, conversion of binary numbers to octal and hexadecimal numbers does not need to undergo the above operations.
• A 1-bit octal number can be represented as a 3-bit binary number, and a 1-bit hexadecimal number as a 4-bit binary number

There are 6 kinds of bit operations (and, or, xOR, inversion, left shift, and right shift)

• Among them, left shift and right shift are called shift operation, and shift operation is divided into arithmetic shift and logical shift.
• Of the above bit operations, only the inverse operation is unary, the rest are binary operations.

solution

• Decimal conversion to base 2 method, using the problem

/ * * *@param {number} n - a positive integer
 * @return {number}* /
var hammingWeight = function(n) {
  // Divide by 2 every time, knowing that the result is 0
  let ans = 0;
  while(true) {
    if(n % 2= =1) ans++;
    // console.log(n);
    n = parseInt(n / 2);
    if(n == 0) return ans;
  }
  return ans;
};
Copy the code

bibliography

• leetbookBit operation, we recommend you can go to see