位圖算法

編輯：關於C語言

位圖法定義

位圖法就是bitmap的縮寫，所謂bitmap，是用每一位來存放某種狀態，適用於大規模數據，但數據狀態又不是很多的情況。通常是用來判斷某個數據存不存在的。

例如，要判斷一千萬個人的狀態，每個人只有兩種狀態：男人，女人，可以用0，1表示。那麼就可以開一個int數組，一個int有32個位，就可以表示32個人。操作的時候可以使用位操作。本文地址：http://www.cnblogs.com/archimedes/p/bitmap.html，轉載請注明源地址。

數據結構

unsigned int bit[N];
在這個數組裡面，可以存儲 N * sizeof(int) * 8個數據，但是最大的數只能是N * sizeof(int) * 8 - 1。假如，我們要存儲的數據范圍為0-15，則我們只需要使得N=1，這樣就可以把數據存進去。如下圖：

數據為【5，1，7，15，0，4，6，10】，則存入這個結構中的情況為

位圖法應用

一、給40億個不重復的unsigned int的整數，沒排過序的，然後再給一個數，如何快速判斷這個數是否在那40億個數當中

申請512M的內存

一個bit位代表一個unsigned int值

讀入40億個數，設置相應的bit位

讀入要查詢的數，查看相應bit位是否為1，為1表示存在，為0表示不存在

二、使用位圖法判斷整形數組是否存在重復

判斷集合中存在重復是常見編程任務之一，當集合中數據量比較大時我們通常希望少進行幾次掃描，這時雙重循環法就不可取了。位圖法比較適合於這種情況，它的做法是按照集合中最大元素max創建一個長度為max+1的新數組，然後再次掃描原數組，遇到幾就給新數組的第幾位置上1，如遇到 5就給新數組的第六個元素置1，這樣下次再遇到5想置位時發現新數組的第六個元素已經是1了，這說明這次的數據肯定和以前的數據存在著重復。這種給新數組初始化時置零其後置一的做法類似於位圖的處理方法故稱位圖法。它的運算次數最壞的情況為2N。如果已知數組的最大值即能事先給新數組定長的話效率還能提高一倍。

#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#include<stdbool.h>

bool hasDuplicatedItem(int *a, int len)
{
    int length, max, i; 
    length = len;
    max = a[0];
    for(i = 1; i < length; i++){
        if(a[i] > max)
            max = a[i];
    }
    int *arr;
    arr = (int*)malloc(sizeof(int) * (max + 1));
    for(i = 0; i < length; i++){
        if(arr[a[i]])
            return true;
        else
            arr[a[i]] = 1;
    }
    return false;
}

int main()
{
    int length;
    int test[] = {0,1,2,3,45,12,13};
    length = (sizeof(test) / sizeof(test[0]));
    if(hasDuplicatedItem(test, length))
        printf("hasDuplicatedItem!\n");
    else
        printf("hasNoDuplicatedItem!\n");
    return 0;
}

三、使用位圖法進行整形數組排序

首先遍歷數組，得到數組的最大最小值，然後根據這個最大最小值來縮小bitmap的范圍。這裡需要注意對於int的負數，都要轉化為unsigned int來處理，而且取位的時候，數字要減去最小值。

#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#include<stdbool.h>

void bitmapSort(int *a, int len)
{
    int length, max, min, i, index; 
    length = len;
    min = max = a[0];
    //找出數組最大值
    for(i = 1; i < length; i++){
        if(a[i] > max){
            max = a[i];
        }
        if(min > a[i]) {
            min = a[i];
        }
    }
    //得到位圖數組
    int *arr;
    arr = (int*)malloc(sizeof(int) * (max - min + 1));
    for(i = 0; i < length; i++){
        index = a[i] - min;
        arr[index]++;
    }
    //重整a中的元素
    int arr_length;
    arr_length = max - min + 1;
    index = 0;
    for(i = 0; i < arr_length; i++){
        while(arr[i] > 0){
            a[index] = i + min;
            index++;
            arr[i]--;
        }
    }
}

void print(int *a, int n)
{
    int i;
    for(i = 0; i < n; i++) {
        printf("%d ", a[i]);
    }
    printf("\n");
}

int main()
{
    int length;
    int test[] = {50,1,26,3,45,12,13};
    length = sizeof(test) / sizeof(test[0]);
    print(test, length);
    bitmapSort(test, length);
    print(test, length);
    return 0;
}

四、位圖法存數據

輸入：一個最多包含n個正整數的文件，每個數都小於n，其中n=10,000,000 輸入文件中沒有重復的整數，沒有其他數據與該整數相關聯。

輸出：按升序排列這些數。

約束：有 1MB多（不超過2MB）的內存空間可用，有充足的硬盤空間。

#include<stdio.h>
#define BITSPERWORD 32
#define SHIFT 5
#define MASK 0x1F
#define N 10000000
int a[1 + N/BITSPERWORD];

/* a[i>>SHIFT]是第i位應該在第幾個int上 */
/* (1<<(i & MASK))是第i位在該int上的第幾個bit */

void set(int i)
{
    a[i>>SHIFT] |= (1<<(i & MASK));
}

void clr(int i)
{
    a[i>>SHIFT] &= ~(1<<(i & MASK));
}

int test(int i)
{
    return a[i>>SHIFT] & (1<<(i & MASK));
}

int main()
{
    int i;
    for(i = 0; i < N; i++)
        clr(i);
    while(scanf("%d", &i) != EOF)
        set(i);
    for(i = 0; i < N; i++)
        if(test(i))
            printf("%d\n", i);
    return 0;
}