This is the 23rd day of my participation in the August More Text Challenge

One, foreword

Hello everyone, this is the 12th article in a series of articles titled “Offer of the Day”.

In this series of articles, I will review the data structure and algorithm basis by brushing questions for practice, and I will also share my brushing process in the form of blog. If you happen to want to brush up on algorithms, encourage each other to learn. My algorithm foundation is weak, and I hope to make up for this loophole in the next two or three months. The language used for this brush is Java, and it is expected that Python will be used for the second brush.

  • Leetcode’s key Offer topic
  • Code cloud warehouse address

Second, the subject

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

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: n = 11 (00000000000000000000000000001011) the console input output: 3: input binary string in 00000000000000000000000000001011, a total of three for the '1'.Copy the code

Example 2:

Input: n = 128 (00000000000000000000000010000000) the console input output: 1: input binary string in 00000000000000000000000010000000, a total of a '1'.Copy the code

Example 3:

Input: n = 4294967293 (console enter 11111111111111111111111111111101, n = 3) in the part of the language output: 31: Input binary string in 11111111111111111111111111111101, a total of 31 as' 1 '.Copy the code

Third, the problem solving

3.1 Idea 1: Bitwise judgment

According to the & operation, there is an integer n, which has the following definition:

  • 1, if n & 1 ==0, then the last bit of n is 0
  • 2, if n &1 ==1, then the last bit of the binary of n is 1.

For example, execute the following code with values 1 and 0

System.out.println(3&1); //1 System.out.println(4&1); / / 0Copy the code

So we can do it bit by bit, 32 bits

<< : left shift operator, num << 1, equivalent to num multiplied by 2 >> : right shift operator, num >> 1, equivalent to num divided by 2 >>> : unsigned right shift, ignoring sign bits, empty Spaces complete with 0Copy the code
3.1.1 code
public static int Solution(int n){ int res =0; for (int i = 0; i < 32; i++) { System.out.println(3 &1); res +=(n>>i&1); } return res; }Copy the code
3.1.2 Execution Effect

3.1.3 complexity
  • Time complexity: O(k)O(k), k is the bit of int, fixed to 3232 bits
  • Space complexity: O(1)O(1)

3.2 Idea 2: Right-shift statistics

This is an optimization of train of thought 1. The high digit in train of thought 1 should also be checked in a loop. In fact, it can be avoided by moving n directly to the right.

3.2.1 code
public static int Solution2(int n){ int res =0; while (n! =0){ res+=(n>>=1&1); n>>>=1; } return res; }Copy the code
3.2.2 Execution Effect

3.3 Idea 3: Surprise solution, skillfully use N &(n-1)

If you subtract 1 from an integer, you change the rightmost 1 to 0, and if you have another 0 to the right, all the zeros become 1, and all the bits to the left remain the same, so you can use it to cancel out the rightmost 1 of the number N.

3.3.1 code
 public class Solution3 {
     public int hammingWeight(int n) {
         int res = 0;
         while(n != 0) {
             res++;
             n &= n - 1;
         }
         return res;
     }
 }
Copy the code
3.3.2 Execution Effect

3.3.3 complexity
  • Time complexity O(M)
  • Space complexity O(1)

3.4 Thought 4: API

 public static int Solution4(int n){
     return Integer.bitCount(n);
 }
Copy the code

Four,

The binary and bit operations, especially the n& (n-1) solution of the problem is more subtle.