Skip to content

Add find_prev() and find_last() and their _off to boost::dynamic_bitset #109

Open

Description

@TheoBordillon

Description

Currently, boost::dynamic_bitset provides find_first() and find_next() to efficiently iterate over set bits (1) in ascending order, as well as find_first_off() and find_next_off() for unset bits (0).

However, there are no equivalent methods for searching bits in reverse order.

I would like to propose adding four methods:

  • find_last(): Returns the index of the last (highest) set bit.
  • find_prev(pos): Returns the index of the previous set bit strictly before pos.
  • find_last_off(): Returns the index of the last (highest) unset bit.
  • find_prev_off(pos): Returns the index of the previous unset bit strictly before pos.

All methods should return npos when no matching bit exists.

Proposed API

size_type find_last() const;
size_type find_prev(size_type pos) const;

size_type find_last_off() const;
size_type find_prev_off(size_type pos) const;

Example usage

boost::dynamic_bitset<> bs(10);
bs.set(2);
bs.set(5);
bs.set(8);

// Finding set bits (1)
assert(bs.find_last() == 8);
assert(bs.find_prev(8) == 5);
assert(bs.find_prev(5) == 2);
assert(bs.find_prev(2) == bs.npos);

// Finding unset bits (0)
assert(bs.find_last_off() == 9);
assert(bs.find_prev_off(9) == 7);
assert(bs.find_prev_off(7) == 6);
assert(bs.find_prev_off(1) == 0);
assert(bs.find_prev_off(0) == bs.npos);

Motivation

These methods would provide a symmetric API with the existing find_first(), find_next(), find_first_off(), and find_next_off() methods, allowing efficient traversal of both set and unset bits in either direction.

Although reverse searches can be implemented manually, having native implementations would allow Boost to optimize them at the block level, avoiding bit-by-bit scanning or unnecessary temporary bitset allocations.

This would be particularly useful for algorithms that frequently need to find the highest set or unset bit, or iterate over bits in descending order.

Thanks for considering this enhancement!

Activity

  1. changed the title [-]Add find_prev() and find_last() to boost::dynamic_bitset[/-] [+]Add find_prev() and find_last() and their _off to boost::dynamic_bitset[/+] on Nov 17, 2026
  2. gennaroprota commented on Nov 17, 2026

    @gennaroprota
    Collaborator

    I implemented find_prev() and find_last() (with slightly different names) in PR #103, upon another user's request. But, then, the user disappeared, so I didn't merge it (he was the only one to request them). I'll reconsider the request (and add the _off variants). Thanks.

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment

Metadata

Metadata

Assignees

No one assigned

    Labels

    No labels
    No labels

    Type

    No type

    Projects

    No projects

      Milestone

      No milestone

      Relationships

      None yet

      Development

      No branches or pull requests

      Issue actions