190_reverseBits.md

190. 颠倒二进制位

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

示例 1：

输入: 00000010100101000001111010011100

输出: 00111001011110000010100101000000

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

方法一：分治法

• 时间复杂度：O(1)
• 空间复杂度：O(1)

#include <stdio.h>

unsigned int reverseBits(unsigned int x)
{
    unsigned int M1 = 0x55555555;
    unsigned int M2 = 0x33333333;
    unsigned int M4 = 0x0F0F0F0F;
    unsigned int M8 = 0x00FF00FF;

    x = ((x >> 1) & M1) | ((x & M1) << 1);
    x = ((x >> 2) & M2) | ((x & M2) << 2);
    x = ((x >> 4) & M4) | ((x & M4) << 4);
    x = ((x >> 8) & M8) | ((x & M8) << 8);

    return (x >> 16) | (x << 16);
}

int main(void)
{
    unsigned int i = 0b00000010100101000001111010011100;
    printf("%d\n", reverseBits(i));

    return 0;
}