位图算法-速度之巅

C/C++位图class="superseo">算法 前提条件

应用场景假设

• 假如需要在一堆数字当中快速找到一个数是否存在在这堆数组中
• 例如：2，5，9，55 ，需确定55是否存在在这堆数组中

算法原理

• 我们都应该知道1个字节有8位二进制（硬件的基本单位是位（bit），1位代表的就是0或1）

使用一块内存来标记已存在的数，将这块内存全部清0（这时候每一位都是0），假设已有（74，5， 99）我们在这一块内存中对应位标志为1，也就是说在第5位标志为1，第74位标志为1，第99位标志为1，其余位是0 简单的讲数字（74）标志在第74位也就是第10个字节的第3位，如果我们从0数起就是第9个字节第2位，因为一个字节有8位所以就是74除8等于9余2 我们在查找的时候只需要找到对应字节的对应位，然后确定是否为1，如果为0则不存在 如图是表示（74，5，99）这三个数 图1-1. 整数（74）

图1-2. 整数（5）

图1-3. 整数（99）

注意这是用一块内存！！！ 使用c语言来实现

• 简洁版

char* initBit(int* nums, int numsSize, int mallocSize) {

	char* origin = (char*)malloc(mallocSize);

	memset(origin, 0, mallocSize);

	for (int i = 0; i < numsSize; i++) {
		char* position = origin + nums[i] / 8;
		*position = *position | (1 << (nums[i] % 8));
	}

	return origin;
}

bool query(char* memory, int value) {

	memory = memory + value / 8;
	return *memory & (1 << (value % 8));
}

• 注释版

#include 
#include 

char* initBit(int* nums, int numsSize, int mallocSize) {

	//分配一块mallocSize大小的内存
	char* origin = (char*)malloc(mallocSize);

	//将这块内存中所有字节置空
	memset(origin, 0, mallocSize);

	for (int i = 0; i < numsSize; i++) {
		//指向具体的字节
		char* position = origin + nums[i] / 8;

		//指向具体位（bit）        取8的余数，假设余x，1就左移x（因为1的二进制就是1） 
		*position = *position | (1 << (nums[i] % 8));
	}

	return origin;
}

bool query(char* memory, int value) {
	//指向具体的字节
	memory = memory + value / 8;

	//指向具体位（bit）
	return *memory & (1 << (value % 8));
}

int main(void) {

	int nums[8] = { 75, 5, 99 };
	char* memory = initBit(nums, sizeof(nums) / sizeof(nums[0]), 1024);

	int input = 1;

	while (input) {
		scanf_s("%d", &input);
		printf("是否存在:%d\n",query(memory, input));
	}

	return 0;
}

------------奇牛学院