bit.hpp

浏览该文件的文档.

#ifndef MSTL_CORE_MEMORY_BIT_HPP__
#define MSTL_CORE_MEMORY_BIT_HPP__

 
#include "MSTL/core/typeinfo/types.hpp"
MSTL_BEGIN_NAMESPACE__

MSTL_BEGIN_CONSTANTS__

MSTL_INLINE17 constexpr byte_t POPCOUNT_TABLE[256] = {
    0,1,1,2,1,2,2,3,1,2,2,3,2,3,3,4,1,2,2,3,2,3,3,4,2,3,3,4,3,4,4,5,
    1,2,2,3,2,3,3,4,2,3,3,4,3,4,4,5,2,3,3,4,3,4,4,5,3,4,4,5,4,5,5,6,
    1,2,2,3,2,3,3,4,2,3,3,4,3,4,4,5,2,3,3,4,3,4,4,5,3,4,4,5,4,5,5,6,
    2,3,3,4,3,4,4,5,3,4,4,5,4,5,5,6,3,4,4,5,4,5,5,6,4,5,5,6,5,6,6,7,
    1,2,2,3,2,3,3,4,2,3,3,4,3,4,4,5,2,3,3,4,3,4,4,5,3,4,4,5,4,5,5,6,
    2,3,3,4,3,4,4,5,3,4,4,5,4,5,5,6,3,4,4,5,4,5,5,6,4,5,5,6,5,6,6,7,
    2,3,3,4,3,4,4,5,3,4,4,5,4,5,5,6,3,4,4,5,4,5,5,6,4,5,5,6,5,6,6,7,
    3,4,4,5,4,5,5,6,4,5,5,6,5,6,6,7,4,5,5,6,5,6,6,7,5,6,6,7,6,7,7,8
};
 
MSTL_END_CONSTANTS__

 
#ifdef MSTL_DATA_BUS_WIDTH_64__

constexpr int popcount64(const uint64_t x) noexcept {
    return
        _CONSTANTS POPCOUNT_TABLE[static_cast<byte_t>(x & 0xFFULL)] +
        _CONSTANTS POPCOUNT_TABLE[static_cast<byte_t>((x >> 8) & 0xFFULL)] +
        _CONSTANTS POPCOUNT_TABLE[static_cast<byte_t>((x >> 16) & 0xFFULL)] +
        _CONSTANTS POPCOUNT_TABLE[static_cast<byte_t>((x >> 24) & 0xFFULL)] +
        _CONSTANTS POPCOUNT_TABLE[static_cast<byte_t>((x >> 32) & 0xFFULL)] +
        _CONSTANTS POPCOUNT_TABLE[static_cast<byte_t>((x >> 40) & 0xFFULL)] +
        _CONSTANTS POPCOUNT_TABLE[static_cast<byte_t>((x >> 48) & 0xFFULL)] +
        _CONSTANTS POPCOUNT_TABLE[static_cast<byte_t>((x >> 56) & 0xFFULL)];
}

MSTL_CONSTEXPR14 int clz64(uint64_t x) noexcept {
    if (x == 0) return 64;
    int n = 0;
    if (x <= 0x00000000FFFFFFFFULL) { n += 32; x <<= 32; }
    if (x <= 0x0000FFFFFFFFFFFFULL) { n += 16; x <<= 16; }
    if (x <= 0x00FFFFFFFFFFFFFFULL) { n += 8; x <<= 8; }
    if (x <= 0x0FFFFFFFFFFFFFFFULL) { n += 4; x <<= 4; }
    if (x <= 0x3FFFFFFFFFFFFFFFULL) { n += 2; x <<= 2; }
    if (x <= 0x7FFFFFFFFFFFFFFFULL) { n += 1; }
    return n;
}
 
#endif

constexpr int popcount32(const uint32_t x) noexcept {
    return
        _CONSTANTS POPCOUNT_TABLE[static_cast<byte_t>(x & 0xFFU)] +
        _CONSTANTS POPCOUNT_TABLE[static_cast<byte_t>((x >> 8) & 0xFFU)] +
        _CONSTANTS POPCOUNT_TABLE[static_cast<byte_t>((x >> 16) & 0xFFU)] +
        _CONSTANTS POPCOUNT_TABLE[static_cast<byte_t>((x >> 24) & 0xFFU)];
}

