Как задать маску вида 0x55555555 переносимым образом?

Question

В некоторых задачах связанных с манипуляцией битами нужна маска для всех чётных битов. Каждый раз такая маска задаётся константой вида 0x55555555, что хорошо если unsigned занимает 32 бита. А если 16 или 64?

Как определить маску для всех чётных битов способом, который будет работать для любого числа бит в типе? Определение должно быть константой времени компиляции.

Answer 1

С использованием constexpr-функции:

#include <iostream>
#include <iomanip>
using namespace std;

template <typename T> 
T constexpr mask101() 
{
    T ret = 0;
    for(T mask=1;mask;mask<<=2)
    {
        ret|=mask;
    }
    return ret;
}

int main() 
{
    constexpr auto test = mask101<size_t>();
    cout << std::hex <<"0x" << test << endl;
    cout << std::hex <<"0x" << mask101<int32_t>() << endl;
    cout << std::hex <<"0x" << mask101<uint16_t>() << endl;
    cout << std::hex <<"0x" << int(mask101<int8_t>()) << endl;
    return 0;
}

Вывод:

0x5555555555555555
0x55555555
0x5555
0x55

Код на ideone

Answer 2

Воспользуемся тем, что в реальной жизни

Размер байта — 8 бит.
Размеры целочисленных типов в байтах — степени двойки.

Если это не так, можно пользоваться ответом gbg :)

template<unsigned_integral T>
consteval T mask2()
{
    T mask = 0x55;
    for(unsigned int i = 1; i < sizeof(T); i*=2)
        mask |= mask << i*8;
    return mask;
}

Все ж таки O(log N):), где N — размер типа.

Bычисляется, как и у gbg, во время компиляции — https://gcc.godbolt.org/z/78EaTqzKK

Answer 3

В Си помогает создавать константы двойная компиляция. Пример в gcc :

gcc makemask.c -o makemask && makemask > mask.h

Пишем шаблоном, используя размер типа :

# define MAKECONST( T , N ) { \
  printf ( "%s const %s = 0x" , ( # T ) , ( N ) ) ; \
  for ( int i = 0 ; i < sizeof ( T ) ; ++ i ) \
    printf ( "%x" , 0x55 ) ; \
  puts ( " ;" ) ; \
}

# include <stdio.h>

int main() {
  MAKECONST ( unsigned short int , "ushort_mask" ) ;
  MAKECONST ( unsigned int , "uint_mask" ) ;
  fflush ( stdout ) ;
}

получаем хедер : mask.h

unsigned short int const ushort_mask = 0x5555 ;
unsigned int const uint_mask = 0x55555555 ;

Answer 4

Имея значения для степеней двойки это можно посчитать без циклов :

template<unsigned long long x_index>
constexpr auto pow2{2ull * pow2<x_index - 1ull>};

template<>
constexpr auto pow2<0ull>{1ull};

template<typename x_Integer>
constexpr x_Integer odd_mask{(pow2<sizeof(x_Integer) * 8ull> - 1ull) / 3ull};

static_assert(0x55u == odd_mask<unsigned char>);
static_assert(0x5555u == odd_mask<unsigned short>);
static_assert(0x55555555u == odd_mask<unsigned int>);
static_assert(0x5555555555555555u == odd_mask<unsigned long long>);

online compiler

Answer 5

Можно просто (unsigned int)-1 / 3.

Answer 6

Маска может быть представлена в виде суммы 4⁰ + 4¹ + ... + 4^k. По формуле суммы геометрической прогрессии эта сумма равна (4^k+1 - 1) / 3.

Если в беззнаковом типе чётное число бит, его максимальное значение есть 2^2k - 1. Что равно 4^k - 1. Если это число поделить на три, получится нужная маска. Например, для unsigned вычислите UINT_MAX / 3.

Программа на C строит маски переносимым образом. Максимальные значения типов получаются как приведение -1 к беззнаковому типу. Ещё одно приведение нужно чтобы значения типов короче unsigned были так же короткими. Иначе получается тип unsigned со значением маски unsigned short или unsigned char:

#include <stdio.h>

#define MASK(type) ((type)((type)-1 / 3))

int main() {
    printf("0x%hhx\n", MASK(unsigned char     ));
    printf("0x%hx\n" , MASK(unsigned short    ));
    printf("0x%x\n"  , MASK(unsigned          ));
    printf("0x%lx\n" , MASK(unsigned long     ));
    printf("0x%llx\n", MASK(unsigned long long));
}

$ gcc -std=c11 -pedantic -Wall -Wextra -Werror mask.c && ./a.out 
0x55
0x5555
0x55555555
0x5555555555555555
0x5555555555555555

То же самое на C++:

#include <iomanip>
#include <iostream>

template<typename T> constexpr T mask() { return static_cast<T>(-1) / 3; }

int main() {
    std::cout << std::hex;
    std::cout << static_cast<unsigned>(mask<unsigned char     >()) << '\n';
    std::cout <<                       mask<unsigned short    >()  << '\n';
    std::cout <<                       mask<unsigned          >()  << '\n';
    std::cout <<                       mask<unsigned long     >()  << '\n';
    std::cout <<                       mask<unsigned long long>()  << '\n';
}

$ g++ -std=c++17 -pedantic -Wall -Wextra -Werror mask.cpp && ./a.out 
55
5555
55555555
5555555555555555
5555555555555555

Но что делать если на вашем компьютере есть типы с нечётным числом бит? Например пятибайтовое целое и девять бит в байте. Придётся сделать ещё один шаг:

#define DRAFT_MASK(type) ((type)((type)-1 / 3))
#define ODD_BITS(type) ((DRAFT_MASK(type) & 1) ^ 1)
#define MASK(type) ((type)(DRAFT_MASK(type) << ODD_BITS(type) | 1))

DRAFT_MASK - маска старого образца. Если число бит нечётно, то получится

(2^2k+1 - 1) / 3 = (2·4^k - 1) / 3 = (2(4^k - 1) + 1) / 3 = 2((4^k - 1) / 3) + 1 / 3.

Левое слагаемое - удвоенная маска. Правое слагаемое округляется до нуля - деление целочисленное. Получилась маска выделяющая нечётные биты.

Конструкция ODD_BITS(type) равна единице если число бит в типе нечётное - проверяется младший бит маски. В этом случае старую маску надо сдвинуть на разряд влево и добавить младший бит. Что и делает MASK. Если число бит чётно, результат MASK не отличается от DRAFT_MASK.

Как обзаведусь соответствующим железом, обязательно потестирую.

БЛОГ НА HUSL

Как задать маску вида 0x55555555 переносимым образом?

Ответы (6 шт):