leetcode-201_ 2021_ 10_ seventeen

leetcode-201_ Invert binary bit

Law 1 ：

Classic practice , It's also the simplest way . Create a new object ret To maintain the reversed results . Traverse n Of 32 position , If the first i Position as 1, that ret Of the (31-i) Position as 1. One small detail is if n The highest of 1 Has been traversed , Then you can finish ahead of time , Because the back is full of 0.

class Solution {
    
public:
    uint32_t reverseBits(uint32_t n) {
    
        uint32_t ret = 0;
        for(int i = 0; i < 32; ++i){
    
            if(!(n >> i)) // Optimize , If n >> i by 0, Then there is no need to recycle 
            break;

            if((n >> i) & 1){
    
                ret |= (1 << (31 - i)); 
            }
        }
        return ret;
    }
};

Law two ：

class Solution {
    
public:
    uint32_t reverseBits(uint32_t n) {
    
        n = ((n >> 16) & m1) + ((n << 16) & M1);
        n = ((n >> 8)  & m2) + ((n << 8)  & M2);
        n = ((n >> 4)  & m3) + ((n << 4)  & M3);
        n = ((n >> 2)  & m4) + ((n << 2)  & M4);
        n = ((n >> 1)  & m5) + ((n << 1)  & M5);
        return n;
    }
private:
    int m1 = 0xffff; // 0000 0000 0000 0000 1111 1111 1111 1111 
    int M1 = 0xffff0000;
    int m2 = 0xff00ff;
    int M2 = 0xff00ff00;
    int m3 = 0xf0f0f0f;
    int M3 = 0xf0f0f0f0;
    int m4 = 0x33333333;
    int M4 = 0xcccccccc;
    int m5 = 0x55555555;
    int M5 = 0xaaaaaaaa; 
};

Method 2 is a very clever algorithm . Invert a number , It's going to be the front 16 After bit becomes 16 position , after 16 Bit change to front 16 position . And then in each 16 In a , Before the 8 After bit becomes 8 position , after 8 Bit becomes Front 8 position . Then at every 8 Half and half of the bits are swapped again … Until the swapped bits become 1. We can easily implement this process by using masks .

The process of exchange requires a mask to implement , We will n >> 16 Before it needs to be cleared 16 The influence of position , So we need to & On
0000 0000 0000 0000 1111 1111 1111 1111,n << 16 Orthomorphism , Then add the two together to exchange the former 16 Position and back 16 position .
take n >> 8 Behind you , In order to eliminate the influence of unnecessary bits , need & On 0000 0000 1111 1111 0000 0000 1111 1111, Keep the second 1-8 Bit and 17-24 Digit number , The other bits are cleared . Moving left is the same . Then add the two together and swap the former 8 Position and back 8 position .
The following are the same .