MSTL_CONSTEXPR14 int clz32(uint32_t x) noexcept {
    if (x == 0) return 32;
    int n = 0;
    if (x <= 0x0000FFFFU) { n += 16; x <<= 16; }
    if (x <= 0x00FFFFFFU) { n += 8; x <<= 8; }
    if (x <= 0x0FFFFFFFU) { n += 4; x <<= 4; }
    if (x <= 0x3FFFFFFFU) { n += 2; x <<= 2; }
    if (x <= 0x7FFFFFFFU) { n += 1; }
    return n;
}

constexpr int popcount(const uintptr_t x) noexcept {
#ifdef MSTL_DATA_BUS_WIDTH_64__
    return popcount64(x);
#else
    return popcount32(x);
#endif
}

constexpr int countl_zero(const uintptr_t x) noexcept {
#ifdef MSTL_DATA_BUS_WIDTH_64__
    return clz64(x);
#else
    return clz32(x);
#endif
}

constexpr int countl_one(const uintptr_t x) noexcept {
    return countl_zero(~x);
}

constexpr int countr_zero(const uintptr_t x) noexcept {
    return popcount((x & (~x + 1)) - 1);
}

constexpr int countr_one(const uintptr_t x) noexcept {
    return countr_zero(~x);
}
 

constexpr int lowest_set_bit_pos(const intptr_t x) noexcept {
    return x == 0 ? -1 : countr_zero(x);
}

MSTL_CONSTEXPR14 int highest_set_bit_pos(const intptr_t x) noexcept {
    if (x == 0) return -1;
#ifdef MSTL_DATA_BUS_WIDTH_64__
    return 63 - clz64(x);
#else
    return 31 - clz32(x);
#endif
}
 

MSTL_CONSTEXPR14 bool parity32(uint32_t x) noexcept {
    x ^= x >> 16;
    x ^= x >> 8;
    x ^= x >> 4;
    x ^= x >> 2;
    x ^= x >> 1;
    return (x & 1) != 0;
}
 
#ifdef MSTL_DATA_BUS_WIDTH_64__

MSTL_CONSTEXPR14 bool parity64(uint64_t x) noexcept {
    x ^= x >> 32;
    x ^= x >> 16;
    x ^= x >> 8;
    x ^= x >> 4;
    x ^= x >> 2;
    x ^= x >> 1;
    return (x & 1) != 0;
}
 
#endif

constexpr bool parity(const uintptr_t x) noexcept {
#ifdef MSTL_DATA_BUS_WIDTH_64__
    return parity64(x);
#else
    return parity32(x);
#endif
}
 // BitCounting


constexpr int bit_width(const uintptr_t x) noexcept {
#ifdef MSTL_DATA_BUS_WIDTH_64__
    return x == 0 ? 0 : 64 - countl_zero(x);
#else
    return x == 0 ? 0 : 32 - countl_zero(x);
#endif
}

constexpr uintptr_t bit_floor(const uintptr_t x) noexcept {
    return x == 0 ? 0 : uintptr_t{1} << (bit_width(x) - 1);
}

MSTL_CONSTEXPR14 uint64_t bit_ceil(const uintptr_t x) noexcept {
    if (x <= 1) return 1;
    const uint64_t floor = bit_floor(x);
    return floor == x ? x : floor << 1;
}

constexpr bool has_single_bit(const uintptr_t x) noexcept {
    return x != 0 && (x & (x - 1)) == 0;
}

MSTL_CONSTEXPR14 uint32_t rotate_l32(const uint32_t x, const int s) noexcept {
    constexpr int bits = 32;
    int shift = s % bits;
    if (shift < 0) shift += bits;
    if (shift == 0) return x;
    return (x << shift) | (x >> (bits - shift));
}

