uamer's blog

About Bitset in c++ !!
By uamer, 3 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

»
3 years ago, # |
  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
  • »
    »
    3 years ago, # ^ |
      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
    • »
      »
      »
      3 years ago, # ^ |
        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