算法场景

考虑下面这个场景，给你任意一个数字，要你求出大于等于它的并且最接近它的2的次幂

比如给一个数字13，那么大于等于13，并且最接近13的2的次幂为2的4次幂，也就是16，然后现在我们的限制条件是不允许使用循环，那么你会如何实现呢？

思路分析

既然不能用循环，那么肯定就要利用位运算的特性了，首先要明确一点，2的次幂，在二进制层面上是可以转换成次幂位后全为1，再加上1得到的，什么意思呢？

比如2的4次方是16，它的二进制为0001 0000，次幂位是从右往左数的第5位，其可以转换成0000 1111 + 0000 0001得到，那么利用这一点，我们可以想办法将任意数字构造出0000 1111这样的二进制位，然后再加1，就可以得到大于等于该数字并且最接近该数字的2的次幂了

还是以数字13为例，其二进制为0000 1101，以最高位的1为基准，将其后面全部转成1，也就是0000 1111，然后再加上1，就可以得到16了

那么如何将0000 1101转成0000 1111呢？这就需要用到位运算的小技巧了

无论最高位 1 在哪，我们只要让其不断地和自己右移之后的结果进行或运算，即可让其右边的二进制位变成 1，什么意思呢？

以25为例，0001 1001，右移一位，得到的是0000 1100，两者进行或运算后，得到的是0001 1101，再右移两位，得到的是0000 0111，两者再或运算后，得到的是0001 1111，这样就将最高位1后全部二进制位变成1了，然后加1即可得到我们想要的结果

特殊情况

如果数字本身就已经是2的次幂的话该怎么办？比如16的二进制为0001 0000，经过转换后就变成了0001 1111，再加1得到的就是0010 0000，也就是32，但答案应当是16才对，这个时候我们可以让数字本身减1，然后转换后再加1就是正常的了

代码实现

实现的代码如下：

export const solution = (num: number) => {
  // 避免数字本身就是 2 的次幂时转换出错
  // 比如 16 的二进制为 0001 0000 最高位 1 后全转为 1 得到的是 0001 1111
  // 这时候再加 1 得到的是 0010 0000 也就是 32
  // 显然并不正确，而先减 1 则可以避免该问题
  num--

  // js 的 number 是 64 位的 需要确保能够将最高位 1 后全部转为 1
  // 最极端的情况就是第 64 位为 1
  // 1000 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000
  // 要保证将它后面的所有位都能转成 1 需要经过下面这样操作
  num |= num >>> 1
  num |= num >>> 2
  num |= num >>> 4
  num |= num >>> 8
  num |= num >>> 16
  num |= num >>> 32

  // 对于负数而言，大于等于它的且最接近它的 2 的次幂就是 2 的 0 次幂，也就是 1
  // 而正数的话则是最高位之后全变为 1 后再加 1
  return num < 0 ? 1 : num + 1
}

单元测试

通过一个简单的vitest单元测试来验证一下

import { solution } from './index'

describe('03-求出大于等于给定数字且最接近该数字的2的次幂', () => {
  test('happy path', () => {
    expect(solution(13)).toBe(16)
    expect(solution(23)).toBe(32)
    expect(solution(1023)).toBe(1024)
    expect(solution(-666)).toBe(1)
  })
})

测试通过，没问题