JavaScript中获取最高位（最左侧位）位置的最快方法是什么？

比如给定整数9，它的二进制是00001001，我们要找的是最高位对应的2^3=8（或者说最高位的位置是3，从0开始计数）。下面是几种高效的实现方式：

通用思路 #

核心是找到最大的k，使得2^k ≤ n，对应结果就是2^k。用位运算实现通常比调用数学函数更快、更高效。

C/C++ 实现 #

方法1：纯位运算快速消除低位 #

unsigned int highestPowerOf2(unsigned int n) {
    // 把最高位以下的所有位都置为1
    n |= n >> 1;
    n |= n >> 2;
    n |= n >> 4;
    n |= n >> 8;
    n |= n >> 16;
    // 减去右移一位的结果，只保留最高位的1
    return n - (n >> 1);
}

举个例子：9（二进制1001）经过几次右移或操作后变成1111，1111 - 0111 = 1000（也就是8）。

方法2：利用编译器内置函数 #

GCC/Clang提供了__builtin_clz（统计前导零个数），32位无符号整数可以这么写：

unsigned int highestPowerOf2(unsigned int n) {
    // 注意：n不能为0，否则__builtin_clz行为未定义
    return 1 << (31 - __builtin_clz(n));
}

__builtin_clz(n)返回n二进制前导零的数量，31减去这个数就是最高位的位置，左移1就得到对应的幂。

Java 实现 #

Java的Integer类直接封装了这个功能，一行代码搞定：

public static int highestPowerOf2(int n) {
    return Integer.highestOneBit(n);
}

输入9的话，返回值就是8，完美符合需求。

Python 实现 #

方法1：位运算（推荐） #

def highest_power_of_2(n):
    if n == 0:
        return 0
    # bit_length()返回二进制的位数，减1就是最高位的位置
    k = n.bit_length() - 1
    return 1 << k

比如9的二进制是4位，4-1=3，1<<3=8。

方法2：数学库实现 #

如果不介意调用数学函数，也可以这么写：

import math

def highest_power_of_2(n):
    if n == 0:
        return 0
    k = math.floor(math.log2(n))
    return 2 ** k

注意n必须是正整数，否则log2会报错。

JavaScript 实现 #

function highestPowerOf2(n) {
    if (n === 0) return 0;
    // Math.clz32统计32位整数的前导零个数
    return 1 << (31 - Math.clz32(n));
}

比如9的32位二进制前导零有28个，31-28=3，1<<3=8。

内容的提问来源于stack exchange，提问作者bohkoval