leetcode_ 191_ 2021-10-15

leetcode_191_ position 1 The number of

This is a very simple topic , Here I would like to introduce its optimization solution .

Law 1 ：

Direct traversal 32 position , Use the bit operation to find the 1 Bit , And then use it oneNums To maintain the .

class Solution {
    
public:
    int hammingWeight(uint32_t n) {
    
        int oneNums = 0;
        for(int i = 0; i < 32; ++i){
     // Direct traversal n Every one of them 
            if((n >> i) & 1) // If the bit is 1
            oneNums++;
        }
        return oneNums; 
    }
};

Law two ：

This is the most direct and simple method , Its time complexity is O(N) ( Although it is traversal 32 Time , Can be viewed as O(1), But in order to distinguish from the following methods , It is thought here that O(N)), The space complexity is O(1).
We also have optimization schemes .
Here's a little tip ,Brian Kernighan Algorithm . utilize n & (n - 1) Will n Last digit of 1 become 0. Use this technique , We just need to keep n & n-1, until n be equal to 0. And here n become 0 The number of times experienced is 1 The number of .

class Solution {
    
public:
    int hammingWeight(uint32_t n) {
    
        //  Law two ：  utilize n & (n - 1)  Will n Last digit of 1 become 0
        int oneNums = 0;
        while(n){
    
            n &= n - 1; // Eliminate one bit 0, until n == 0
            oneNums++; 
        }
        return oneNums; 
    }
};

The time complexity is O(K),K yes n In Chinese, it means 1 The number of . The space complexity is O(1).
And we have more advanced methods .

Law three ：

This method is similar to dichotomy , Every bit in binary has no other meaning . And what we have to do is to give everyone something else ： Each bit in the binary represents 1 A counter , All we have to do is try to add up these counters , That's our answer .

• explain ：
  consider 3 This unsigned integer ,3 How many binary sequences are there 1 Well ？
  

Based on this idea , Here's the way .

class Solution {
    
public:
    int hammingWeight(uint32_t n) {
    
        // Law three ： Think of each bit as a counter 
        n = (n & 0x55555555) + ((n >> 1) & 0x55555555); 
        n = (n & 0x33333333) + ((n >> 2) & 0x33333333);
        n = (n & 0xf0f0f0f) + ((n >> 4) & 0xf0f0f0f);
        n = (n & 0xff00ff) + ((n >> 8) & 0xff00ff);
        n = (n & 0xffff) + ((n >> 16) & 0xffff);
        return n;
    }
};

• You may not understand what this code is doing , Don't worry. . Let's take a look at the characteristics of these numbers .
  

n & 0x55555555 Is to count the low order of every two digits 1 The number of .
(n >> 1) & 0x55555555 It is to calculate the high order of every two digits 1 The number of .
Add it up and you get the middle of every two digits 1 The number of .
then n & 0x33333333 Is to count every 4 One of the two lowest places 1 The number of .
(n >> 2) & 0x33333333 Is to calculate every 4 One of the two highest places 1 The number of .
The rest is the same .
The time complexity is O(1), The complexity of space is also O(1).

Law four ：( Entertainment Law )

I found this method in a book , The technique used is template meta programming . It just can't be used in this problem , Pure entertainment .

template<int N>
struct OneInBinary {
    
    enum {
    value = N % 2 + OneInBinary<N/2>::value };
};

template<>
struct OneInBinary<0> {
    
    enum {
    value = 0};
};

// Calling method 
OneInBinary<45>::value;