Bitset改进你的程序质量

时间：2019-10-19 18:03:55 阅读：57 评论：0 收藏：0 [点我收藏+]

1:Bitset介绍

BitSet 是用于存储二进制位和对二进制进行操作的自动去重Java 数据结构,

此类实现了一个按需增长的位向量。位 set 的每个组件都有一个 boolean 值。用非负的整数将 BitSet 的位编入索引。可以对每个编入索引的位进行测试、设置或者清除。通过逻辑与、逻辑或和逻辑异或操作，可以使用一个 BitSet 修改另一个 BitSet 的内容。

默认情况下，set 中所有位的初始值都是 false。

2:优化空间

在程序runtime时,我们经常需要使用数组来记住程序的运行状态,并且根据这些状态及时对数据做出更新,一般有以下处理办法

使用 Int [] state=new int[22]; 保存状态
使用 boolean [] state = new boolean[22] 保存状态

分析可知,1byte=8bit int占用4个字节,如果考虑使用bit直接存储状态 ,将会大大节约时间, 不过在改变你的编程习惯之前,你应该清楚我们如何保存状态,以及对于状态的操作

3:Bitset常用api

构建

BitSet() 
          创建一个新的位 set。 默认64
BitSet(int nbits) 
          创建一个位 set，它的初始大小足以显式表示索引范围在 0 到 nbits-1 的位。  一般要求给出大小 当给出的值小于实际需要的值,会自动扩容

操作

更新:  
void set(int bitIndex) 
          将指定索引处的位设置为 true。 
 void set(int bitIndex, boolean value) 
          将指定索引处的位设置为指定的值。 
 void set(int fromIndex, int toIndex) 
          将指定的 fromIndex（包括）到指定的 toIndex（不包括）范围内的位设置为 true。 
 void set(int fromIndex, int toIndex, boolean value) 
          将指定的 fromIndex（包括）到指定的 toIndex（不包括）范围内的位设置为指定的值。 
获取:

`boolean`	`get(int bitIndex)` 返回指定索引处的位值。
`BitSet`	`get(int fromIndex, int toIndex)` 返回一个新的 `BitSet`，它由此 `BitSet` 中从 `fromIndex`（包括）到 `toIndex`（不包括）范围内的位组成。

翻转:

`boolean`	`get(int bitIndex)` 返回指定索引处的位值。
`BitSet`	`get(int fromIndex, int toIndex)` 返回一个新的 `BitSet`，它由此 `BitSet` 中从 `fromIndex`（包括）到 `toIndex`（不包括）范围内的位组成。


删除

`void`	`clear()` 将此 BitSet 中的所有位设置为 `false`。
`void`	`clear(int bitIndex)` 将索引指定处的位设置为 `false`。
`void`	`clear(int fromIndex, int toIndex)` 将指定的 `fromIndex`（包括）到指定的 `toIndex`（不包括）范围内的位设置为 `false`。


长度:

int cardinality()
返回此 BitSet 中设置为 true 的位数。

int length()
返回此 BitSet 的“逻辑大小”：BitSet 中最高设置位的索引加 1。

int size()
返回此 BitSet 表示位值时实际使用空间的位数。

重要: 遍历相关:

`int`	`nextClearBit(int fromIndex)` 返回第一个设置为 `false` 的位的索引，这发生在指定的起始索引或之后的索引上。
`int`	`nextSetBit(int fromIndex)` 返回第一个设置为 `true` 的位的索引，这发生在指定的起始索引或之后的索引上。

4.BitSet 应用举例

统计随机个数

    private final static int LEN_NUM = 10;
    public static void main(String[] args) {
        BitSet set = new BitSet();

        ArrayList<Integer> list = new ArrayList<>();

        Random random = new Random();
        for (int i = 0; i < LEN_NUM; i++) {
            list.add(random.nextInt(100));
        }
        for (int i = 0; i < list.size(); i++) {
            set.set(list.get(i));
        }
        for (int i = 0; i < 10; i++) {
            if(!set.get(i)) { //输出不在10范围以内的个数
                System.out.print(i+" ");
            }
        }
        System.out.println();
        System.out.println("有true的多少个"+set.cardinality());
    }

输出素数:

// 原始
    public static void main(String[] s) {
        int n = 1000000;
        long start = System.currentTimeMillis();
        int[] hash = new int[n + 1];
        for (int i = 2; i < n; i++) {
            if (hash[i] == 0) {
                for (int j = 2 * i; j < n; j += i) {
                    hash[j] = 1;
                }
            }
        }
        long end = System.currentTimeMillis();
        System.out.println((end - start) + " ms");
    }
// 改进后的

    public static void main(String[] args) {
        long start = System.currentTimeMillis();
        BitSet bitSet = new BitSet(10000000);
        for (int i = 2; i < 1000000; i++) {
            if(!bitSet.get(i)) {
                for (int j = i*2; j <1000000 ; j+=i) {
                    bitSet.set(j,true);
                }
            }
        }
        for (int i = 0; i < 1000000; i++) {
            if(!bitSet.get(i)) {
                System.out.println(i+" ");
            }
        }
        long end = System.currentTimeMillis();
        System.out.println((end - start) + " ms");
    }

Bitset改进你的程序质量

原文：https://www.cnblogs.com/dgwblog/p/11704541.html

踩

(0)

评论一句话评论（0）

分享档案

更多>

2021年09月23日 (328)
2021年09月24日 (313)
2021年09月17日 (191)
2021年09月15日 (369)
2021年09月16日 (411)
2021年09月13日 (439)
2021年09月11日 (398)
2021年09月12日 (393)
2021年09月10日 (160)
2021年09月08日 (222)