bit-math.hpp

Go to the documentation of this file.

/*
 * Copyright (C) 2023  Christopher J. Howard
 *
 * This file is part of Antkeeper source code.
 *
 * Antkeeper source code is free software: you can redistribute it and/or modify
 * it under the terms of the GNU General Public License as published by
 * the Free Software Foundation, either version 3 of the License, or
 * (at your option) any later version.
 *
 * Antkeeper source code is distributed in the hope that it will be useful,
 * but WITHOUT ANY WARRANTY; without even the implied warranty of
 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
 * GNU General Public License for more details.
 *
 * You should have received a copy of the GNU General Public License
 * along with Antkeeper source code.  If not, see <http://www.gnu.org/licenses/>.
 */
 
#ifndef ANTKEEPER_BIT_MATH_HPP
#define ANTKEEPER_BIT_MATH_HPP
 
#include <stdint.h>
 
namespace bit {
 
template <class T>
constexpr T compress(T x) noexcept;
 
template <class T>
constexpr int count(T x) noexcept;
 
template <class T>
constexpr T crossover(T a, T b, int i) noexcept;
 
template <class T>
constexpr T crossover_n(T a, T b, T mask) noexcept;
 
template <class T>
constexpr T deposit(T x, T mask) noexcept;
 
template <class T>
constexpr T desegregate(T x) noexcept;
 
template <class T>
constexpr int difference(T x, T y) noexcept;
 
template <class T>
constexpr T expand(T x) noexcept;
 
template <class T>
constexpr T extract(T x, T mask) noexcept;
 
template <class T>
constexpr T flip(T x, int i) noexcept;
 
template <class T, class U = T>
constexpr U interleave(T a, T b) noexcept;
 
template <class T>
constexpr T merge(T a, T b, T mask) noexcept;
 
template <class T>
constexpr T parity(T x) noexcept;
 
template <class T>
constexpr T segregate(T x) noexcept;
 
template <class T>
constexpr T swap_adjacent(T x) noexcept;
 
std::uint16_t swap16(std::uint16_t x) noexcept;
 
std::int16_t swap16(std::int16_t x) noexcept;
 
std::uint32_t swap32(std::uint32_t x) noexcept;
 
std::int32_t swap32(std::int32_t x) noexcept;
 
std::uint64_t swap64(std::uint64_t x) noexcept;
 
std::int64_t swap64(std::int64_t x) noexcept;
 
template <class T>
constexpr T compress(T x) noexcept
{
    x &= T(0x5555555555555555);
    
    x = (x ^ (x >> 1)) & T(0x3333333333333333);
    x = (x ^ (x >> 2)) & T(0x0f0f0f0f0f0f0f0f);
    
    if constexpr(sizeof(T) >= 2)
        x = (x ^ (x >>  4)) & T(0x00ff00ff00ff00ff);
    if constexpr(sizeof(T) >= 4)
        x = (x ^ (x >>  8)) & T(0x0000ffff0000ffff);
    if constexpr(sizeof(T) >= 8)
        x = (x ^ (x >> 16)) & T(0x00000000ffffffff);
    
    return x;
}
 
template <class T>
constexpr int count(T x) noexcept
{
    int n = 0;
    for (; x; ++n)
        x &= x - 1;
    return n;
}
 
template <class T>
inline constexpr T crossover(T a, T b, int i) noexcept
{
    T mask = (T(1) << i) - 1;
    return merge(b, a, mask);
}
 
template <class T>
constexpr T crossover_n(T a, T b, T mask) noexcept
{
    T merge = ~T(0) * parity(mask);
    
    while (mask)
    {
        merge ^= (mask ^ (mask - 1)) >> 1;
        mask &= mask - 1;
    }
    
    return merge(a, b, merge);
}
 
template <class T>
inline constexpr T desegregate(T x) noexcept
{
    return interleave<T>(x, x >> (sizeof(T) << 2));
}
 
template <class T>
constexpr T expand(T x) noexcept
{
    x &= (1 << (sizeof(T) << 2)) - 1;
    
    if constexpr(sizeof(T) >= 8)
        x = (x ^ (x << 16)) & T(0x0000ffff0000ffff);
    if constexpr(sizeof(T) >= 4)
        x = (x ^ (x <<  8)) & T(0x00ff00ff00ff00ff);
    if constexpr(sizeof(T) >= 2)
        x = (x ^ (x <<  4)) & T(0x0f0f0f0f0f0f0f0f);
    
    x = (x ^ (x << 2)) & T(0x3333333333333333);
    x = (x ^ (x << 1)) & T(0x5555555555555555);
    
    return x;
}
 
template <class T>
constexpr T deposit(T x, T mask) noexcept
{
    T result = 0;
    
    for (T i = 1; mask; i <<= 1)
    {
        if (x & i)
            result |= mask & -mask;
        mask &= mask - 1;
    }
    
    return result;
}
 
template <class T>
inline constexpr int difference(T x, T y) noexcept
{
    return count(x ^ y);
}
 
template <class T>
constexpr T extract(T x, T mask) noexcept
{
    T result = 0;
    
    for (T i = 1; mask; i <<= 1)
    {
        if (x & mask & -mask)
            result |= i;
        mask &= mask - 1;
    }
    
    return result;
}
 
template <class T>
inline constexpr T flip(T x, int i) noexcept
{
    return x ^ (T(1) << i);
}
 
template <class T, class U>
inline constexpr U interleave(T a, T b) noexcept
{
    return expand<U>(a) | (expand<U>(b) << 1);
}
 
template <class T>
inline constexpr T merge(T a, T b, T mask) noexcept
{
    return a ^ ((a ^ b) & mask);
}
 
template <class T>
constexpr T parity(T x) noexcept
{
    if constexpr(sizeof(T) >= 8)
        x ^= x >> 32;
    if constexpr(sizeof(T) >= 4)
        x ^= x >> 16;
    if constexpr(sizeof(T) >= 2)
        x ^= x >> 8;
    
    x ^= x >> 4;
    
    return (0x6996 >> (x & 0xf)) & 1;
}
 
template <class T>
constexpr T segregate(T x) noexcept
{
    T odd = compress(x);
    T even = compress(x >> 1);
    
    return odd | (even << (sizeof(T) << 2));
}
 
template <class T>
constexpr T swap_adjacent(T x) noexcept
{
    return ((x & T(0xaaaaaaaaaaaaaaaa)) >> 1) | ((x & T(0x5555555555555555)) << 1);
}
 
std::uint16_t swap16(std::uint16_t x) noexcept
{
    return (x << 8) | (x >> 8);
}
 
std::int16_t swap16(std::int16_t x) noexcept
{
    return (x << 8) | ((x >> 8) & 0xFF);
}
 
std::uint32_t swap32(std::uint32_t x) noexcept
{
    x = ((x << 8) & 0xFF00FF00) | ((x >> 8) & 0xFF00FF);
    return (x << 16) | (x >> 16);
}
 
std::int32_t swap32(std::int32_t x) noexcept
{
    x = ((x << 8) & 0xFF00FF00) | ((x >> 8) & 0xFF00FF); 
    return (x << 16) | ((x >> 16) & 0xFFFF);
}
 
std::uint64_t swap64(std::uint64_t x) noexcept
{
    x = ((x << 8) & 0xFF00FF00FF00FF00) | ((x >> 8) & 0x00FF00FF00FF00FF);
    x = ((x << 16) & 0xFFFF0000FFFF0000) | ((x >> 16) & 0x0000FFFF0000FFFF);
    return (x << 32) | (x >> 32);
}
 
std::int64_t swap64(std::int64_t x) noexcept
{
    x = ((x << 8) & 0xFF00FF00FF00FF00) | ((x >> 8) & 0x00FF00FF00FF00FF);
    x = ((x << 16) & 0xFFFF0000FFFF0000) | ((x >> 16) & 0x0000FFFF0000FFFF);
    return (x << 32) | ((x >> 32) & 0xFFFFFFFF);
}
 
} // namespace bit
 
#endif // ANTKEEPER_BIT_MATH_HPP