MSTL_CONSTEXPR14 uint32_t rotate_r32(const uint32_t x, const int s) noexcept {
    constexpr int bits = 32;
    int shift = s % bits;
    if (shift < 0) shift += bits;
    if (shift == 0) return x;
    return (x >> shift) | (x << (bits - shift));
}
 
#ifdef MSTL_DATA_BUS_WIDTH_64__

MSTL_CONSTEXPR14 uint64_t rotate_l64(const uint64_t x, const int s) noexcept {
    constexpr int bits = 64;
    int shift = s % bits;
    if (shift < 0) shift += bits;
    if (shift == 0) return x;
    return (x << shift) | (x >> (bits - shift));
}

MSTL_CONSTEXPR14 uint64_t rotate_r64(const uint64_t x, const int s) noexcept {
    constexpr int bits = 64;
    int shift = s % bits;
    if (shift < 0) shift += bits;
    if (shift == 0) return x;
    return (x >> shift) | (x << (bits - shift));
}
 
#endif

MSTL_CONSTEXPR14 int rotate_l(const uintptr_t x, const int s) noexcept {
#ifdef MSTL_DATA_BUS_WIDTH_64__
    return rotate_l64(x, s);
#else
    return rotate_l32(x, s);
#endif
}

MSTL_CONSTEXPR14 int rotate_r(const uintptr_t x, const int s) noexcept {
#ifdef MSTL_DATA_BUS_WIDTH_64__
    return rotate_r64(x, s);
#else
    return rotate_r32(x, s);
#endif
}
 

constexpr uintptr_t bit_extract(const uintptr_t x, const int pos, const int len) noexcept {
    return (x >> pos) & ((uintptr_t{1} << len) - 1);
}

MSTL_CONSTEXPR14 uintptr_t bit_insert(const uintptr_t x, const uintptr_t bits, const int pos, const int len) noexcept {
    const uintptr_t mask = ((uintptr_t{1} << len) - 1) << pos;
    return (x & ~mask) | ((bits << pos) & mask);
}
 

MSTL_CONSTEXPR14 uint32_t reverse_bits32(uint32_t x) noexcept {
    x = ((x >> 1) & 0x55555555U) | ((x & 0x55555555U) << 1);
    x = ((x >> 2) & 0x33333333U) | ((x & 0x33333333U) << 2);
    x = ((x >> 4) & 0x0F0F0F0FU) | ((x & 0x0F0F0F0FU) << 4);
    x = ((x >> 8) & 0x00FF00FFU) | ((x & 0x00FF00FFU) << 8);
    x = ((x >> 16) & 0x0000FFFFU) | ((x & 0x0000FFFFU) << 16);
    return x;
}
 
#ifdef MSTL_DATA_BUS_WIDTH_64__

MSTL_CONSTEXPR14 uint64_t reverse_bits64(uint64_t x) noexcept {
    x = ((x >> 1) & 0x5555555555555555ULL) | ((x & 0x5555555555555555ULL) << 1);
    x = ((x >> 2) & 0x3333333333333333ULL) | ((x & 0x3333333333333333ULL) << 2);
    x = ((x >> 4) & 0x0F0F0F0F0F0F0F0FULL) | ((x & 0x0F0F0F0F0F0F0F0FULL) << 4);
    x = ((x >> 8) & 0x00FF00FF00FF00FFULL) | ((x & 0x00FF00FF00FF00FFULL) << 8);
    x = ((x >> 16) & 0x0000FFFF0000FFFFULL) | ((x & 0x0000FFFF0000FFFFULL) << 16);
    x = (x >> 32) | (x << 32);
    return x;
}
 
#endif

constexpr uintptr_t reverse_bits(const uintptr_t x) noexcept {
#ifdef MSTL_DATA_BUS_WIDTH_64__
    return reverse_bits64(x);
#else
    return reverse_bits32(x);
#endif
}
 

constexpr uintptr_t mask_from_to(const int from, const int to) noexcept {
    return ((uintptr_t{1} << (to - from + 1)) - 1) << from;
}
 // BitManipulation
 
MSTL_END_NAMESPACE__
#endif // MSTL_CORE_MEMORY_BIT_HPP__