bitops.hpp

Go to the documentation of this file.

/*
 * SPDX-Licence-Identifier: MIT
 *
 * Copyright 2025 Larry Chips
 *
 * Permission is hereby granted, free of charge, to any person obtaining a copy
 * of this software and associated documentation files (the “Software”), to deal
 * in the Software without restriction, including without limitation the rights
 * to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
 * copies of the Software, and to permit persons to whom the Software is
 * furnished to do so, subject to the following conditions:
 *
 * The above copyright notice and this permission notice shall be included in
 * all copies or substantial portions of the Software.
 *
 * THE SOFTWARE IS PROVIDED “AS IS”, WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
 * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
 * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
 * AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
 * LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
 * OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE
 * SOFTWARE.
 */
#pragma once

 
#include <cstdint>
#include <type_traits>
#include <utility>
 
#include "ugmisc/features.hpp"
#include "ugmisc/sfinae_helpers.hpp"
 
 
 
 
#ifdef UGMISC_HAVE_BITOPS
# include <bit>
#endif
 
 
namespace ugmisc {
 
 
 
 
/*
 * Forward declarations.
 *
 * We declare these two ways:
 *
 * 1. With concepts if concepts are supported OR if we are building the docs.
 * 2. With enable_if based return types otherwise.
 *
 * The declaration used is defined as a macro for use in the definition later.
 * Just using the option without concepts everywhere would work, but users of
 * the library may get more helpful error messages where the concepts have been
 * used.
 */
 
#ifdef UGMISC_USE_CONCEPT_DECLS
template<BitwiseUint T> constexpr T clz(T) noexcept;

template<BitwiseUint T> constexpr T cl1(T) noexcept;

template<BitwiseUint T> constexpr T crz(T) noexcept;

template<BitwiseUint T> constexpr T cr1(T) noexcept;

template<BitwiseUint T> constexpr T bitwidth(T) noexcept;
 
# ifndef UGMISC_DOCS
#  define UGMISC__clz(x) template<BitwiseUint T> constexpr T clz(T x) noexcept
#  define UGMISC__bitwidth(x) template<BitwiseUint T> constexpr T bitwidth(T x) noexcept
#  define UGMISC__cr1(x) template<BitwiseUint T> constexpr T cr1(T x) noexcept
#  define UGMISC__crz(x) template<BitwiseUint T> constexpr T crz(T x) noexcept
#  define UGMISC__cl1(x) template<BitwiseUint T> constexpr T cl1(T x) noexcept
# endif
 
#else
 
template<class T> constexpr bitwise_uint_only<T> clz(T) noexcept;
template<class T> constexpr bitwise_uint_only<T> cl1(T) noexcept;
template<class T> constexpr bitwise_uint_only<T> crz(T) noexcept;
template<class T> constexpr bitwise_uint_only<T> cr1(T) noexcept;
template<class T> constexpr bitwise_uint_only<T> bitwidth(T) noexcept;
 
# ifndef UGMISC_DOCS
#  define UGMISC__clz(x) template<class T> constexpr bitwise_uint_only<T> clz(T x) noexcept
#  define UGMISC__cl1(x) template<class T> constexpr bitwise_uint_only<T> cl1(T x) noexcept
#  define UGMISC__crz(x) template<class T> constexpr bitwise_uint_only<T> crz(T x) noexcept
#  define UGMISC__cr1(x) template<class T> constexpr bitwise_uint_only<T> cr1(T x) noexcept
#  define UGMISC__bitwidth(x) template<class T> constexpr bitwise_uint_only<T> bitwidth(T x) noexcept
# endif
 
#endif
 
 
 
 
#ifdef UGMISC_HAVE_BITOPS
 
/*
 * We have all the functions in the standard library, so ours are simple wrappers.
 *
 * The UGMISC__* macros were defined before because we use different
 * declarations for C++20 and C++17, so we can use concepts.
 */
 
#ifndef UGMISC_DOCS
    UGMISC__clz(x) { return std::countl_zero(x); }
    UGMISC__cl1(x) { return std::countl_one(x); }
    UGMISC__crz(x) { return std::countr_zero(x); }
    UGMISC__cr1(x) { return std::countr_one(x); }
    UGMISC__bitwidth(x) { return std::bit_width(x); }
#endif
 
 
#else
 
/*
 * We don't have std::countl_zero, std::countr_one etc.
 *
 * TODO: Detect or guess compiler intrinsics and use those.
 */
 
 
 

namespace bitops_ {
 
 
enum BitFunc { CLZ, CR1, CL1, CRZ };
 
 
 
 
/*
 * In the absence of std bitops functions, this generic function partitions the
 * word into big chunks until it finds one with all ones or all zeros, one the
 * left or right as required.
 */
template<BitFunc F, class T, T Bits = std::numeric_limits<T>::digits, T Shift = 0 >
static constexpr bitwise_uint_only<T> cxx(T v) noexcept {
    constexpr T max_bits = std::numeric_limits<T>::digits;
    constexpr T all_ones = ~((T)0);
    constexpr T mask_rightshifted = (all_ones >> (max_bits - Bits));
 
    static_assert( Bits >= 1 );
    static_assert( Bits + Shift <= max_bits );
 
    constexpr bool from_left   = F == CLZ || F == CL1;
    constexpr bool count_ones  = F == CL1 || F == CR1;
    constexpr bool count_zeros = ! count_ones;
    constexpr    T mask        = mask_rightshifted << Shift;
 
    bool all_set = (mask & v) == mask;
    bool all_clear = (mask & v) == 0;
    bool all_bits_of_counted_state = (count_ones && all_set) || (count_zeros && all_clear);
    bool all_bits_of_uncounted_state = (count_ones && all_clear) || (count_ones && all_set);
    bool trivial_result = all_bits_of_counted_state || all_bits_of_uncounted_state;
 
    /*
     * First we want to know if all the bits were set or all clear, so we can
     * trivially return a result.  If that fails we delegate to two functions
     * which examine a smaller part of the word each.  Each function is an
     * instance of this function template.
     *
     * These functions cannot be instantiated if either of them will have 0
     * Bits.  So we must keep the delegating part of our function shielded by a
     * constexpr if condition.
     */
 
    if constexpr ( Bits == 1 ) {
        return all_bits_of_counted_state ? 1 : 0;
    } else {
        if ( trivial_result ) {
            return all_bits_of_counted_state ? Bits : 0;
        }
 
        constexpr T left_partition_bits = Bits/2;
        constexpr T right_partition_bits = Bits - left_partition_bits;
        constexpr T left_partition_shift = Shift + right_partition_bits;
        constexpr T right_partition_shift = Shift;
 
        constexpr T first_partition_bits
            = from_left ? left_partition_bits : right_partition_bits;
        constexpr T second_partition_bits
            = from_left ? right_partition_bits : left_partition_bits;
 
        constexpr T first_partition_shift
            = from_left ? left_partition_shift : right_partition_shift;
        constexpr T second_partition_shift
            = from_left ? right_partition_shift : left_partition_shift;
 
        T first_result = cxx<F, T, first_partition_bits, first_partition_shift>(v);
 
        if ( first_result < first_partition_bits ) {
            return first_result;
        } else {
            T second_result = cxx<F, T, second_partition_bits, second_partition_shift>(v);
            return first_result + second_result;
        }
    }
}
 
} /* bitops_ (::ugmisc::bitops_) */
 
 
 
 
#ifndef UGMISC_DOCS
    UGMISC__clz(x) { return bitops_::cxx<bitops_::CLZ, T>(x); }
    UGMISC__cl1(x) { return bitops_::cxx<bitops_::CL1, T>(x); }
    UGMISC__crz(x) { return bitops_::cxx<bitops_::CRZ, T>(x); }
    UGMISC__cr1(x) { return bitops_::cxx<bitops_::CR1, T>(x); }
    UGMISC__bitwidth(x) { return std::numeric_limits<T>::digits - clz(x); }
#endif
 
 
 
 
 
#endif /* No C++20 library bit funcs. */
 
 
 
 
} /* ::ugmisc */