如何找出一个二进制数中所有1的位置？

Question

比如给定一个数 210 (二进制表示为 11010010），其中第2、5、7、8位是1（从最右开始数），那么结果就是 [2,5,7,8]。

有什么高效的解决办法呢？

Answer 1

水平有限.
不知道你想要的高效解决方案是什么样,但是我自己试了一下,在python里,我认为应该高效的方法实际上并不高效,反而是我认为最蠢的办法效率更高.

# coding:utf-8
def bit(n):
    ret = []
    c = 1
    while n > 0:
        if n & 1 == 1:
            ret.append(c)
        n >>= 1
        c += 1
    return ret


def string(n):
    s = bin(n)[:1:-1]  # 截掉0b1001的0b部分并倒序排列
    # ret = []
    # i = 1
    # for index in s:
    #     if i == "1":
    #         ret.append(index+1)
    #     i += 1
    return [i for i, j in enumerate(s) if j == "1"]


def main():
    from timeit import Timer
    t1 = Timer("string(2156456456465465432132123132132123132123132123165460)",
               "from __main__ import string")
    print "str", t1.timeit(100000)
    t2 = Timer("bit(2156456456465465432132123132132123132123132123165460)",
               "from __main__ import bit")
    print "bit", t2.timeit(100000)


if __name__ == '__main__':
    main()

"""
str 2.27909399816
bit 7.63658934322
"""

这么跑一下反而是遍历字符串的速度更快,位运算的优势完全无法体现出来,相比来说while本身就比for要慢一些,我怀疑是这里造成的差异.
我再试了一下golang,

package main

import (
    "fmt"
    "log"
    "time"
)

func bit(n int64) []int64 {
    ret := []int64{}
    var c int64
    c = 1
    for n > 0 {
        if n&1 == 1 {
            ret = append(ret, c)
        }
        c++
        n >>= 1
    }
    return ret
}

func str(n int64) []int {
    ret := []int{}
    s := []rune(fmt.Sprintf("%b", n))
    length := len(s)
    for i := length - 1; i >= 0; i-- {
        if s[i] == 49 {
            ret = append(ret, length-i)
        }
    }
    return ret
}

func main() {
    t1 := time.Now()
    for index := 0; index < 100000; index++ {
        bit(1 << 62)
    }
    log.Println(time.Since(t1))
    t2 := time.Now()
    for index := 0; index < 100000; index++ {
        str(1 << 62)
    }
    log.Println(time.Since(t2))
}
//2018/10/28 19:23:46 22.9372ms
//2018/10/28 19:23:46 113.6953ms

由于golang这个字符串方法我写的比较挣扎,速度也比位运算慢了5倍左右.
这给我的感受就是,这个操作本身因为本身就比较简单,随便增加一点边边角角的操作,就会对整体耗时造成非常大的影响,的去提升他的效率可能一不小心就负优化了.

Answer 2

直接上答案吧，我是用列表推导来做的，

[i + 1 for i, x in enumerate(list(bin(a)[::-1])) if x =='1']

后来为了更高的效率，我直接这样做了。

a = (i + 1 for i, x in enumerate(list(bin(a)[::-1])) if x =='1')

# 需要打印出来就用这个迭代呗。
for x in a:
    print(x)

Answer 3

public static List<Integer> getBitCollections (long bits) {  
    List<Integer> index = new ArrayList<>();  
 int position = 1;  
 while (bits != 0) {  
    if ((bits & 1) != 0) {  
        index.add(position);  
    }  
      position++;  
      bits = bits >>> 1;  
  }  
    return index;  
}