利用bitmap進行排序,裝入數(shù)據(jù)的時候只需要位運算設置1,那么取出數(shù)據(jù)的時候一般是怎么把標記為1的位轉(zhuǎn)換成10進制的數(shù)?例如假設一個byte存儲0-7的數(shù)據(jù)信息,那么如何將0000,1000轉(zhuǎn)換成3(0000,0011).簡單例子: 用一個32位的int表示0-31的數(shù)據(jù),并對一個數(shù)組排序輸出public static void main(String[] args){ int[] data = new int[]{5,10,15,3,16,17,6,8,11}; //待排序數(shù)組 int model = 0; //bitmap初始化為0 for(int i:data){ model = model|(1<<i); //把對應位設置為1 } for(int i=1;i<=32;i++){ //遍歷32位,判斷是否為1,為1的話取出數(shù)據(jù) if((model&(1<<i))!=0) //問題來了,如何從model&(1<<i) 得到對數(shù)? }比如0000,1000 的值是8,即2^3 但因為是bitmap所以對應的值應該是3(右數(shù)第4位為1)簡單想法1: 右移循環(huán)int count = 0;while((((model&(1<<i))>>1)!=0){ //每次右移一位以此計算有幾位 count++;}簡單想法2: Math.log()Math.log(); //底層是c語言庫,不知道怎么實現(xiàn)。。問題整理:1.一般bitmap取出數(shù)據(jù)時用什么方法?2.我的兩種想法有什么問題?3.按照我的想法,既然取出數(shù)據(jù)還需要一次循環(huán),那么bitmap的O(N)如何體現(xiàn)?
2 回答

斯蒂芬大帝
TA貢獻1827條經(jīng)驗 獲得超8個贊
在循環(huán)時記錄下循環(huán)的位置就能進行轉(zhuǎn)換了。
for(int i = 1; i <= 32; i++) {
if((model & (1 << i)) != 0) {
// i 就是位置呀
}
}
另外,關(guān)于你說的O(N)的問題,循環(huán)兩次也并不是表示O(2N),這里也是O(N)。時間復雜度表示的是量級,并不總是對應循環(huán)的次數(shù)。
添加回答
舉報
0/150
提交
取消