精华内容
下载资源
问答
  • bitset

    2016-08-14 08:19:59
    bitset

    构造函数

    #include < bitset >

    bitset< n > b;
    b有n位,每位都为0,参数n可以为一个表达式.
    如bitset<5> b0;则”b0”为”00000”;

    bitset< n > b(unsigned long u);
    b有n位,并用u赋值;如果u超过n位,则顶端被截除
    如:bitset<5>b0(5);则”b0”为”00101”;

    bitset< n > b(string s);
    b是string对象s中含有的位串的副本
    string bitval ( “10011” );
    bitset<5> b0 ( bitval4 );
    则”b0”为”10011”;

    赋值

    bitset重载了[]运算符,故可以像bool数组那样赋值
    bi[2] = 1;
    这样就能将第二位赋值为1

    常用函数

    b1 = b2 & b3;//按位与
    b1 = b2 | b3;//按位或
    b1 = b2 ^ b3;//按位异或
    b1 = ~b2;//按位补
    b1 = b2 << 3;//移位
    int one = b1.count();//统计1的个数

    bool any( )
    是否存在置为1的二进制位?和none()相反
    bool none( )
    是否不存在置为1的二进制位,即全部为0?和any()相反.
    size_t size( )
    二进制位的个数
    flip()
    把所有二进制位逐位取反
    set()
    把所有二进制位都置为1
    reset()
    把所有二进制位都置为0
    unsigned long to_ulong( )
    用同样的二进制位返回一个unsigned long值
    string to_string ()
    返回对应的字符串.

    习题

    UVALive 7272

    展开全文
  • BitSet

    2018-12-04 11:16:00
    Bitset类 一个Bitset类创建一种特殊类型的数组来保存值。BitSet中数组大小会随需要增加。这和位向量比较类似。 Java平台的BitSet用于存放一个位序列,如果要高效的存放一个位序列,就可以使用位集(BitSet)。由于位...

    Bitset类

    一个Bitset类创建一种特殊类型的数组来保存值。BitSet中数组大小会随需要增加。这和位向量比较类似。
    Java平台的BitSet用于存放一个位序列,如果要高效的存放一个位序列,就可以使用位集(BitSet)。由于位集将位包装在字节里,所以使用位集比使用Boolean对象的List更加高效和更加节省存储空间。
    BitSet是位操作的对象,值只有0或1即false和true,内部维护了一个long数组,初始只有一个long,所以BitSet最小的size是64,当随着存储的元素越来越多,BitSet内部会动态扩充,一次扩充64位,最终内部是由N个long来存储。
    默认情况下,BitSet的所有位都是false即0。
    在没有外部同步的情况下,多个线程操作一个BitSet是不安全的。
    一个1GB的空间,有8102410241024 = 8.5810^9bit,也就是1GB的空间可以表示85亿多个数。

    • 比如,一个BitSet是怎么存储数字0,2,4,6,8,10,12,14呢?
    对应值 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14
    1 0 1 0 1 0 1 0 1 0 1 0 1 0 1
    BitSet()
    

    第二个方法允许用户指定初始化大小。所有位初始化位0

    BitSet(int size)
    
    • void and(BitSet set)

    对此目标位 set 和参数位 set 执行逻辑与操作。

    • void andNot(BitSet set)

    清除此 BitSet 中所有的位,其相应的位在指定的 BitSet 中已设置。

    • int cardinality( )

    返回此 BitSet 中设置为 true 的位数。

    • void clear( )

    将此 BitSet 中的所有位设置为 false。

    • void clear(int index)

    将索引指定处的位设置为 false。

    • void clear(int startIndex, int endIndex)

    将指定的 fromIndex(包括)到指定的 toIndex(不包括)范围内的位设置为 false。

    • Object clone( )

    复制此 BitSet,生成一个与之相等的新 BitSet。

    • boolean equals(Object bitSet)

    将此对象与指定的对象进行比较。

    • void flip(int index)

    将指定索引处的位设置为其当前值的补码。

    • void flip(int startIndex, int endIndex)

    将指定的 fromIndex(包括)到指定的 toIndex(不包括)范围内的每个位设置为其当前值的补码。

    • boolean get(int index)

    返回指定索引处的位值。

    • BitSet get(int startIndex, int endIndex)

    返回一个新的 BitSet,它由此 BitSet 中从 fromIndex(包括)到 toIndex(不包括)范围内的位组成。

    • int hashCode( )

    返回此位 set 的哈希码值。

    • boolean intersects(BitSet bitSet)

    如果指定的 BitSet 中有设置为 true 的位,并且在此 BitSet 中也将其设置为 true,则返回 true。

    • boolean isEmpty( )

    如果此 BitSet 中没有包含任何设置为 true 的位,则返回 true。

    • int length( )

    返回此 BitSet 的"逻辑大小":BitSet 中最高设置位的索引加 1。

    • int nextClearBit(int startIndex)

    返回第一个设置为 false 的位的索引,这发生在指定的起始索引或之后的索引上。

    • int nextSetBit(int startIndex)

    返回第一个设置为 true 的位的索引,这发生在指定的起始索引或之后的索引上。

    • void or(BitSet bitSet)

    对此位 set 和位 set 参数执行逻辑或操作。

    • void set(int index)

    将指定索引处的位设置为 true。

    • void set(int index, boolean v)

    将指定索引处的位设置为指定的值。

    • void set(int startIndex, int endIndex)

    将指定的 fromIndex(包括)到指定的 toIndex(不包括)范围内的位设置为 true。

    • void set(int startIndex, int endIndex, boolean v)

    将指定的 fromIndex(包括)到指定的 toIndex(不包括)范围内的位设置为指定的值。

    • int size( )

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

    • String toString( )

    返回此位 set 的字符串表示形式。

    • void xor(BitSet bitSet)

    对此位 set 和位 set 参数执行逻辑异或操作。

    package com.java1995;
    
    import java.util.BitSet;
    
    public class BitSetTest {
        public static void main(String[] args){
            BitSet bits1 = new BitSet(16);
            BitSet bits2 = new BitSet(16);
    
            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("Initial pattern in bits2:");
            System.out.println(bits2);
    
            bits2.and(bits1);
            System.out.println("bits2 and bits1:");
            System.out.println(bits2);
    
            bits2.or(bits1);
            System.out.println("bits2 or bits1:");
            System.out.println(bits2);
    
            bits2.xor(bits1);
            System.out.println("bits2 xor bits1:");
            System.out.println(bits2);
        }
    }
    

    应用场景

    • 统计一组大数据中没有出现过的数

    将这组数据映射到BitSet,然后便利BitSet,对应位位0的数表示没有出现过的数据。

    • 对大数据进行排序

    将数据映射到BitSet,遍历BitSet得到的就是有序数据

    • 在内存对大数据进行压缩存储等等

    1GB的内容空间可以存储85亿多个数,可以有效实现数据的压缩存储,节省内存开销

    为什么BitSet使用long数组做内部存储?

    JDK选择long数组作为BitSet的内部存储结构是出于性能的考虑,因为BitSet提供and和or这种操作,需要对两个BitSet中的所有bit位做and或者or,实现的时候需要遍历所有的数组元素。使用long能够使得循环的次数降到最低,所以Java选择使用long数组作为BitSet的内部存储结构。
        从数据在栈上的存储来说,使用long和byte基本是没有什么差别的,除了编译器强制地址对齐的时候,使用byte最多会浪费7个字节(强制按照8的倍数做地址对其),另外从内存读数组元素的时候,也是没有什么区别的,因为汇编指令有对不同长度数据的mov指令。所以说,JDK选择使用long数组作为BitSet的内部存储结构的根本原因就是在and和or的时候减少循环次数,提高性能。
        例如我们进行BitSet中的and, or,xor操作时,要对整个bitset中的bit都进行操作,需要依次读出bitset中所有的word,如果是long数组存储,我们可以每次读入64个bit,而int数组存储时,只能每次读入32个bit。另外我们在查找bitset中下一个置为1的bit时,word首先会和0进行比较,如果word的值为0,则表示该word中没有为1的bit,可以忽略这个word,如果是long数组存储,可以一次跳过64个bit,如果是int数组存储时,一次只能跳过32个bit。
    展开全文
  • Bitset

    2019-09-29 13:22:12
    #include<iostream> #include<cstdio> #include<cstring> #include<string> #include<bitset> using namespace std; int main(){ bitset<16>A; bit...
    #include<iostream>
    #include<cstdio>
    #include<cstring>
    #include<string>
    #include<bitset>
    using namespace std;
    
    
    int main(){
        bitset<16>A;
        bitset<16>B(0xfa2);
        bitset<16>C(string("100000"));
        
        cout<<A<<endl;
        cout<<B<<endl;
        cout<<C<<endl;
        
        cout<<(A^=B)<<endl;
        cout<<(A|=B)<<endl;
        cout<<(A^=B)<<endl;
        
        cout<<(A<<=1)<<endl;
        cout<<(A<<1)<<endl;
        cout<<(~A)<<endl;
        
        cout<<(A==B)<<endl;
        cout<<(A!=B)<<endl;
        
        cout<<(A&B)<<endl;
        cout<<(A|B)<<endl;
        
        cout<<A.size()<<endl;
        cout<<A.count()<<endl;
        cout<<A.any()<<endl;
        cout<<A.none()<<endl;
       cout<<A.test()<<endl;

    A.
    set(); int p=0,x=1; A.set(p); A.set(p,x); A.reset(); A.reset(p); A.flip(); A.flip(p); A.to_ulong(); A.to_string(); return 0; }

     

    转载于:https://www.cnblogs.com/zzyer/p/8716241.html

    展开全文

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 8,845
精华内容 3,538
热门标签
关键字:

bitset