ddddfang's Blog.

bit-set

bitmap
字数统计: 924阅读时长: 3 min
2019/01/31 Share

如何实现简单的位数组(bit array) ref

以下摘自 How can I implement sets or arrays of bits？，仅使用几个简单的宏就实现了一个基本的位数组（bitset，又名 bitmap）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
#include <limits.h>        /* for CHAR_BIT */

//CHAR_BIT is the number of bits in char,almost all architectures
//use 8 bits per byte but it is not the case always

//作为utils使用
#define BITMASK(b) (1 << ((b) % CHAR_BIT))
#define BITSLOT(b) ((b) / CHAR_BIT)

//将bitset数组a[]的第b个bit置1
#define BITSET(a, b) ((a)[BITSLOT(b)] |= BITMASK(b))
//将bitset数组a[]的第b个bit清0
#define BITCLEAR(a, b) ((a)[BITSLOT(b)] &= ~BITMASK(b))
//将bitset数组a[]的第b个bit反转
#define BITREVERSE(a, b) ((a)[BITSLOT(b)] ^= BITMASK(b))
//测试bitset数组a[]的第b个bit是否为1
#define BITTEST(a, b) ((a)[BITSLOT(b)] & BITMASK(b))

//计算 若有nb个bit，则 bitset a[] 需要分配的字节数
#define BITNSLOTS(nb) ((nb + CHAR_BIT - 1) / CHAR_BIT)

下面是一些简单的例子：

1
2
3
4
5
6
7
8
9
10
11
12
//    声明一个固定长度（50个bit）的位数组：
char bitarray[BITNSLOTS(50)];
//    设置位数组中的某一位：
BITSET(bitarray, 23);
//    检测某一位
if(BITTEST(bitarray, 35)) ...
//    求两个位数组的并集
for(i = 0; i < BITNSLOTS(47); i++)
    bitarray3[i] = bitarray1[i] | bitarray2[i];
//    求两个位数组的交集
for(i = 0; i < BITNSLOTS(47); i++)
    bitarray3[i] = bitarray1[i] & bitarray2[i];

下面是一个完整的例子，利用 Sieve of Eratosthenes 算法求素数（质数） (这个算法在【语言学习】python2.2 那里讲 filter 的时候有说明)：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
#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;
}
  • bitset在《编程珠玑》ch01即有讲到，在对数据进行排序，当输入满足以下条件, 可使用bitset实现O(n)排序
    • 正整数
    • 在已知的范围内
    • 不重复时
  • bitmap的一个延伸就是2-bit的概念（每个数分配2bit，00表示不存在，01表示出现一次，10表示多次，11无意义）当然还有intmap的概念，这样不仅可以统计某个index代表的数有没有出现，还可以统计其出现的次数。不过这样的前提是对目标集合的分布范围已知。当目标集合分布的范围很大，而实际的个数却很少的时候（稀疏的），这类map其实还是很浪费空间的。
  • hashmap? bitmap/intmap 可以看作 key 和 val 都只能是 int 类型的map（因为数组的index只能是 int 呀）。hashmap的key和val可以是任何类型，内部经过哈希函数将 key 转化为int 类型的 数组 index. hashmap内建集合set 的功能。
  • bitset 可以用于实现 布隆过滤器（有点像是一种集合set ） 可以参看 这里.
    bitset通过将某一个bit 置1 或 清0 可以实现一个集合的效果。但是当数据分布不可知时候，空间占用量会很大。
    如果我们只是想知道某个元素是否已经存在于集合中，可以使用布隆过滤器（通过多个bit来标识某个数据） 啊。
    eg.使用三个hash函数，当给出一个数据，算出三个不同的hash值，然后将bitset对应的位置都置1。
    因此只要数据存在于集合中，则此三个位置必然全1。
    集合里有该元素，则bloomfilter查找结果一定为有
    集合里没有改元素，bloomfilter查找结果不一定为无！
    bloom 在时间和空间都不能牺牲的情况下，只能牺牲正确率了………

原文作者：ddddfang

原文链接：https://ddddfang.github.io/2019/01/31/bit-set/

发表日期：January 31st 2019, 5:57:48 pm

更新日期：January 31st 2019, 6:09:31 pm

版权声明：本文采用知识共享署名-非商业性使用 4.0 国际许可协议进行许可

CATALOG
  1. 1. 如何实现简单的位数组(bit array) ref
Total : 42
2019
binary-search bitmap caffe c++ 单例模式 common misc makefile 宏 顺序容器 智能指针 排序 shell linux command docker blog ffmpeg gdb gitbook p4 printf 可变参数 static and dynamic library 第k小的数 ubuntu setup 并查集 git draw.io markdown vscode office2016 密钥 键值对集合 链表 最大堆(大顶堆) swig python c vim 红黑树 skip-list hash-table
algorithm-and-data-struct caffe common-misc cpp linux-daily ffmpeg