java BitSet类

偏执的太偏执、 2021-06-22 15:37 393阅读 0赞

我们先来看一下java.utils.BitSet类的介绍。

一个Bitset类创建一种特殊类型的数组来保存位值。BitSet中数组大小会随需要增加。这和位向量（vector of bits）比较类似。这是一个传统的类，但它在Java 2中被完全重新设计。

**1、构造方法：**

BitSet bs2 = new BitSet();
    或者
    BitSet bs2 = new BitSet(n);

BitSet默认创建大小64位，当超过后会自动扩容，扩容时按照64的倍数进行扩容（128、192...）。在构造函数中指定的n，如果小于64，则按照64位初始化，大于64小于128，按照128初始化，一次类推。。。

**2、常用方法：**

<table> 
 <tbody> 
 <tr> 
 <th>序号</th> 
 <th>方法描述</th> 
 </tr> 
 <tr> 
 <td>1</td> 
 <td>void and(BitSet set) 对此目标位 set 和参数位 set 执行逻辑与操作。</td> 
 </tr> 
 <tr> 
 <td>2</td> 
 <td>void andNot(BitSet set) 清除此&nbsp;BitSet&nbsp;中所有的位，其相应的位在指定的&nbsp;BitSet&nbsp;中已设置。</td> 
 </tr> 
 <tr> 
 <td>3</td> 
 <td>int cardinality( ) 返回此&nbsp;BitSet&nbsp;中设置为&nbsp;true&nbsp;的位数。</td> 
 </tr> 
 <tr> 
 <td>4</td> 
 <td>void clear( ) 将此 BitSet 中的所有位设置为&nbsp;false。</td> 
 </tr> 
 <tr> 
 <td>5</td> 
 <td>void clear(int index) 将索引指定处的位设置为&nbsp;false。</td> 
 </tr> 
 <tr> 
 <td>6</td> 
 <td>void clear(int startIndex, int endIndex) 将指定的 startIndex（包括）到指定的 toIndex（不包括）范围内的位设置为 false。</td> 
 </tr> 
 <tr> 
 <td>7</td> 
 <td>Object clone( ) 复制此&nbsp;BitSet，生成一个与之相等的新&nbsp;BitSet。</td> 
 </tr> 
 <tr> 
 <td>8</td> 
 <td>boolean equals(Object bitSet) 将此对象与指定的对象进行比较。</td> 
 </tr> 
 <tr> 
 <td>9</td> 
 <td>void flip(int index) 将指定索引处的位设置为其当前值的补码。</td> 
 </tr> 
 <tr> 
 <td>10</td> 
 <td>void flip(int startIndex, int endIndex) 将指定的&nbsp;fromIndex（包括）到指定的&nbsp;toIndex（不包括）范围内的每个位设置为其当前值的补码。</td> 
 </tr> 
 <tr> 
 <td>11</td> 
 <td>boolean get(int index) 返回指定索引处的位值。</td> 
 </tr> 
 <tr> 
 <td>12</td> 
 <td>BitSet get(int startIndex, int endIndex) 返回一个新的&nbsp;BitSet，它由此&nbsp;BitSet&nbsp;中从&nbsp;fromIndex（包括）到&nbsp;toIndex（不包括）范围内的位组成。</td> 
 </tr> 
 <tr> 
 <td>13</td> 
 <td>int hashCode( ) 返回此位 set 的哈希码值。</td> 
 </tr> 
 <tr> 
 <td>14</td> 
 <td>boolean intersects(BitSet bitSet) 如果指定的&nbsp;BitSet&nbsp;中有设置为&nbsp;true&nbsp;的位，并且在此&nbsp;BitSet&nbsp;中也将其设置为&nbsp;true，则返回 true。</td> 
 </tr> 
 <tr> 
 <td>15</td> 
 <td>boolean isEmpty( ) 如果此&nbsp;BitSet&nbsp;中没有包含任何设置为&nbsp;true&nbsp;的位，则返回 true。</td> 
 </tr> 
 <tr> 
 <td>16</td> 
 <td>int length( ) 返回此&nbsp;BitSet&nbsp;的"逻辑大小"：BitSet&nbsp;中最高设置位的索引加 1。</td> 
 </tr> 
 <tr> 
 <td>17</td> 
 <td>int nextClearBit(int startIndex) 返回第一个设置为&nbsp;false&nbsp;的位的索引，这发生在指定的起始索引或之后的索引上。</td> 
 </tr> 
 <tr> 
 <td>18</td> 
 <td>int nextSetBit(int startIndex) 返回第一个设置为&nbsp;true&nbsp;的位的索引，这发生在指定的起始索引或之后的索引上。</td> 
 </tr> 
 <tr> 
 <td>19</td> 
 <td>void or(BitSet bitSet) 对此位 set 和位 set 参数执行逻辑或操作。</td> 
 </tr> 
 <tr> 
 <td>20</td> 
 <td>void set(int index) 将指定索引处的位设置为&nbsp;true。</td> 
 </tr> 
 <tr> 
 <td>21</td> 
 <td>void set(int index, boolean v) &nbsp;将指定索引处的位设置为指定的值。</td> 
 </tr> 
 <tr> 
 <td>22</td> 
 <td>void set(int startIndex, int endIndex) 将指定的&nbsp;fromIndex（包括）到指定的&nbsp;toIndex（不包括）范围内的位设置为&nbsp;true。</td> 
 </tr> 
 <tr> 
 <td>23</td> 
 <td>void set(int startIndex, int endIndex, boolean v) 将指定的&nbsp;fromIndex（包括）到指定的&nbsp;toIndex（不包括）范围内的位设置为指定的值。</td> 
 </tr> 
 <tr> 
 <td>24</td> 
 <td>int size( ) 返回此&nbsp;BitSet&nbsp;表示位值时实际使用空间的位数。</td> 
 </tr> 
 <tr> 
 <td>25</td> 
 <td>String toString( ) 返回此位 set 的字符串表示形式。</td> 
 </tr> 
 <tr> 
 <td>26</td> 
 <td>void xor(BitSet bitSet) 对此位 set 和位 set 参数执行逻辑异或操作。</td> 
 </tr> 
 </tbody> 
