C#中BitArray类

简介

BitArray类用于以紧凑的方式表示"位的集合"(sets of bits). 虽然我们能把位的集合存储在常规数组内, 但是如果采用专门为位的集合设计的数据结构就能创建更加有效率的程序. 本章将会介绍如何使用这种数据结构, 并且将讨论一些利用位的集合所解决的问题. 此外, 本章节还包含二进制数、按位运算符以及位移(bit shift)运算符的内容。

1、素数问题

先来看一个最终会用BitArray类来解决的问题. 这个问题就是如何找到素数. 在公元前三世纪, 古希腊哲学家埃拉托色尼(Eratosthenes)发现了一种找素数的方法, 这种方法被称为是埃拉托色尼筛法(the sieve of Eratosthenes). 该方法会不断筛选掉是其他数字整数倍的那些数, 直到最后剩下的数都是素数为止. 例如, 假设要确定出前100 个整数集合内的素数. 这里会先从2 开始, 它是第一个素数. 接着从头到尾遍历整数集合, 把所有是2 倍数的整数都移除掉. 然后, 移动到下一个素数3. 还是此从头到尾遍历整数集合, 把所有是 3 倍数的整数都移除掉. 再随后移动到素数5, 继续如此往复操作. 当操作全部结束时, 所有留下的就都是素数了.
我们将首先使用常规数组来解决这个问题, 主要的方法规则与本节后面要介绍的使用BitArray解决问题的方法类似, 首先要初始化一个由100个元素组成的数组, 每个元素都设置为值1. 接着从索引2开始（因为2是第一个素数）, 检查每个后续数组索引的值是1还是0. 如果值为1, 则检查它是否为2的倍数. 如果是, 则该索引处的值设置为0, 直到检查完全部元素. 然后再从索引3开始, 使用3来检查值为1的索引与3的倍数关系, 依此类推, 直至每个索引都完成检查.
这里会借助先前章节开发的自定义CArray类. 第一件事就是创建一个筛选素数的方法. 代码如下所示：