《编程珠玑》读书笔记(一)
本文关键词:编程珠玑,由笔耕文化传播整理发布。
第一章
以下转载自
位向量的定义和应用:位向量/位图在充分利用小空间存储大数据方面很有优势。Linux内核中很多用到了位向量。
一般地,对于多个对象和一个性质,这些对象可能满足(true)也可能不满足(false)这条性质。那么,为了表示所有对象对这个性质的满足情况,最容易想到的方式是分配一个int型变量(这里不讨论布尔型,C++没有对布尔型占用空间有明确规定;本文主要讨论C)作为标志,用1表示满足条件,用0表示不满足条件。同时为了方便查询,把这些对象的标志整合成一个数组。显然,使用int来表示是0还是1有些太浪费空间了,即使把int改为char,浪费的情况也只是减轻了一部分,仍有很大的空间被浪费。考虑到计算机中最小的数据单位是非0即1的二进制位,对于一个对象,使用一个二进制位就足够了。很多语言都具有位运算,利用位运算是可以完成本段开始处提出的要求的。当然,因为不能用一个变量名直接表示一个位,那么可以将多个位组合成一个基本数据类型,通过对这个基本数据类型进行操作,达到使用位的方法。同时,为了方便,延续使用int数组的做法,把这些由位组合成的基本数据类型也组成数组。
经过这样分析,位向量的实现方法大体是:多个位组成一个基本数据类型,基本数据类型组合成数组。根据这个思路就可以写出位向量的表示了。在阅读下面代码前,建议读者尝试自己独立完成,这是一些提示:简单起见,使用int作为位组成的基本数据类型,且int使用32位表示;int数组中元素的个数如何计算?
#define N 10000000 //number of elements #define BITPERWORD 32 //bits of int depends on machine int a[(N-1)/BITPERWORD + 1]; //allocate space for bitmap //《编程珠玑》原书中是N/BITPERWORD + 1 //如果N恰为BITPERWORD的倍数,那么又要浪费一个int的空间了 //N取0时,仍会浪费一个int的空间 //N非0非BITPERWORD的倍数时,最多是最后一个int不完全利用而已写完了表示,,就需要为这个数据结构增加对应的操作了。对于每个位的操作,有三种:设置为0、设置为1、读取当前值。根据上文位向量的表示,实现这三种操作。同样建议读者先尝试独立完成。以下代码参考自《编程珠玑》习题1.2。 #define SHIFT 5 //32 = 2^5 #define MASK 0x1F // vaule 11111 in binary //i代表需要进行操作的第i个对象 //i>>SHIFT相当于i/32,将i定位到具体是哪个int中,即a[i>>SHIFT] //i&MASK相当于i%32 只保留i的0至4位,即i在int中的第几位,然后把1左移这么多位 //将a[i>>SHIFT]和(1<<(i&MASK))视需要进行操作 //同1做或运算或即为位设置 //同1取反再做与运算即为位清除 //同1做与,结果为0则原位为0,为1则原位为1 void set(int i) { a[i>>SHIFT] |= (1<<(i&MASK));} void clr(int i) { a[i>>SHIFT] &= ~(1<<(i&MASK));} void test(int i) { return a[i>>SHIFT] & (1<<(i&MASK));} 使用位向量前不要忘记对所有位进行初始化:for(i=0;i<N;i++) clr(i);Q:为什么不用看上去比较直接的i / 32或者i % 32?
A:提高效率
本文关键词:编程珠玑,由笔耕文化传播整理发布。
本文编号:330781
本文链接:https://www.wllwen.com/wenshubaike/mishujinen/330781.html