Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

Efficient way of iterating over true bits in std::bitset?

Is there a way of iterating over a (possibly huge) std::bitset that is linear in the number of bits that are set to true? I want to prevent having to check every single position in the bitset. The iteration should successively return the indices of each bit that is set to true.

like image 882
Astyanax Avatar asked Sep 04 '25 01:09

Astyanax


1 Answers

A standard bitvector does not support efficient iteration over true bits - the runtime is always O(n), where n is the number of total bits, which has no dependence on k. However, there are specialized data structures like van Emde Boas trees and y-fast tries, that support iteration over the bits in time O(k lg lg n), where n is the number of bits and k is the number of true bits.

like image 144
templatetypedef Avatar answered Sep 07 '25 04:09

templatetypedef