🌕 🌗 190. 颠倒二进制位

难度: 🌕 🌗

问题描述

---

解法 1

public class Solution {
    // you need treat n as an unsigned value
    public int reverseBits(int n) {
        // 思路:
        // 2^0 * [31] + 2^2 * [30] + ... + 2^31 * [0]
        // 从低位开始依次判断是否为 1，若为 1 * 对应的 2 的 n 次方
        long res = 0;
        for(int i = 0; i < 32; i ++) {
            if((n & 1) == 1) {
                // System.out.println(i + "  " + res);
                res = res | (1 << (31 - i));
            }
            n >>= 1;
        }
        return (int)res;
    }
}

---

输出 1

---

解法 2 - 分治

public class Solution {
    // you need treat n as an unsigned value
    public int reverseBits(int n) {
        // 思路：
        // 优化 - 分治
        // 假设现在有 8 位二进制表示的数，二进制表示为 a b c d e f g h
        // 要想获得反转结果 h g f e d c b a
        // 可以采用以下方式：
        // 1. 以 2 位 为单位进行互换 => b a | d c | f e | h g
        // 2. 以 4 位 为单位互换 => dc ba | hg fe
        // 3. 以 8 位 为单位互换 => hg fe dc ba 从而得到结果
        // 32 位同理
        int tmp2 = 1431655765; // 01010101010101010101010101010101
        int tmp4 = 858993459; // 00110011001100110011001100110011
        int tmp8 = 252645135; // 00001111000011110000111100001111;
        int tmp16 = 16711935; // 00000000111111110000000011111111;
        int tmp32 = 65535; // 00000000000000001111111111111111;

        // 以 2 位为单位进行互换，即 获取奇数位 a & 偶数位 b 后，将 b 调换到 a 的前面
        int odd = (n >>> 1) & tmp2;
        int even = n & tmp2;
        even <<= 1; // 偶数位左移，奇数位已经右移了
        int res = odd | even;
        // 以 4 位为单位互换
        odd = (res >>> 2) & tmp4; // res 右移可以看出，odd 位已经到了低位处
        even = res & tmp4;
        even <<= 2;
        res = odd | even;

        odd = (res >>> 4) & tmp8;
        even = res & tmp8;
        even <<= 4;
        res = odd | even;

        odd = (res >>> 8) & tmp16;
        even = res & tmp16;
        even <<= 8;
        res = odd | even;

        odd = (res >>> 16) & tmp32;
        even = res & tmp32;
        even <<= 16;
        res = odd | even;
        return res;
    }
}

---

输出 2