</table>

3、示例：

import java.util.BitSet;
 
 public class BitSetDemo {
 
 public static void main(String args[]) {
 BitSet bits1 = new BitSet(16);
 BitSet bits2 = new BitSet(16);
 
 // set some bits
 for(int i=0; i<16; i++) {
 if((i%2) == 0) bits1.set(i);
 if((i%5) != 0) bits2.set(i);
 }
 System.out.println("Initial pattern in bits1: ");
 System.out.println(bits1);
 System.out.println("\nInitial pattern in bits2: ");
 System.out.println(bits2);
 
 // AND bits
 bits2.and(bits1);
 System.out.println("\nbits2 AND bits1: ");
 System.out.println(bits2);
 
 // OR bits
 bits2.or(bits1);
 System.out.println("\nbits2 OR bits1: ");
 System.out.println(bits2);
 
 // XOR bits
 bits2.xor(bits1);
 System.out.println("\nbits2 XOR bits1: ");
 System.out.println(bits2);
 }
 }
 
 输出：
 Initial pattern in bits1:
 {0, 2, 4, 6, 8, 10, 12, 14}
 
 Initial pattern in bits2:
 {1, 2, 3, 4, 6, 7, 8, 9, 11, 12, 13, 14}
 
 bits2 AND bits1:
 {2, 4, 6, 8, 12, 14}
 
 bits2 OR bits1:
 {0, 2, 4, 6, 8, 10, 12, 14}
 
 bits2 XOR bits1:
 {}

参考：[https://www.runoob.com/java/java-bitset-class.html][https_www.runoob.com_java_java-bitset-class.html]

接下来我们谈一下bitMap这种数据结构的应用。（java中对应的是bitSet类，非线程安全）

计算机中一个字节（byte）占8位（bit），在java中数据至少按字节存储的，比如一个int占4个字节。如果遇到大的数据量，这样必然会需要很大存储空间和内存。如何减少数据占用存储空间和内存可以用算法解决。

有这样一个问题：给40亿个不重复的unsigned int的整数，没排序。再给一个数，快速判断这个数是否存在40亿个整数中？内存限制2G。40亿个数，我们先看内存占用：（40亿\*4）/1024/1024/1024=14.9G （int 占4字节32bit）所以用传统的内存排序肯定不可以。使用bitmap结构，用一个bit位来标识一个int整数，这样需要的内存空间为：40亿/8/1024/1024=476M。

假设我们要对5个不重复的数（4，7，2，5，3）排序。确定最大值是7，数值范围是0~7，共8个数，需要8bit，即1byte。

从0计数，从右往左，即：00000000 –> 76543210，最终结果为10111100，遍历这8个bit位，将值为1输出，排序结果为 （7，5，4，3，2）。代码如下：

public static void main(String[] args) { 
 int[] intArray = { 4, 7, 2, 5, 3 };
 BitSet bitSet = new BitSet(8);
 
 for (int i = 0; i < intArray.length; i++) {
 bitSet.set(intArray[i], true);
 }
 
 System.out.println(bitSet);
 }

说明：Bitmap排序需要的时间复杂度和空间复杂度依赖于数据中最大的数字，比如上例中的7。当数据类似（1，1000，10万）只有3个数据的时候，用bitmap时间复杂度和空间复杂度相当大，只有当数据比较密集时才有优势。

同类问题：  
【1】已知某个文件内包含一些电话号码，每个号码为8个数字，统计不同号码的个数。  
解决方法： 8位最多99999999,占用100,000,000个bit,大小为12MB，这样用12M内存就表示来所有8位数的电话。

【2】2.5亿个整数中找出不重复的整数的个数，内存空间不足以同时容纳这2.5亿个整数。  
解决方法： 将bitmap扩展一下，用2bit表示一个数即可，0表示未出现，1表示出现一次，2表示出现2次及以上，在遍历这些数的时候，如果对应位置的值是0，则将其置为1；如果是1，将其置为2；如果是2，则保持不变。或者我们不用2bit来进行表示，我们用两个bit-map即可模拟实现这个2bit-map，都是一样的道理。

【3】对10亿个不重复的整数进行排序。  
【4】找出10亿个数字中重复的数字。  
解决方法：bitmap初始化数据，当发现数组中的值是1，则判断出该数字是重复出现的。

【5】一个序列里除了一个元素，其他元素都会重复出现3次，设计一个时间复杂度与空间复杂度最低的算法，找出这个不重复的元素。

[https_www.runoob.com_java_java-bitset-class.html]: https://www.runoob.com/java/java-bitset-class.html