Codeforces Round 1133 (Div. 1, Div. 2) is coming soon! Register here. ×

uamer's blog

About Bitset in c++ !!
By uamer, 4 years ago, In English

with bitset<2001> bits[1000][1000];

what time complexity of operation shifting ( =<< or =>> ) !!

and what is Memory ?

  • Vote: I like it
  • +1
  • Vote: I do not like it

»
4 years ago, hide # |
 
Vote: I like it 0 Vote: I do not like it

Standard doesn't says anything about it, but I think it's safe to assume, that bitsets inside just static array of unsigned numbers. So shifting must be just loop over that array. So complexity would be O(N / bits_per_number). And what memory you are asking?

→ Reply
  • »
    »
    4 years ago, hide # ^ |
     
    Vote: I like it 0 Vote: I do not like it

    so time complexity this operation bits[ 1 ][1] |= ( bits[ 0 ][0] >> 1 ) take O( 1 ) !

    → Reply
    • »
      »
      »
      4 years ago, hide # ^ |
       
      Vote: I like it 0 Vote: I do not like it

      O(1) with big constant (if bitset stores 32bit numbers that it would be ceil(2001 / 32) = 66)

      → Reply