连云港网站推广优化,wordpress 盗链,品牌网站建设 优帮云,凡客诚品app学习交流加#xff08;可免费帮忙下载CSDN资源#xff09;#xff1a;个人微信#xff1a; liu1126137994学习交流资源分享qq群1#xff08;已满#xff09;#xff1a; 962535112学习交流资源分享qq群2#xff1a; 780902027 今天有朋友遇到一个笔试题#xff1a;一个… 学习交流加可免费帮忙下载CSDN资源个人微信 liu1126137994学习交流资源分享qq群1已满 962535112学习交流资源分享qq群2 780902027 今天有朋友遇到一个笔试题一个 4096位的bit数组要找出前10个二进制的1 所在的位置麻烦写一个函数来实现
bit数组对我来说是一个新的概念故整理资料学习bit数组的概念~
加qq1126137994一起学习更多技术
文章目录1、位数组的概念将一个整数添加到二进制数组中 判断一个整数是否在二进制数组中删除二进制数组中的一个整数完整代码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);elseprintf(25 not in\n);if (is_in_bitarray(bitarr, 30) ! 0)printf(30 in\n);elseprintf(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号开始所以产生了偏移
到此我们已经用了一种方法来解决这个笔试题同时也学会了一个新的概念位数组
