题目描述（简单难度）

190. Reverse Bits - 图1

将一个 int 类型的数字，32 个 bit，进行倒置。

解法一

用一个变量 res 去存储结果，依次得到要转换数字的低位，然后依次保存到 res 中。res 每得到一位后进行左移腾出位置保存下一位。举个具体的例子。

  1. 原数字 1011 ，res = 0
  3. res 左移一位，res = 0，
  4. 得到 1011 的最低位 1 加过来, res = 1
  5. 1011 右移一位变为 101
  7. res = 1 左移一位，res = 10，
  8. 得到 101 的最低位 1 加过来, res = 11
  9. 101 右移一位变为 10 
  11. res = 11 左移一位，res = 110，
  12. 得到 10 的最低位 0 加过来, res = 110
  13. 10 右移一位变为 1 
  15. res = 110 左移一位，res = 1100，
  16. 得到 1 的最低位 1 加过来, res = 1101
  17. 1 右移一位变为 0, 结束

至于怎么得到最低位，和把最低位加过来，我们可以通过位操作完成。

  1. public int reverseBits(int n) {
  2.     int res = 0;
  3.     int count = 0;
  4.     while (count < 32) {
  5.         res <<= 1;  //res 左移一位空出位置
  6.         res |= (n & 1); //得到的最低位加过来
  7.         n >>= 1;//原数字右移一位去掉已经处理过的最低位
  8.         count++;
  9.     }
  10.     return res;
  11. }

解法二

另一种想法，参考 这里-bit-operation-C%2B%2B-solution-(8ms))。

如果是两位数字怎么逆序呢？比如 2 4，我们只需要交换两个数字的位置，变成 4 2。

如果是四位数字怎么逆序呢？比如 1 2 3 4，同样的我们只需要交换两部分 1 2 和3 4 的数字，变成 3 4 1 2，接下来只需要分别将两部分 3 4 和 1 2 分别逆序，两位数的逆序已经讨论过。

如果是八位数字怎么逆序呢？比如 1 2 3 4 5 6 7 8，同样的我们只需要交换两部分1 2 3 4 和 5 6 7 8 的数字，变成 5 6 7 8 1 2 3 4，接下来只需要分别将两部分 5 6 7 8 和 1 2 3 4 分别逆序，四位数的逆序已经讨论过。

这道题也可以用这个思想去解决，32 位的数字左半部分何右半部分交换，得到两个 16 位的数字，然后两部分再交换，得到两个 8 位的数字…

在二进制中交换两部分，可以用一个技巧，举个例子，对于 x = 1101 交换两部分，我们只需要

(1100) & x >>> 2 | (0011) & x <<< 2 = (0011)|(0100)= 0111，然后就完成了 11 和 01 的交换。

  1. public int reverseBits(int n) {
  2.     n = ((n & 0xffff0000) >>> 16) | ((n & 0x0000ffff) << 16);
  3.     n = ((n & 0xff00ff00) >>> 8) | ((n & 0x00ff00ff) << 8);
  4.     n = ((n & 0xf0f0f0f0) >>> 4) | ((n & 0x0f0f0f0f) << 4);
  5.     n = ((n & 0xcccccccc) >>> 2) | ((n & 0x33333333) << 2);
  6.     n = ((n & 0xaaaaaaaa) >>> 1) | ((n & 0x55555555) << 1);
  7.     return n;
  8. }

上边的写成 16 进制可能一下子不能理解，写成 2 进制就明白了。

比如 n = ((n & 0xcccccccc) >>> 2) | ((n & 0x33333333) << 2); 也就是之前讨论的两位和两位交换。

我们需要分别和 1100 和 0011 进行与操作，写成 16 进制就是 c 和 3，因为我们要同时对 32 位的数字操作，每四个算一组，也就是八组，也就是 8和 c 和 8 个 3 了。

另外需要注意的是一定要是逻辑右移，也就是三个大于号 >>>，不能去考虑符号位，具体就是涉及到 补码 的知识了。

总

重点是对于二进制的理解，计算机中的数字都是以二进制的形式存储，按位与，按位或，右移左移一些位操作需要熟悉。

windliang wechat

添加好友一起进步~

如果觉得有帮助的话，可以点击 这里 给一个 star 哦 ^^

如果想系统的学习数据结构和算法，强烈推荐一个我之前学过的课程，可以点击 这里 查看详情