찾다

 >  Q&A  >  본문

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

利用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)如何体现?

PHP中文网PHP中文网2887일 전347

모든 응답(2)나는 대답할 것이다

  • ringa_lee

    ringa_lee2017-04-17 17:33:39

    루프할 때 루프의 위치를 ​​기록하고 변환할 수 있습니다.

    으아아아

    게다가 말씀하신 O(N) 문제와 관련하여 두 번 반복한다고 해서 여기서도 O(2N)이 되는 것은 아닙니다. 시간 복잡도는 크기를 나타내며 항상 루프 수와 일치하는 것은 아닙니다.

    회신하다
    0
  • PHP中文网

    PHP中文网2017-04-17 17:33:39

    비트를 얻는 것은 일반적으로 시프트 플러스 AND 연산입니다. 예를 들어 숫자 A의 3비트(2-4비트)를 얻는 경우 다음 방법을 사용할 수 있습니다. >1, 즉 Take 0000 1110, 해당 3bit, 이것이 실제로 프로젝트에서 구현되는 방식입니다

    회신하다
    0
  • 취소회신하다