## 二进制串反转 Reverse Bits 原

叶枫啦啦

Reverse bits of a given 32 bits unsigned integer.

For example, given input 43261596 (represented in binary as 00000010100101000001111010011100), return 964176192 (represented in binary as 00111001011110000010100101000000).

If this function is called many times, how would you optimize it?

Related problem: Reverse Integer

① 目标：将二进制串反转，原数不断右移取出最低位，赋给新数的最低位后新数再不断左移。

public class Solution { // 2ms
// you need treat n as an unsigned value
public int reverseBits(int n) {
int res = 0;
for (int i = 0;i < 32 ;i ++,n >>= 1) {
res = res << 1 | (n & 1); //将结果左移然后将最低位取出赋值给新的数（移位运算符优先于|）
}
return res;
}
}

public class Solution { //2ms
// you need treat n as an unsigned value
public int reverseBits(int n) {
int res = 0;
for (int i = 0;i < 32 ;i ++ ) {
res = (res << 1) + (n & 1);
n = n >> 1;
}
return res;
}
}

② 分段相或法：根据Java标准的Integer.reverse()源码。将数字的位按照整块整块的翻转，例如32位分成两块16位的数字，16位分成两个8位进行翻转，这样以此类推直到只有一位。

public class Solution{ //2ms
public int reverseBits(int n) {
int res = n;
res = res >>> 16 | res << 16; //交换前后两个双字节
res = (res & 0xff00ff00) >>> 8 | (res & 0x00ff00ff) << 8; //交换相邻的两个字节
res = (res & 0xf0f0f0f0) >>> 4 | (res & 0x0f0f0f0f) << 4; //交换每8位中的前四位和后四位
res = (res & 0xcccccccc) >>> 2 | (res & 0x33333333) << 2; //交换每4位中的前两位和后两位
res = (res & 0xaaaaaaaa) >>> 1 | (res & 0x55555555) << 1; //交换每两位
return res;
}
}

0xff00ff00 = ‭1111 1111 0000 0000 1111 1111 0000 0000‬

0x00ff00ff = 0000 0000 1111 1111 0000 0000 1111 1111

0xf0f0f0f0 = 1111 0000 1111 0000 1111 0000 1111 0000

0x0f0f0f0f = 0000 1111 0000 1111 0000 1111 0000 1111

0xCCCCCCCC =   1100 1100 1100 1100 1100 1100 1100 1100

0x33333333 =      0011 0011 0011 0011 0011 0011 0011 0011

0xAAAAAAAA =    1010 1010 1010 1010 1010 1010 1010 1010

0x55555555 =        0101 0101 0101 0101 0101 0101 0101 0101

```/*
0000 0010 1001 0100 0001 1110 1001 1100
0001 1110 1001 1100 0000 0010 1001 0100 //每16位交换
1001 1100 0001 1110 1001 0100 0000 0010 //每8位交换
1100 1001 1110 0001 0100 1001 0010 0000 //每4位交换
0011 0110 1011 0100 0001 0110 1000 0000 //每2位交换
0011 1001 0111 1000 0010 1001 0100 0000 //每1位交换
*/```

public class Solution{ //7ms
private final Map<Byte, Integer> map = new HashMap<Byte, Integer>();
public int reverseBits(int n) {
byte[] bytes = new byte[4];
for (int i = 0; i < 4; i ++) // convert int into 4 bytes
bytes[i] = (byte)((n >>> 8 * i) & 0xFF);
int result = 0;
for (int i = 0; i < 4; i ++) {
result += reverseByte(bytes[i]); // reverse per byte
if (i < 3)
result <<= 8;
}
return result;
}
private int reverseByte(byte b) {
Integer value = map.get(b); // first look up from map
if (value != null)
return value;
value = 0;
// reverse by bit
for (int i = 0; i < 8; i ++) {
value += ((b >>> i) & 1);
if (i < 7)
value <<= 1;
}
map.put(b, value);
return value;
}
}

### 叶枫啦啦

hell0cat
2016/09/04
35
0
LeetCode算法题-Reverse Bits（Java实现）

2018/11/28
0
0
leetcode算法题解(Java版)-2-最长回文子串

kissjz
2018/04/28
0
0

(九) 短信部分——PDU简介及其格式 　　PDU是大多数手机短信通讯的核心，仅有少数手机只支持Text模式（例如笔者的MOTO C330）。PDU模式比起Text模式可以提供能为强大的功能，但其编码较Text模...

zhengyijie
2014/02/17
0
0

Reverse bits of a given 32 bits unsigned integer. For example, given input 43261596 (represented in binary as 00000010100101000001111010011100), return 964176192 (represented in......

golang_yh
2016/02/13
58
0

MySQL查询执行

47分钟前
0
0
CDH5动静态资源池配置与回滚

hblt-j
52分钟前
3
0
WordPress仿站实战教程

55分钟前
3
0

https://github.com/nothings/stb 目前一般主流的图像格式也就是bmp，jpg，png，tga，dds，除了DDS一般是给DX用的，虽然一堆OpenGL程序也有用的，但是我一般只用png和tga， png不用说了，带a...

robslove

1
0
Spring 事务提交回滚源码解析

TSMYK

2
0