Hello, I recently needed to reduce the "weight" of the Boolean array to use a bit chain, for this I used vector<bool> , it worked very slowly, the bitset turned out to be faster, but not as much as I would like.

Actually a question.

  1. Is there a faster bitset alternative?
  2. And is it possible to make a two-dimensional bitset?

Thank you in advance.

    3 answers 3

    From bitset it is possible to make a matrix:

     template <size_t M, size_t N> class BitMatrix { private: typedef std::bitset<M * N> Data; public: bool operator() (size_t m, size_t n) const { return data_[m * N + n]; } typename Data::reference operator() (size_t m, size_t n) { return data_[m * N + n]; } private: std::bitset<M * N> data_; }; // ... BitMatrix<10, 20> m; m(1,1) = true; m(2,2) = false; std::cout << m(1,1) << m(2,2) << "\n";
    • one
      Why do we need such difficulties when you can make an array of bitsets with the usual [] indexing? std :: bitset <64> bits [32]; bits [5] [49] = true; - gammaker
    • Maybe because of a little more economical memory consumption, in general, with an array is really easier. - gkuznets

    Bit operations are generally not too fast.

    It is necessary to extract a byte (or better long) containing the specified bit, make the required mask shift, possibly invert it (to reset the bit), test or change and write the byte back.

    Perhaps you should do it yourself (apparently without calling functions (or try static inline functions)), it may be possible to speed up the algorithm if you have any specific (according to the logic of the problem) dependencies between groups of bits. For example, sometimes you can greatly improve performance by checking the byte (or word) for zero and not testing individual bits there.

    • Clearly, please answer 2 points, can there already exist headers / libraries for a two-dimensional bitset? - username76
    • By the way, for acceleration, you can calculate the necessary bit masks in advance, and then only apply them. - insolor
    • Regarding 2, the usual array of long can be considered a two-dimensional bitmap of 32 * n bits. In general, it all depends on the specific task. - insolor
    • And how to do it? - username76
    • one
      About the task: if the nodes are small and there are many connections, then it is easier to use a two-dimensional bool array. And if, on the contrary, there are a lot of nodes, and there are few links, it is more advantageous to use not the adjacency matrix, but the list of edges. If there are about a million nodes, then no dense packing of bits will help. - insolor

    Is there a faster bitset alternative?

    Not. If it were possible to do it faster, bitset, I think, would do it faster. A bit does not have a separate address; in order to access a specific bit, you need to refer to the byte in which it is located and determine it using the shift and mask. If you have a weak point in working with bats, try to implement it yourself, perhaps even in assembly language.

    And is it possible to make a two-dimensional bitset?

    What's the problem? You do an array bitset and that's it.