Submask Enumeration
(algo/enumeration/submask.hpp)

• View this file on GitHub
• Last update: 2026-07-07 22:10:04+09:00
• Include: #include "algo/enumeration/submask.hpp"

Overview

This header wraps common bitmask loops for submasks and supermasks. The public namespace is m1une::algo.

UInt must be an unsigned integral type other than bool.

Functions

Function	Description	Complexity
for_each_submask(mask, f)	Calls f(submask) for every submask of mask, including zero.	$O(2^K)$
for_each_nonzero_submask(mask, f)	Calls f(submask) for every nonzero submask of mask.	$O(2^K)$
for_each_supermask(mask, bit_count, f)	Calls f(supermask) for every supermask within bit_count bits.	$O(2^{B-K})$

Here $K$ is the popcount of mask, and $B$ is bit_count. Submasks are generated in descending numeric order. Supermasks are generated by descending order of the free added bits.

Example

#include "algo/enumeration/submask.hpp"

#include <cstdint>

int main() {
    std::uint32_t mask = 0b1011;
    int count = 0;
    m1une::algo::for_each_nonzero_submask(mask, [&](std::uint32_t submask) {
        (void)submask;
        ++count;
    });
}

Required by

• Algorithms All (algo/all.hpp)
• Enumeration Algorithms All (algo/enumeration/all.hpp)

Verified with

• verify/algo/enumeration/submask.test.cpp

Code

#ifndef M1UNE_ALGO_ENUMERATION_SUBMASK_HPP
#define M1UNE_ALGO_ENUMERATION_SUBMASK_HPP 1

#include <cassert>
#include <concepts>
#include <limits>
#include <type_traits>

namespace m1une {
namespace algo {

namespace internal {

template <std::unsigned_integral UInt>
requires(!std::same_as<std::remove_cv_t<UInt>, bool>)
UInt submask_low_bits(int bit_count) {
    constexpr int digits = std::numeric_limits<UInt>::digits;
    assert(0 <= bit_count && bit_count <= digits);
    if (bit_count == digits) return ~UInt(0);
    return (UInt(1) << bit_count) - UInt(1);
}

}  // namespace internal

template <std::unsigned_integral UInt, class F>
requires(!std::same_as<std::remove_cv_t<UInt>, bool>)
void for_each_submask(UInt mask, F f) {
    UInt submask = mask;
    while (true) {
        f(submask);
        if (submask == 0) break;
        submask = (submask - 1) & mask;
    }
}

template <std::unsigned_integral UInt, class F>
requires(!std::same_as<std::remove_cv_t<UInt>, bool>)
void for_each_nonzero_submask(UInt mask, F f) {
    for (UInt submask = mask; submask != 0; submask = (submask - 1) & mask) {
        f(submask);
    }
}

template <std::unsigned_integral UInt, class F>
requires(!std::same_as<std::remove_cv_t<UInt>, bool>)
void for_each_supermask(UInt mask, int bit_count, F f) {
    const UInt universe = internal::submask_low_bits<UInt>(bit_count);
    assert((mask & ~universe) == 0);
    const UInt free_bits = universe ^ mask;
    for_each_submask(free_bits, [&](UInt added_bits) {
        f(mask | added_bits);
    });
}

}  // namespace algo
}  // namespace m1une

#endif  // M1UNE_ALGO_ENUMERATION_SUBMASK_HPP

#line 1 "algo/enumeration/submask.hpp"



#include <cassert>
#include <concepts>
#include <limits>
#include <type_traits>

namespace m1une {
namespace algo {

namespace internal {

template <std::unsigned_integral UInt>
requires(!std::same_as<std::remove_cv_t<UInt>, bool>)
UInt submask_low_bits(int bit_count) {
    constexpr int digits = std::numeric_limits<UInt>::digits;
    assert(0 <= bit_count && bit_count <= digits);
    if (bit_count == digits) return ~UInt(0);
    return (UInt(1) << bit_count) - UInt(1);
}

}  // namespace internal

template <std::unsigned_integral UInt, class F>
requires(!std::same_as<std::remove_cv_t<UInt>, bool>)
void for_each_submask(UInt mask, F f) {
    UInt submask = mask;
    while (true) {
        f(submask);
        if (submask == 0) break;
        submask = (submask - 1) & mask;
    }
}

template <std::unsigned_integral UInt, class F>
requires(!std::same_as<std::remove_cv_t<UInt>, bool>)
void for_each_nonzero_submask(UInt mask, F f) {
    for (UInt submask = mask; submask != 0; submask = (submask - 1) & mask) {
        f(submask);
    }
}

template <std::unsigned_integral UInt, class F>
requires(!std::same_as<std::remove_cv_t<UInt>, bool>)
void for_each_supermask(UInt mask, int bit_count, F f) {
    const UInt universe = internal::submask_low_bits<UInt>(bit_count);
    assert((mask & ~universe) == 0);
    const UInt free_bits = universe ^ mask;
    for_each_submask(free_bits, [&](UInt added_bits) {
        f(mask | added_bits);
    });
}

}  // namespace algo
}  // namespace m1une

Back to top page