Leetcode 190. reverse binary bit operation /easy

---

1.Description

Invert given 32 The binary bit of an unsigned integer .

Tips ：

Please note that , In some languages （ Such as Java） in , There is no unsigned integer type . under these circumstances , Both input and output will be specified as signed integer types , And should not affect your implementation , Because whether integers are signed or unsigned , Its internal binary representation is the same .
stay Java in , The compiler uses binary complement notation to represent signed integers . therefore , Above Example 2 in , The input represents a signed integer -3, The output represents a signed integer -1073741825.

Advanced :
If you call this function more than once , How will you optimize your algorithm ？

---

2.Example

 Input ：11111111111111111111111111111101
 Output ：10111111111111111111111111111111
 explain ： Binary string of input  11111111111111111111111111111101  Represents an unsigned integer  4294967293,
      Therefore return  3221225471  Its binary representation is  10111111111111111111111111111111 .

---

3.Solution

1. Bit by bit

The code I wrote uses arrays , In fact, you don't need an array ：

public class Solution {
    
    // you need treat n as an unsigned value
    public int reverseBits(int n) {
    
        int[] nums = new int[32];
        for(int i=0;i<32;i++) {
    
        	if((n&1)==1) {
    
        		nums[i] = 1;
        	}
        	n = n>>>1;
        }
        int sum = 0;
        for(int i=0;i<32;i++) {
    
        	if(nums[i]==1) {
    
        		sum += 1<<(31-i);
        	}
        }
        return sum;
    }
}

Official explanation ：

public class Solution {
    
    public int reverseBits(int n) {
    
        int res = 0;
        for (int i = 0; i < 32; ++i) {
    
            res = (res << 1) | (n & 1);// or | The function of is equivalent to adding 
            n >>= 1;
        }
        return res;
    }
}

2. Divide and conquer

There is another way of not using loops , It's similar to merging and sorting .

Its idea is to divide and rule , Divide the number into two halves , Then exchange the order of the two halves ; Then divide the front and back halves into two halves , Exchange internal order …… Until the last exchange of order , The only numbers exchanged are 1 position .

With a 8 Bit binary digits as an example ：

The official solution here starts from the bottom of recursion , The first level of recursion exchanges all odd and even digits , Then the second layer exchanges two groups （ Odd arrays and even groups ） The location of ......

public class Solution {
    
    private static final int M1 = 0x55555555; // 01010101010101010101010101010101
    private static final int M2 = 0x33333333; // 00110011001100110011001100110011
    private static final int M4 = 0x0f0f0f0f; // 00001111000011110000111100001111
    private static final int M8 = 0x00ff00ff; // 00000000111111110000000011111111

    public int reverseBits(int n) {
    
    	// Because no matter what number and M1 There was one & After the operation , There is only odd information left 
    	//（ because M1 Even digits of are 0, One & All the words become 0 了 ）
    	// So or symbol | The previous operation means ： First the n Moves to the right one , Move even digit information to odd digit , And again M1 phase & Then we get the original even digits 
    	//（ Now it moves to odd digit , Equivalent to the exchange of even and odd numbers ）,| After that, it means to move the odd digit information to the even digit ,
    	// Two operations one | Then the exchange was completed . After that, the operation is similar , Refer to the picture above .
        n = n >>> 1 & M1 | (n & M1) << 1;
        n = n >>> 2 & M2 | (n & M2) << 2;
        n = n >>> 4 & M4 | (n & M4) << 4;
        n = n >>> 8 & M8 | (n & M8) << 8;
        return n >>> 16 | n << 16;
    }
}