如何最高效的找出一个二进制数第n个1的位置？

Question

比如整数 430 （二进制表示为 110101110）, 我想找出这个数从右边开始的第4个1出现的位置，在这个例子中是5（序数从0开始）。

有什么高效的算法么？任何语言的实现都可以。

Answer 1

从右边开始会很简单，从左边开始的话，我就不写代码了，直接说下思路，很简单的。

首先拿110101110和100000000进行&操作，如果最左边的为1，自然就知道了，

然后110101110左移一位，变为101011100，再和100000000进行&操作，，，，就这样自己计数就好了。

时间复杂度O(n)，这个复杂度是跑不掉的了，只是写法的优化而已，最好的写法无疑是位运算。

---

如果从右边开始，那就更简单了，方法同上，不过与110101110进行&运算的数变为1就可以了，然后每次移动方向变为右移，但是注意，右移分逻辑右移和算术右移，需要做个转化，具体参考https://subetter.com/articles...

Answer 2

JS的写法

var str = change(430); //定义字符串
console.log(str);
var num = 0;
for (var i = 0; i < str.length; i++) {
    //遍历字符串，如果字符串中某一项值为1，让num自加1
    if (str[i] == 1) {
        num += 1;
        //判断num为4的时候，输出i
        if (num == 4) {
            console.log(i);
        }
    }
}

function change(number) {
    var temparr = []; //定义一个空数组
    var temp; //定义中间变量
    var temostr = '';
    //循环，处理正整数
    while (number > 0) {
        //整数模2，得到的余数赋值给temp
        temp = number % 2;
        //余数必定为0或者1，push进数组
        temparr.push(temp);
        //如果是2的倍数，继续模。如果不是2的倍数，向下取整之后，继续模
        number = Math.floor(number / 2);
        //直到数模除成0
    }
    while (temparr.length != 0) {
        //数组反向，一个个加到字符串上
        temostr += temparr.pop().toString();
    }
    return temostr; //返回最终结果
}

Answer 3

JS

// 二进制 110101110 是 十进制 430
// 右边
/^(.*?)((10*){4})$/g.exec((430).toString(2))[2].length - 1
// 左边
/^(.*?)((10*){4})$/g.exec((430).toString(2))[1].length - 1

Answer 4

用汇编指令效率最高，这里用python模拟一下算法~

python3

#如何最高效的找出一个二进制数第n个1的位置？

# popcnt 是cpu里的汇编指令，这里用函数模拟
def popcnt(b):
    n=0
    while(b):
        n+=1
        b &= b-1
    return n

def x(b, n):
    for i in range(n-1):
        b &= b-1
    return popcnt(b ^ (b-1))
    
b = 0b110101110
n = 4
print(x(b, n))
# 6 ##（序数从 1开始，第 6个位置）