算法 - 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

Enregistrez la position de la boucle lors de la boucle et vous pourrez la convertir.

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

De plus, concernant le problème O(N) que vous avez mentionné, boucler deux fois ne signifie pas O(2N). C'est aussi O(N) ici. La complexité temporelle représente l'ampleur et ne correspond pas toujours au nombre de boucles.

Answer 2

Obtenir des bits est généralement une opération décalage plus ET. Par exemple, si vous obtenez 3 bits (2-4 bits) d'un nombre A, vous pouvez utiliser ce qui suit, (A&0x0e)>&gt. ;1, c'est-à-dire Take 0000 1110, le 3 bits correspondant, c'est en fait ainsi qu'il est implémenté dans le projet