G2A Many GEOs
SHARE
TWEET

Bitset with get segment

PloadyFree Nov 27th, 2018 (edited) 86 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
Ledger Nano X - The secure hardware wallet
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