颠倒二进制位

位运算分治

  1. 解题思路：

  2. 图解：

  3. 复杂度：

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

  4. 代码实现：

    var reverseBits = function (n) {
  //低16位与高16位交换
  // ffff ffff 右移16位，变成 0000 ffff
  // ffff ffff 左移16位，变成 ffff 0000
  n = (n >>> 16) | (n << 16);

  //每16位中低8位和高8位交换
  n = ((n & 0xff00ff00) >>> 8) | ((n & 0x00ff00ff) << 8);

  //每8位中低4位和高4位交换
  n = ((n & 0xf0f0f0f0) >>> 4) | ((n & 0x0f0f0f0f) << 4);

  //每4位中低2位和高2位交换
  n = ((n & 0xcccccccc) >>> 2) | ((n & 0x33333333) << 2);

  //每2位中低1位和高1位交换
  n = ((n & 0xaaaaaaaa) >>> 1) | ((n & 0x55555555) << 1);

  return n >>> 0;
};

迭代颠倒

  1. 解题思路：

    • res 初始值为 0，每次把 res 左移，把 n 的二进制末尾数字，拼接到结果 res 的末尾；
    • 然后把 n 右移，不断去掉 n 末尾的数字；

  2. 图解：无符号右移

  3. 复杂度：

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

  4. 代码实现：

    JS
    TS
    var reverseBits = function (n) {
  let res = 0;

  for (let i = 0; i < 32; i++) {
    // res 左移一位，加上 n 的最后一位
    res = (res << 1) | (n & 1);
    // n 每次右移一位
    n >>= 1;
  }

  // x >>> 0本质上就是保证x有意义（为数字类型），且为正整数，且在无意义的情况下缺省值为0
  return res >>> 0;
};

    function reverseBits(n: number): number {
  let res = 0;

  for (let i = 0; i < 32; i++) {
    // res 左移一位，加上 n 的最后一位
    res = (res << 1) | (n & 1);
    // n 每次右移一位
    n >>= 1;
  }

  // x >>> 0本质上就是保证x有意义（为数字类型），且为正整数，且在无意义的情况下缺省值为0
  return res >>> 0;
};
打赏作者
您的打赏是我前进的动力
微信
支付宝
评论

中午好👏🏻，我是 ✍🏻   疯狂 codding 中...

粽子

这有关于前端开发的技术文档和你分享。

相信你可以在这里找到对你有用的知识和教程。

了解更多

目录

  1. 1. 颠倒二进制位
  2. 2. 位运算分治
  3. 3. 迭代颠倒