算法 - bitmap一般如何取出其所表示的数据(以java为例)

Question

利用bitmap进行排序，装入数据的时候只需要位运算设置1，那么取出数据的时候一般是怎么把标记为1的位转换成10进制的数？例如假设一个byte存储0-7的数据信息，那么如何将0000,1000转换成3(0000,0011).

简单例子: 用一个32位的int表示0-31的数据，并对一个数组排序输出

public static void main(String[] args){
        int[] data = new int[]{5,10,15,3,16,17,6,8,11};    //待排序数组
        int model = 0;    //bitmap初始化为0
        for(int i:data){
            model = model|(1<<i);   //把对应位设置为1 
        }
        for(int i=1;i<=32;i++){    //遍历32位，判断是否为1，为1的话取出数据
            if((model&(1<<i))!=0)    
                //问题来了，如何从model&(1<<i) 得到对数?
        }

比如0000,1000 的值是8，即2^3 但因为是bitmap所以对应的值应该是3(右数第4位为1)

简单想法1: 右移循环

int count = 0;
while((((model&(1<<i))>>1)!=0){    //每次右移一位以此计算有几位
    count++;
}

简单想法2: Math.log()

Math.log();    //底层是c语言库，不知道怎么实现。。

问题整理:
1.一般bitmap取出数据时用什么方法？
2.我的两种想法有什么问题？
3.按照我的想法，既然取出数据还需要一次循环，那么bitmap的O(N)如何体现？

Answer 1

Rekodkan kedudukan gelung semasa menggelung dan anda boleh menukarnya.

for(int i = 1; i <= 32; i++) {
    if((model & (1 << i)) != 0) {
        // i 就是位置呀
    }
}

Selain itu, mengenai masalah O(N) yang anda nyatakan, gelung dua kali tidak bermakna O(2N) di sini. Kerumitan masa mewakili magnitud dan tidak selalu sepadan dengan bilangan gelung.

Answer 2

Mendapatkan bit biasanya merupakan operasi anjakan tambah DAN Anda boleh mendapatkan berbilang bit Contohnya, jika anda mendapat 3 bit (2-4 bit) nombor A, anda boleh menggunakan yang berikut, (A&0x0e)>&gt. ;1, iaitu Ambil 0000 1110, 3bit yang sepadan, ini sebenarnya bagaimana ia dilaksanakan dalam projek