原文鏈接https://www.jianshu.com/p/6082a2f7df8e

一、問題引入

舉一個例子，有一個無序有界int數組{1,2,5,7},初步估計占用內存4X4=16字節，這倒是沒什么奇怪的，但是假如有10億個這樣的數呢，如果這樣的一個大的數據做查找和排序，那估計內存也崩潰了，有人說，這些數據可以不用一次性加載，那就是要存盤了，存盤必然消耗IO。我們提倡的是高性能，這個方案直接不考慮。

二、問題分析

bitmap: 基于位的映射

一個byte是占8個bit，如果每一個bit的值就是有或者沒有，也就是二進制的0或者1，如果用bit的位置代表數組值有還是沒有，那么0代表該數值沒有出現過，1代表該數組值出現過。不也能描述數據了嗎？具體如下圖：

這樣，一個占用32bit的數據現在只占用了1bit，節省了不少的空間，排序就更不用說了，一切顯得那么順利。這樣的數據之間沒有關聯性，要是讀取的，你可以用多線程的方式去讀取。時間復雜度方面也是O(Max/n)，其中Max為byte[]數組的大小，n為線程大小。
處。

三、應用與代碼

基于bit運算實現

再看代碼之前，我們先搞清楚一個問題，一個數怎么快速定位它的索引號，也就是說搞清楚byte[index]的index是多少，position是哪一位。舉個例子吧，例如add(14)。14已經超出byte[0]的映射范圍，在byte[1]范圍之類。那么怎么快速定位它的索引呢。如果找到它的索引號，又怎么定位它的位置呢。Index(N)代表N的索引號，Position(N)代表N的所在的位置號。

Index(N) = N/8 = N >> 3;

Position(N) = N%8 = N & 0x07;

1. add(int num)

你要向bitmap里add數據該怎么辦呢，不用擔心，很簡單，也很神奇。
上面已經分析了，add的目的是為了將所在的位置從0變成1.其他位置不變.
（下圖應是作或運算 ）

實例代碼

public void add(int num){
        // num/8得到byte[]的index
        int arrayIndex = num >> 3; 
        
        // num%8得到在byte[index]的位置
        int position = num & 0x07; 
        
        //將1左移position后，那個位置自然就是1，然后和以前的數據做或運算，這樣，那個位置就替換成1了。
        bits[arrayIndex] |= 1 << position; 
    }

2. clear(int num)

對1進行左移，然后取反，最后與byte[index]作與操作。

public void clear(int num){
        // num/8得到byte[]的index
        int arrayIndex = num >> 3; 
        
        // num%8得到在byte[index]的位置
        int position = num & 0x07; 
        
        //將1左移position后，那個位置自然就是1，然后對取反，再與當前值做&，即可清除當前的位置了.
        bits[arrayIndex] &= ~(1 << position); 

    }

3. contain(int num)

 public boolean contain(int num){
        // num/8得到byte[]的index
        int arrayIndex = num >> 3; 
        
        // num%8得到在byte[index]的位置
        int position = num & 0x07; 
        
        //將1左移position后，那個位置自然就是1，然后和以前的數據做&，判斷是否為0即可
        return (bits[arrayIndex] & (1 << position)) !=0; 
    }

全部代碼

package com.chs.alg.bitmap;

public class BitMap {
    //保存數據的
    private byte[] bits;
    
    //能夠存儲多少數據
    private int capacity;
    
    
    public BitMap(int capacity){
        this.capacity = capacity;
        
        //1bit能存儲8個數據，那么capacity數據需要多少個bit呢，capacity/8+1,右移3位相當于除以8
        bits = new byte[(capacity >>3 )+1];
    }
    
    public void add(int num){
        // num/8得到byte[]的index
        int arrayIndex = num >> 3; 
        
        // num%8得到在byte[index]的位置
        int position = num & 0x07; 
        
        //將1左移position后，那個位置自然就是1，然后和以前的數據做|，這樣，那個位置就替換成1了。
        bits[arrayIndex] |= 1 << position; 
    }
    
    public boolean contain(int num){
        // num/8得到byte[]的index
        int arrayIndex = num >> 3; 
        
        // num%8得到在byte[index]的位置
        int position = num & 0x07; 
        
        //將1左移position后，那個位置自然就是1，然后和以前的數據做&，判斷是否為0即可
        return (bits[arrayIndex] & (1 << position)) !=0; 
    }
    
    public void clear(int num){
        // num/8得到byte[]的index
        int arrayIndex = num >> 3; 
        
        // num%8得到在byte[index]的位置
        int position = num & 0x07; 
        
        //將1左移position后，那個位置自然就是1，然后對取反，再與當前值做&，即可清除當前的位置了.
        bits[arrayIndex] &= ~(1 << position); 

    }
    
    public static void main(String[] args) {
        BitMap bitmap = new BitMap(100);
        bitmap.add(7);
        System.out.println("插入7成功");
        
        boolean isexsit = bitmap.contain(7);
        System.out.println("7是否存在:"+isexsit);
        
        bitmap.clear(7);
        isexsit = bitmap.contain(7);
        System.out.println("7是否存在:"+isexsit);
    }
}

四、bitmap排序實例

以下參考https://wizardforcel.gitbooks.io/the-art-of-programming-by-july/content/06.07.html

//定義每個Byte中有8個Bit位  
#include ＜memory.h＞  
#define BYTESIZE 8  
void SetBit(char *p, int posi)  
{  
    for(int i=0; i < (posi/BYTESIZE); i++)  
    {  
        p++;  
    }  

    *p = *p|(0x01<<(posi%BYTESIZE));//將該Bit位賦值1  
    return;  
}  

void BitMapSortDemo()  
{  
    //為了簡單起見，我們不考慮負數  
    int num[] = {3,5,2,10,6,12,8,14,9};  

    //BufferLen這個值是根據待排序的數據中最大值確定的  
    //待排序中的最大值是14，因此只需要2個Bytes(16個Bit)  
    //就可以了。  
    const int BufferLen = 2;  
    char *pBuffer = new char[BufferLen];  

    //要將所有的Bit位置為0，否則結果不可預知。  
    memset(pBuffer,0,BufferLen);  
    for(int i=0;i<9;i++)  
    {  
        //首先將相應Bit位上置為1  
        SetBit(pBuffer,num[i]);  
    }  

    //輸出排序結果  
    for(int i=0;i<BufferLen;i++)//每次處理一個字節(Byte)  
    {  
        for(int j=0;j<BYTESIZE;j++)//處理該字節中的每個Bit位  
        {  
            //判斷該位上是否是1，進行輸出，這里的判斷比較笨。  
            //首先得到該第j位的掩碼（0x01＜＜j），將內存區中的  
            //位和此掩碼作與操作。最后判斷掩碼是否和處理后的  
            //結果相同  
            if((*pBuffer&(0x01<<j)) == (0x01<<j))  
            {  
                printf("%d ",i*BYTESIZE + j);  
            }  
        }  
        pBuffer++;  
    }  
}  

int _tmain(int argc, _TCHAR* argv[])  
{  
    BitMapSortDemo();  
    return 0;  
}