Secret.Codes's blog

Help on Bitset
By Secret.Codes, 6 years ago, In English

Does bitset optimize time ? or memory only?

Let there is an array ara[n] and a bitset a , both has size n. . if we access the array with a for loop as for(int i=0;i<n;i++)ara[i] the complexity is O(n). Now if we access the bitset as for(int i=0;i<n;i++)a[i] then what is the complexity? O(n) or O(n/32)??

  • Vote: I like it
  • -4
  • Vote: I do not like it

»
6 years ago, # |
← Rev. 2   Vote: I like it +8 Vote: I do not like it

Complexity is O(n). What is bitset? This is array of (n + 31) / 32 uint32_t items or (n + 63) / 64 uint64_t items.

set / unset / get operations:

typedef uint64_t ull;
ull bitset[(n+63)/64];
bitset[pos / 64] |=  (ull(1) << pos % 64);      // set array[pos] = 1
bitset[pos / 64] &= ~(ull(1) << pos % 64));     // set array[pos] = 0
int value = (bitset[pos / 64] >> pos % 64) & 1; // get array[pos]

Your cycle equivalent to:

for (int i = 0; i < n; ++i) {
    value = (bitset[i / 64] >> i % 64) & 1;
}

But XOR, AND, SHIFT and other require  ≈ N / 64 operations

→ Reply