【C/C++ 基础算法】 C/C++ 位图算法的使用-阿里云开发者社区

【C/C++ 基础算法】 C/C++ 位图算法的使用

2024-03-26 35

版权

本文内容由阿里云实名注册用户自发贡献，版权归原作者所有，阿里云开发者社区不拥有其著作权，亦不承担相应法律责任。具体规则请查看《阿里云开发者社区用户服务协议》和《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容，填写侵权投诉表单进行举报，一经查实，本社区将立刻删除涉嫌侵权内容。

简介： 【C/C++ 基础算法】 C/C++ 位图算法的使用

C/C++ 位图算法

1. 什么是位图算法

位图算法（Bitmap Algorithm）是一种在计算机科学和数据结构中用于高效地管理位（bit）的算法。它通常用于快速检索和存储数据。位图算法在内存使用上非常高效，因为它每个元素只使用一个位。

In computer science, a bitmap is a mapping from some domain to bits.

位图法就是bitmap的缩写，所谓bitmap，是用每一位来存放某种状态，适用于大规模数据，但数据状态又不是很多的情况。

通常是用来判断某个数据存不存在的。

例如，要判断一千万个人的状态，每个人只有两种状态：男人，女人，可以用0，1表示。

那么就可以开一个int数组，一个int有32个位，就可以表示32个人。操作的时候可以使用位操作。

数据结构

unsigned int bit[N];
//在这个数组里面，可以存储 N * sizeof(int) * 8个数据，但是最大的数只能是N * sizeof(int)  * 8 - 1。
//假如，我们要存储的数据范围为0-15，则我们只需要使得N=1，这样就可以把数据存进去。

2. 位图算法的应用场景

数据库索引
图像处理
网络数据传输
内存管理

3. 位图算法的基础操作

3.1 设置位（Set Bit）

void set_bit(char *bitmap, int index) {
    bitmap[index / 8] |= (1 << (index % 8));
}

3.2 清除位（Clear Bit）

void clear_bit(char *bitmap, int index) {
    bitmap[index / 8] &= ~(1 << (index % 8));
}

3.3 检查位（Check Bit）

bool check_bit(char *bitmap, int index) {
    return bitmap[index / 8] & (1 << (index % 8));
}

这些基础操作在GCC编译器的源码中，具体可以在gcc/bitmap.c文件中找到。

4. 位图算法的优缺点

优点	缺点
内存使用高效	不能存储复杂数据
检索速度快	可能导致空间浪费

正如Bjarne Stroustrup在《The C++ Programming Language》中所说：“The closer your representation to the domain, the more meaning you can give to the individual bits and bytes.”

5. 位图的应用举例

给40亿个不重复的unsigned int的整数，没排过序的，然后再给一个数，如何快速判断这个数是否在那40亿个数当中

申请512M的内存 (注:1G ≈ 10亿字节)

一个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;
}

示例

事实上,我们是用每一个元素表示一个32位的二进制字符串,这样这个元素可以保留相邻32个号码是否存在的信息,数组范围就下降到10000000/32了.例如对于号码 89256,由于89256 mod 32=2789…8,这样我们应该置a[2789]中32位字符串的第8位(从低位数起)为1.

#define WORD 32
#define SHIFT 5 移动5个位,左移则相当于乘以32,右移相当于除以32取整
#define MASK 0x1F //16进制下的31
#define N 10000000
int bitmap[1 + N / WORD];
/*
 * 置位函数——用"|"操作符,i&MASK相当于mod操作
 * m mod n 运算，当n = 2的X次幂的时候,m mod n = m&(n-1)
 */
void set(int i) {
 bitmap[i >> SHIFT] |= (1 << (i & MASK));
}
/* 清除位操作，用&~操作符 */
void clear(int i) {
 bitmap[i >> SHIFT] &= ~(1 << (i & MASK));
}
/* 测试位操作用&操作符 */
int test(int i) {
 return bitmap[i >> SHIFT] & (1 << (i & MASK));
}

//实现排序（不能重复）：
int main(void) {
 FILE *in = fopen("in.txt", "r");
 FILE *out = fopen("out.txt", "w");
 if (in == NULL || out == NULL) 
 {
 exit(-1);
 }
 int i = 0;
 int m;
 for (i = 0; i < N; i++) {
 clear(i);
 }
 while (!feof(in)) {
 fscanf(in, "%d", &m);
 printf("%d/n", m);
 set(m);
 }
 printf("abnother");
 for (i = 0; i < N; i++) {
 if (test(i)) {
  printf("%d/n", i);
  fprintf(out, "%d/n", i);
 }
 }
 fclose(in);
 fclose(out);
 return EXIT_SUCCESS;
}

6. 总结

位图算法是一种高效、快速的数据管理算法，广泛应用于各种计算场景。通过理解其内部工作原理，我们不仅可以更好地编写代码，还可以深入了解信息处理的基本需求和人类思维的一些方面。

希望这篇文章能帮助你深入了解位图算法在C/C++中的应用和原理。

结语

在我们的编程学习之旅中，理解是我们迈向更高层次的重要一步。然而，掌握新技能、新理念，始终需要时间和坚持。从心理学的角度看，学习往往伴随着不断的试错和调整，这就像是我们的大脑在逐渐优化其解决问题的“算法”。

这就是为什么当我们遇到错误，我们应该将其视为学习和进步的机会，而不仅仅是困扰。通过理解和解决这些问题，我们不仅可以修复当前的代码，更可以提升我们的编程能力，防止在未来的项目中犯相同的错误。

我鼓励大家积极参与进来，不断提升自己的编程技术。无论你是初学者还是有经验的开发者，我希望我的博客能对你的学习之路有所帮助。如果你觉得这篇文章有用，不妨点击收藏，或者留下你的评论分享你的见解和经验，也欢迎你对我博客的内容提出建议和问题。每一次的点赞、评论、分享和关注都是对我的最大支持，也是对我持续分享和创作的动力。