一、定义
位图法就是bitmap的缩写。所谓bitmap,就是用每一位来存放某种状态,适用于大规模数据,但数据状态又不是很多的情况。通常是用来判断某个数据存不存在的。在STL中有一个bitset容器,其实就是位图法

数据结构

unsigned int bit[N];

在这个数组里面,可以存储 N*sizeof(int)*8个数据,但是最大的数只能是N*sizeof(int)*8-1

相关操作

写入数据

定义一个数组: unsigned char bit[8*1024];这样做,能存 8K*8=64K 个 unsigned short 数据。

bit 存放的字节位置和位位置(字节0~8191,位 0~7 )比如写1234,字节序:1234/8 = 154; 位序: 1234 &0b111 = 2 ,那么 1234 放在 bit 的下标 154 字节处,把该字节的 2 号位( 0~7)置为 1。

字节位置: int nBytePos =1234/8 = 154;
位位置:   int nBitPos = 1234 & 7 = 2;
比如写入 1236 ,
字节位置: int nBytePos =1236/8 = 154;
位位置:   int nBitPos = 1236 & 7 = 4

// / 把数组的 154 字节的 4 位置为 1  
val = 1<<nBitPos;  
arrBit[nBytePos] = arrBit[nBytePos] |val;  // 再写入 1236 得到arrBit[154]=0b00010100  

代码实现

/* Copyright (C) 1999 Lucent Technologies */
/* From 'Programming Pearls' by Jon Bentley */
/* bitsort.c -- bitmap sort from Column 1 * Sort distinct integers in the range [0..N-1] */ 
#include <stdio.h> 
#define BITSPERWORD 32 
#define SHIFT 5 
#define MASK 0x1F 
#define N 10000000 
int a[1 + N/BITSPERWORD]; 
/*
i是int类型,32位的,而a是int型数组,所以除以32可以知道是在a的数组中哪一个下标,模32可以确定某一位。
a[i>>SHIFT]是第i位应该在第几个int上,右移5位相当于除2^5也就是32
(1<<(i & MASK))是第i位在该int上的第几个bit,i & 0x1F 保留了低五位,相当于模32.
*/
void set(int i) { //将指定的bit赋1
    a[i>>SHIFT] |= (1<<(i & MASK)); 
} 

void clr(int i) { //将指定的bit清0
    a[i>>SHIFT] &= ~(1<<(i & MASK)); 
} 

int test(int i){//取一下存入的值  每5 bit是一组。
    return a[i>>SHIFT] & (1<<(i & MASK)); 
} 
int main() { 
    int i; 
    for (i = 0; i < N; i++) 
        clr(i); //每位设为0,
    /*
    根据输入的i ,放入指定位置,对应的位置为1
    比如你输入,4,2,3,1
        4:0000000000010000
        2:0000000000010100
        3:0000000000011100
        1:0000000000011110
    */
    while (scanf("%d", &i) != EOF) 
        set(i); 
    //遍历所有位,从bit0~~~bit N判断该位是不是0,如果不是0的话,就有数,作输出,相当于排序。
    for (i = 0; i < N; i++) 
        if (test(i)) 
           printf("%d\n", i);
    return 0; 
}
  • 使用位图法判断整形数组是否存在重复遍历数组,一个一个放入bitmap,并且检查其是否在bitmap中出现过,如果没出现放入,否则即为重复的元素。

 

Logo

权威|前沿|技术|干货|国内首个API全生命周期开发者社区

更多推荐