颠倒二进制位

发表于 | 分类于 |
字数统计: 693 字 | 阅读时长 ≈ 2 分钟

题目描述：颠倒给定的 32 位无符号整数的二进制位。

示例 1：
输入：n = 00000010100101000001111010011100
输出：964176192 (00111001011110000010100101000000)
解释：输入的二进制串 00000010100101000001111010011100 表示无符号整数 43261596，
因此返回 964176192，其二进制表示形式为 00111001011110000010100101000000。

示例 2：
输入：n = 11111111111111111111111111111101
输出：3221225471 (10111111111111111111111111111111)
解释：输入的二进制串 11111111111111111111111111111101 表示无符号整数 4294967293，
因此返回 3221225471 其二进制表示形式为 10111111111111111111111111111111 。

提示：
输入是一个长度为 32 的二进制字符串

进阶: 如果多次调用这个函数，你将如何优化你的算法？

循环位运算

每次循环的时候把n的最后一位数字（二进制的）截取掉，放到一个新的数字中的末尾

一些前置知识

  1. 与预算 &
1
2
3
4
1 & 1 // 1的2进制最后一位是1，得到1
2 & 0 // 2的2进制最后一位是0，得到0
3 & 1 // 3的2进制最后一位是1，得到1
4 & 0 // 4的2进制最后一位是0，得到0

所以我们知道了怎么取10进制最后1位的2进制是几。

  1. JavaScript 使用 32 位按位运算数(意思是我们的按位运算都会转成32位，你的数字不能超过32位，会出问题)

    • JavaScript 将数字存储为 64 位浮点数，但所有按位运算都以 32 位二进制数执行。
    • 在执行位运算之前，JavaScript 将数字转换为 32 位有符号整数。
    • 执行按位操作后，结果将转换回 64 位 JavaScript 数。

  2. '<< 1' 运算

    这个运算实际上就是把10进制乘以2，这个乘2在2进制上表现出右边填了一个0，我们距举例来说，

    • 2的2进制是 10，2 << 1 得到4， 4的2进制是100，所以比10多了个0
    • 3的2进制是 11，3 << 1 得到6。6的2进制是110，所以比11多了个0
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
var reverseBits = function(n) {
  let result = 0
  for(let i = 0; i < 32; i++) {
    // res先往左移一位，把最后一个位置空出来，
    // 用来存放n的最后一位数字
    result <<= 1
    // res加上n的最后一位数字
    result += n & 1
    // n往右移一位，把最后一位数字去掉
    n >>= 1
  }

  // 为什么要 >>> 0 呢，一位javascript没有无符号整数，全是有符号的
  // 不>>>0的话，得出来的值是负数，但是无符号整数是没有符号的
  // javascript 有符号转化为无符号的方法就是>>>0
  return result >>> 0
};

复杂度分析

  • 时间复杂度：固定 32 位，循环次数不随输入样本发生改变。复杂度为 O(1)
  • 空间复杂度：O(1)