LeetCode220731_63、颠倒二进制位

颠倒给定的 32 位无符号整数的二进制位。

示例 1：

输入：n = 00000010100101000001111010011100
输出：964176192 (00111001011110000010100101000000)
解释：输入的二进制串 00000010100101000001111010011100 表示无符号整数 43261596，
     因此返回 964176192，其二进制表示形式为 00111001011110000010100101000000。

来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/reverse-bits
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

题解一、创建res变量，进行32位的循环遍历，每次先将res左移一位，作为接收结果的位，进行或|运算，与(n & 1)，这个运算可提取最后一位的数值，前面的位均为0，0000000000000000000000000000000x(x为1或0，取决于数值n的最后一位)。res左移一位后与此结果进行或运算即为拼接数据，0或1与前面31位为0的位置进行或均为原数值，最后一位新左移出来的0，与(n&1)结果进行或，得到数值拼接的效果。循环中，每次拼接后将n进行右移1位，直至32位全部完成，得到颠倒后的结果。

class Solution{
    public int reverseBits(int n){
        int res = 0;
        for(int i = 0; i < 32; i++){
            res = (res << 1) | (n & 1);
            n >>>= 1;
        }
        return res;
 
    }
}

题解二、分治，每相邻16位交换一次，之后8位，4位，2位，1位，即可完成颠倒，

分析两次交换，其余请自行理解。

第一次，每相邻16位进行一次交换，如何完成，将前16位放到最后，前面补0，后16位放到最前，后面补0，然后一拼，完成。具体步骤

①n >>>16(前16位放到最后，前面补0)

②n << 16(后16位放到最前，后面补0)

③拼接操作使用或|运算，右移后的前面为0部分与左移后的前面非0部分，进行或，右移后的后面非0部分，与左移后的后面为0部分进行或，与0或的位为其本身，相当于拼接。

第二次，每相邻8位进行一次交换，32位数据中，取到相邻的前8位和后8位，然后，拼接，完成。具体步骤

①(n & 0xff00ff00)取到每相邻数据的前8位

②(n & 0x00ff00ff)取到每相邻数据的后8位

③交换顺序进行拼接

(n & 0xff00ff00) >>> 8，前面的移动到后面

(n & 0x00ff00ff) <<< 8，后面的移动到前面

或|运算拼接

其余交换类似，主要请克服0x十六进制的表示意义，耐心一点点换成二进制（1,0）表示，动手移动一下，相信各位一定能理解的，加油。

class Solution{
    public int reverseBits(int n){
        n = (n >>> 16) | (n << 16);
        n = ((n & 0xff00ff00) >>> 8) | ((n & 0x00ff00ff) << 8);
        n = ((n & 0xf0f0f0f0) >>> 4) | ((n & 0x0f0f0f0f) << 4);
        n = ((n & 0xcccccccc) >>> 2) | ((n & 0x33333333) << 2);
        n = ((n & 0xaaaaaaaa) >>> 1) | ((n & 0x55555555) << 1);
        return n;
    }
}