位图数据结构

_mystic

在看编程珠玑，看到了一个位图算法...

说：用一个20位长的内存空间可以表示一个所有元素都小于20的简单的非负整数集合。
比如 int a[6] = {1, 2, 3, 5, 8, 13}; 可以用如下方式表示
0 1 1 1 0 1 0 0 1 0 0 0 0 1 0 0 0 0 0 0

请问这是怎么计算出来的啊？

gawk

0 1 1 1 0 1 0 0 1 0 0 0 0 1 0 0 0 0 0 0
从最左边0开始数，每一个位加1，看看有什么效果?

皇家救星

不知道这样行不行
对于所有小于20的非负整数集合做编号
1 {}
2 {1}
3 {1,2}
...

在20位长的内存空间存着这个编号　根据编号反推集合

皇家救星

或者这样

对空间每个位做编号，分别记为1-20
对于每个位，用0表示存在于集合，用1表示不存在于集合

这样20个位正好能记录20个数

皇家救星

相当于一个只有一位的数组，可以考虑用位域来实现

_mystic

.....
一开始也是这么想的，但我是从右边往左数的,正好反了！！
呵呵 谢谢啊 脑子进水了

[ 本帖最后由 _mystic 于 2009-3-10 00:17 编辑 ]

_mystic

呵呵 谢谢啊 应该是你说的第二种方法。。。

_mystic

呵呵 两个人都是正确的答案。这个分数怎么给啊！！！
按先来后到吧。。。
皇家救星 感谢你的热情和帮助！

[ 本帖最后由 _mystic 于 2009-3-10 00:32 编辑 ]

system888net

原帖由 _mystic 于 2009-3-10 00:31 发表
呵呵 两个人都是正确的答案。这个分数怎么给啊！！！
按先来后到吧。。。
皇家救星 感谢你的热情和帮助！

感谢回帖的朋友,欣赏LZ的这种美德!

南无小和尚

我也看了，位图映射吧