- 学习交流加（可免费帮忙下载CSDN资源）：
- 个人微信： liu1126137994
- 学习交流资源分享qq群1（已满）： 962535112
- 学习交流资源分享qq群2： 780902027
今天有朋友遇到一个笔试题：一个 4096位的bit数组，要找出前10个二进制的1 所在的位置，麻烦写一个函数来实现
bit数组对我来说是一个新的概念，故整理资料学习bit数组的概念~
加qq1126137994一起学习更多技术！！！
1、位数组的概念
所谓的位数组，主要是为了有效地利用内存空间而设计的一种存储数据的方式。在这种结构中一个整数在内存中用一位（1 bit）表示。这里所谓的表示就是如果整数存在，相应的二进制位就为1，否则为0。
主要思想：我们知道一个 char 类型的数据在内存中占用 1Byte（即 8 bit），如果我们用二进制位在内存中的顺序来代表整数则可以存储更多的信息。
这样的话，一个 char 类型可以存储 8个整数。假设 a是一个 char 数组的话，整数8就可以用 a[1] 的第一个二进制位表示了。那么512字节就是4096位，第一位代表0，第二位代表1，第三位代表2，第4096位代表4095，这样我们就可以用512字节存储4096个数了，大大的节省了内存空间。
这里的关键就是 一个char型能表示8个整数。
下面我实现一种利用 char 数组构造一个二进制数组。主要包括以下三个方面：：
将一个整数添加到二进制数组中 ：
void add_to_bitarray(char *bitarr, int num){ /* num代表要***数组中的数 */
bitarr[num >> SHIFT] |= (1 << (num & MASK)); /* MASK 为 0x7 */
}
该方法的主要作用是将二进制数组中表示该整数的位置为1。首先我们得找到该整数位于 char 数组的第几个元组中，这里利用该整数除以8即可（代码中除以8用右移三位实现），例如整数25位于25/8 = 3 余 1，表明该整数是用char 数组的第四个元素的第二位表示。那么在该元素的第几位可以利用该整数的后三位表示（0~7刚好可以表示8个位置），即 25 & 0x7 = 1，则代表25在该元素的第二位。将相应位置1，可以先将整数1左移相应位数，然后与二进制数组进行或操作即可。
判断一个整数是否在二进制数组中
int is_in_bitarray(char *bitarr, int num){
return bitarr[num >> SHIFT] & (1 << (num & MASK));
}
先找到该整数在二进制数组中的位置，然后判断该位是否为1，若是则表示该整数位于二进制数组中，反之不在数组中。
删除二进制数组中的一个整数
void clear_bitarray(char *bitarr, int num){
bitarr[num >> SHIFT] &= ~(1 << (num & MASK));
}
思路相同，先找到该整数在二进制数组中的位置，然后将该位置为0即可。
完整代码
完整的代码如下：
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define SHIFT 3
#define MASK 0x7
char *init_bitarray(int);
void add_to_bitarray(char *, int);
int is_in_bitarray(char *, int);
void clear_bitarray(char *, int);
void test(char *);
int main(){
char *arr;
arr = init_bitarray(100);
add_to_bitarray(arr, 25);
test(arr);
clear_bitarray(arr, 25);
test(arr);
getchar();
return 0;
}
char *init_bitarray(int size){
char *tmp;
tmp = (char*)malloc(size / 8 + 1);
memset(tmp, 0, (size / 8 + 1)); //initial to 0
return tmp;
}
void add_to_bitarray(char *bitarr, int num){ /* num代表要***数组中的数 */
bitarr[num >> SHIFT] |= (1 << (num & MASK));
}
int is_in_bitarray(char *bitarr, int num){
return bitarr[num >> SHIFT] & (1 << (num & MASK));
}
void clear_bitarray(char *bitarr, int num){
bitarr[num >> SHIFT] &= ~(1 << (num & MASK));
}
void test(char *bitarr){
if (is_in_bitarray(bitarr, 25) != 0)
printf("25 in\n");
else
printf("25 not in\n");
if (is_in_bitarray(bitarr, 30) != 0)
printf("30 in\n");
else
printf("30 not in\n");
}
以上是对位数组概念的理解，以及如何创建位数组！
在VS中运行结果如下：
- 下面来解决我们最开始留下的笔试题：
一个 4096位的bit数组，要找出前10个二进制的1 所在的位置，麻烦写一个函数来实现。
假设我们这个数组存储的是char类型的512字节，我们利用上面的函数，来构造bit数组，可以往特定的位填1，然后写出函数来查找前10个1所在的位置，并返回位置：
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define N_bit 4096
#define SHIFT 3
#define MASK 0x7
char *init_bitarray(int);
void add_to_bitarray(char *, int);
char *init_bitarray(int size){
char *tmp;
tmp = (char*)malloc(size / 8 + 1);
memset(tmp, 0, (size / 8 + 1)); //initial to 0
return tmp;
}
void add_to_bitarray(char *bitarr, int num){ /* num代表要***数组中的数 */
bitarr[num >> SHIFT] |= (1 << (8 - (num & MASK)));
}
void add_1_to_bitarr(char *bit_arr)
{
add_to_bitarray(bit_arr, 25);
add_to_bitarray(bit_arr, 28);
add_to_bitarray(bit_arr, 23);
add_to_bitarray(bit_arr, 67);
add_to_bitarray(bit_arr, 35);
add_to_bitarray(bit_arr, 36);
add_to_bitarray(bit_arr, 55);
add_to_bitarray(bit_arr, 69);
add_to_bitarray(bit_arr, 44);
add_to_bitarray(bit_arr, 97);
add_to_bitarray(bit_arr, 421);
add_to_bitarray(bit_arr, 564);
add_to_bitarray(bit_arr, 987);
add_to_bitarray(bit_arr, 684);
add_to_bitarray(bit_arr, 986);
add_to_bitarray(bit_arr, 658);
add_to_bitarray(bit_arr, 354);
add_to_bitarray(bit_arr, 764);
add_to_bitarray(bit_arr, 691);
add_to_bitarray(bit_arr, 36);
add_to_bitarray(bit_arr, 345);
}
int main()
{
char *bit_arr;
bit_arr = init_bitarray(4096);
add_1_to_bitarr(bit_arr);
int num[10];
int k = 1;
for (int i = 0; i < N_bit / 8 + 1; i++)
{
for (int j = 1; j < 8 && k <= 10; j++)
{
if ((bit_arr[i] & 128) == 128)
{
num[k] = i * 8 + j + 1;
k++;
}
bit_arr[i] <<= 1;
}
}
for (int n = 1; n <= 10; n++)
{
printf("第%d个1位置为:%d位\n", n, num[n]);
}
//getchar();
return 0;
}
运行结果为：
我们看到前10 个1 的位置都比我们填入到数组中的位置大1，是因为我们认为4096位是从第一个1开始，而数组是从第0号开始，所以产生了偏移！！！
到此我们已经用了一种方法来解决这个笔试题，同时也学会了一个新的概念，位数组！！！
京公网安备 11010502036488号