【LeetCode-位运算】颠倒二进制位

题目描述

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

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

输入：11111111111111111111111111111101
输出：10111111111111111111111111111111
解释：输入的二进制串 11111111111111111111111111111101 表示无符号整数 4294967293，
     因此返回 3221225471 其二进制表示形式为 10111111111111111111111111111111 。

题目链接： https://leetcode-cn.com/problems/reverse-bits/

思路1

使用栈存储二进制序列，出栈就是序列的逆序，然后求和即可。

class Solution {
public:
    uint32_t reverseBits(uint32_t n) {
        uint32_t mask = 1;
        stack<int> s;
        for(int i=0; i<32; i++){
            if(mask&n) s.push(1); //要写成if(mask&n)，不能写if(mask&n>0)，或者if(mask&n!=0)
            else s.push(0);
            mask<<=1;
        }

        uint32_t ans = 0;
        int cnt = 0;
        while(!s.empty()){
            int bit = s.top(); s.pop();
            if(bit==1) ans += 1<<cnt;
            cnt++;
        }
        
        return ans;
    }
};

思路2

假如我们要把一个十进制数 n 翻转，则 ans = ans * 10 + n % 10。同样地，要将一个二进制数翻转需要 ans = ans * 2 + n % 2。
代码如下：

class Solution {
public:
    uint32_t reverseBits(uint32_t n) {
        uint32_t ans = 0;
        for(int i=0; i<32; i++){
            ans = (ans<<1) + (n&1);
            //ans = ans*2 + n%2;   // 这样写也行，上面那样写更快
            n>>=1;
        }
        return ans;
    }
};