SHARE
TWEET

Bitset with get segment

PloadyFree Nov 27th, 2018 (edited) 84 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. int type_size_bits = 6;
  2. int type_size = 1 << type_size_bits;
  3. int lastBits = (1 << type_size_bits) - 1;
  4.  
  5. class MyBitset {
  6.     long[] a;
  7.     int bucketCount;
  8.  
  9.     MyBitset(int size) {
  10.         if ((size & lastBits) != 0) size += lastBits;
  11.         bucketCount = size >> type_size_bits;
  12.         a = new long[bucketCount];
  13.     }
  14.  
  15.     void set(int at) {
  16.         a[at >> type_size_bits] |= 1L << (at & lastBits);
  17.     }
  18.  
  19.     boolean get(int at) {
  20.         long res = a[at >> type_size_bits] & (1L << (at & lastBits));
  21.         return res != 0;
  22.     }
  23.  
  24.     MyBitset get(int l, int r) {
  25.         int size = r - l + 1;
  26.         MyBitset res = new MyBitset(size);
  27.  
  28.         int startBucket = l >> type_size_bits;
  29.         int endBucket = r >> type_size_bits;
  30.         if (startBucket == endBucket) {
  31.             for (int i = l; i <= r; i++) {
  32.                 if (get(i)) {
  33.                     res.set(i - l);
  34.                 }
  35.             }
  36.             return res;
  37.         }
  38.  
  39.         int cutBits = 0;
  40.         if ((l & lastBits) != 0) {
  41.             for (int i = l; (i & lastBits) != 0; i++) {
  42.                 if (get(i)) {
  43.                     res.set(i - l);
  44.                 }
  45.                 cutBits++;
  46.             }
  47.             startBucket++;
  48.         }
  49.         if ((r & lastBits) != lastBits) {
  50.             for (int i = r; (i & lastBits) != lastBits; i--) {
  51.                 if (get(i)) {
  52.                     res.set(i - l);
  53.                 }
  54.             }
  55.             endBucket--;
  56.         }
  57.         for (int i = startBucket; i <= endBucket; i++) {
  58.             int bucket0 = i - startBucket;
  59.             long cur = a[i];
  60.             if (cutBits == 0) {
  61.                 res.a[bucket0] = cur;
  62.                 continue;
  63.             }
  64.             long head = cur & ((1L << (type_size - cutBits)) - 1);
  65.             long tail = cur ^ head;
  66.             res.a[bucket0] |= head << cutBits;
  67.             res.a[bucket0 + 1] |= tail >>> (type_size - cutBits);
  68.         }
  69.  
  70.         return res;
  71.     }
  72.  
  73.     void makeOr(MyBitset other) {
  74.         for (int i = 0; i < other.bucketCount; i++) {
  75.             a[i] |= other.a[i];
  76.         }
  77.     }
  78.  
  79.     @Override
  80.     public String toString() {
  81.         String s = "";
  82.         for (int i = 0; i < bucketCount; i++) {
  83.             for (int j = 0; j < type_size; j++) {
  84.                 if (((a[i] >> j) & 1) == 1) {
  85.                     s += (i * type_size + j) + " ";
  86.                 }
  87.             }
  88.         }
  89.         return s;
  90.     }
  91. }
RAW Paste Data
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy. OK, I Understand
 
Top