如何实现简单的位数组(bit array)(转)
数组 实现 如何 简单 Array bit
2023-09-27 14:28:14 时间
在 comp.lang.c 上面看到一则不错的 FAQ,《How can I implement sets or arrays of bits?》感觉很实用,仅仅使用了几个简单的宏就实现了一个基本的位数组(bitset)。
#include <limits.h> /* for CHAR_BIT */ #define BITMASK(b) (1 << ((b) % CHAR_BIT)) #define BITSLOT(b) ((b) / CHAR_BIT) #define BITSET(a, b) ((a)[BITSLOT(b)] |= BITMASK(b)) #define BITCLEAR(a, b) ((a)[BITSLOT(b)] &= ~BITMASK(b)) #define BITTEST(a, b) ((a)[BITSLOT(b)] & BITMASK(b)) #define BITNSLOTS(nb) ((nb + CHAR_BIT - 1) / CHAR_BIT)
下面是一些简单的例子:
- 声明一个固定长度(50个bit)的位数组:
char bitarray[BITNSLOTS(50)];
-
设置位数组中的某一位:
BITSET(bitarray, 23);
- 检测某一位
if(BITTEST(bitarray, 35)) ...
- 求两个位数组的并集
for(i = 0; i < BITNSLOTS(47); i++) array3[i] = array1[i] | array2[i];
- 求两个位数组的交集
for(i = 0; i < BITNSLOTS(47); i++) array3[i] = array1[i] & array2[i];
下面是一个完整的例子,利用 Sieve of Eratosthenes 算法求素数:
#include <stdio.h> #include <string.h> #define MAX 10000 int main() { char bitarray[BITNSLOTS(MAX)]; int i, j; memset(bitarray, 0, BITNSLOTS(MAX)); for(i = 2; i < MAX; i++) { if(!BITTEST(bitarray, i)) { printf("%d\n", i); for(j = i + i; j < MAX; j += i) BITSET(bitarray, j); } } return 0; }
相关文章
- Java 泛型的实际运用、使用数组实现栈
- .net 反射访问私有变量和私有方法 如何创建C# Closure ? C# 批量生成随机密码,必须包含数字和字母,并用加密算法加密 C#中的foreach和yield 数组为什么可以使用linq查询 C#中的 具名参数 和 可选参数 显示实现接口 异步CTP(Async CTP)为什么那样工作? C#多线程基础,适合新手了解 C#加快Bitmap的访问速度 C#实现对图片文件的压
- shell判断数组内是否包含某成员,获取数组长度
- php实现数组反转
- 【数据结构】队列-数组的实现
- 如何实现数组和List之间的转换?
- 【BZOJ1031】[JSOI2007]字符加密Cipher 后缀数组
- 指针数组 数组指针 函数指针 指针函数
- 《Unity着色器和屏幕特效开发秘笈(原书第2版)》一2.3 使用包装数组
- 数组的几种排序算法的实现
- 第三节:带你详解Java的操作符,控制流程以及数组
- 《Python数据分析》一1.4 NumPy数组
- 【Matlab】系统预定义变量——元胞数组与结构体
- 如何把JS对象转成数组
- JVM系列之:String,数组和集合类的内存占用大小
- 获取到数组的值
- java实现无序数组结构
- Swift - 数组
- Java小白入门200例31之检查数组是否包含某个元素
- 习题6.14 以m行n列二维数组为参数进行方法调用,分别计算二维数组各列元素之和,返回并输出所计算的结果。
- Python实现数组的插入排序