Bitwise AND Monoid
(monoid/and.hpp)

• View this file on GitHub
• Last update: 2026-07-21 20:17:47+09:00
• Include: #include "monoid/and.hpp"

Overview

A monoid representing the bitwise AND operation.

Template Parameters

• T: The underlying integer data type.

Properties

• Operation: Bitwise AND ($a \ \& \ b$)
• Identity Element: ~T(0) (All bits set to 1)

Interface and Complexity

This is a stateless algebra tag. Generic data structures use its public value_type, id(), and op(a, b) members. If the type also provides helpers such as make(...) or inv(x), they are described above or in the documented properties.

Each static operation runs in the cost of the underlying operation shown in the properties. Scalar monoids are $O(1)$; monoids whose value_type stores several items, permutations, or matrices scale with that stored size.

Verified with

• verify/monoid/commutative_flags.test.cpp

Code

#ifndef M1UNE_MONOID_AND_HPP
#define M1UNE_MONOID_AND_HPP 1

namespace m1une {
namespace monoid {

// Monoid for bitwise AND (Range AND).
// ~T(0) sets all bits to 1, acting as the identity for bitwise AND.
template <typename T>
struct And {
    using value_type = T;
    static constexpr bool commutative = true;

    // The identity element for bitwise AND is all bits set to 1.
    static constexpr T id() { return ~T(0); }

    // Returns the bitwise AND of a and b.
    static constexpr T op(const T& a, const T& b) { return a & b; }
};

}  // namespace monoid
}  // namespace m1une

#endif  // M1UNE_MONOID_AND_HPP

#line 1 "monoid/and.hpp"



namespace m1une {
namespace monoid {

// Monoid for bitwise AND (Range AND).
// ~T(0) sets all bits to 1, acting as the identity for bitwise AND.
template <typename T>
struct And {
    using value_type = T;
    static constexpr bool commutative = true;

    // The identity element for bitwise AND is all bits set to 1.
    static constexpr T id() { return ~T(0); }

    // Returns the bitwise AND of a and b.
    static constexpr T op(const T& a, const T& b) { return a & b; }
};

}  // namespace monoid
}  // namespace m1une

Back to top page