Как получить наименьший целочисленный тип, способный вместить число n?

Question

[Szewczyk]

Привет, мне нужен массив чисел, которые будут точно не больше переменой n, в моем случае это размер определенного вектора. Как мне получить наименьший такой тип? Наример вектор имеет размер 10, но хранится он в uint64_t, что достаточно дорого выходит.

Нашел такое решение, но оно не работает в моем случае (наверное потому что мое число не constexpr)

template<unsigned long long Max>
struct RequiredBits
{
    enum {
        value =
        Max <= 0xff ? 8 :
        Max <= 0xffff ? 16 :
        Max <= 0xffffffff ? 32 :
        64
    };
};

template<int bits> struct SelectInteger_;
template<> struct SelectInteger_ <8> { typedef uint8_t type; };
template<> struct SelectInteger_<16> { typedef uint16_t type; };
template<> struct SelectInteger_<32> { typedef uint32_t type; };
template<> struct SelectInteger_<64> { typedef uint64_t type; };

template<unsigned long long Max>
struct SelectInteger : SelectInteger_<RequiredBits<Max>::value> {};

Comments

[Dmitrii]

Можете попробовать реализовать ваш массив как массив char, а интерпретировать элементы исходя из дополнительной переменной, которая будет указывать сколько байт занимает каждый элемент. Тогда в случае, если N < 255 (если тип беззнаковый) кажддый элмент будет занимать 1 байт, и дальше по степеням двойки.

[Szewczyk]

Dmitrii, только в таком случае я сильно потеряю на скорости работы с большими массивами, а для маленьких тип данных не имеет такого значения.

[Xiran]

N во время компиляции известна?

[Xiran]

Можно попробовать еще с AVX

[Szewczyk]

Xiran, нет, не известна.

[Xiran]

Как оно получается?

[Xiran]

Можно через старый добрый union

[Xiran]

Или разбить память на зоны , в которых переменные одного размера

[Xiran]

Для чего вам это в принципе?

[Xiran]

Dmitrii, Лучше тогда использовать векторный тип или машинное слово вместо char

[pfg21]

м-м-м т.е. надо найти что "единицы" есть только в младших битах из 64 бит??
предложу побитовое И с маской, имеющей нужное количество нулевых бит в младших разрядах и проверка "нулевости" результата.
объясняю на пальцах, к примеру проверка что из 8 байт имеются значения только в младших 2 байтах
00 00 00 00 00 00 AB CD
&
FF FF FF FF FF FF 00 00
=
00 00 00 00 00 00 00 00
если б в третьем байте и выше были бы единички результат был не нулевым.
пардон умных с++ не знаю.
за счет элементарных операций работать будет мгновенно.

[mayton2019]

Почему на 1 байте остановился? Десять влезает в 4 бита. Порежь каждый байт пополам и будет
тебе настоящий перфекционизм хранения.

А потом еще VLQ, кодирование Левенштейна, архивация и нет предела совершенству короче.

[Szewczyk]

Xiran, в данном случае, как я и сказал, N - размер вектора, который получает моя функция. Я уже понял, что лучше зарезервировать нужное количество памяти, но как мне кастануть указатель на нужный мне тип uintX_t? можно чутка подробнее про union, потому что я не нашел подобных применений ему пока-что.

[Dmitrii]

Szewczyk, вы всегда либо теряете во времени работы, либо в памяти.

С юнионами вы не добьётесь эффективности по памяти, размер будет определяться наибольшим типом, хранящимся в Юнион. Также в плюсах давно рекомендуют std::variadic вместо union (который, впрочем, не имеет преимуществ по памяти). И в связи со всем этим встаёт вопрос а зачем это все, если выгоды по памяти нет?

Answer 1

[Vindicar]

Я бы тоже посоветовал выделить массив байт, и кастовать указатель к нужному типу, скажем, через union.
Если alignment массива будет подходящий (например, сразу по 8 байтам), то никакого замедления быть не должно в итоге.

Comments

[Szewczyk]

Можно уточнить, как мне кастовать мой void* указатель на поле байтов? Выделил поле, посчитал в другой переменной сколько байт надо. С union не знаком, почитав по интернету пока не смог понять о чем именно вы говорили. Для стандартного кастинга через reinterpret_cast мне тоже нужно знать тип, что возвращает по-сути к изначальной задаче с данным количеством байт и определением типа.

[Vindicar]

Szewczyk, ну если коротко, union подразумевает несколько полей разных типов, только в отличие от структуры они расположены "поверх" друг другоа в одной памяти. Чем-то похоже на reinterprest cast, только для фиксированного набора типов.

Минимальный пример

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

typedef union {
    struct { //один вариант - безымянная структура из двух полей
        uint16_t LowWord;
        uint16_t HighWord;
    };
    uint32_t DoubleWord; //второй вариант 
} DOUBLEWORD;

int main()
{
    DOUBLEWORD w;
    cout << sizeof(w) << " bytes" << endl; //4 bytes - по размеру наибольшего члена union
    //заполняем память, используя первый вариант.
    w.LowWord = 0x0001;
    w.HighWord = 0x0002;
    //читаем, используя второй вариант
    cout << hex << setw(8) << setfill('0') << w.DoubleWord << endl; //00020001
}

В твоём случае будет что-то типа...

typedef struct {
    size_t item_count;
    enum { UINT8, UINT16, UINT32, UINT64 } item_type;
    union {
        void* voidPtr;
        uint8_t* bytePtr;
        uint16_t* wordPtr;
        uint32_t* ulongPtr;
        uint64_t* quadPtr;
    } ptr;
} MultiTypeArray;

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

MultiTypeArray arr;
arr.item_count = 16;
arr.item_type = MultiTypeArray::UINT32;
arr.ptr.voidPtr = malloc(sizeof(uint32_t) * arr.item_count);
for (size_t i = 0; i < arr.item_count; i++)
    arr.ptr.ulongPtr[i] = i;

Можно прикрутить метод-хелпер типа uint8_t& as_byte(size_t index);, но это не сделает работу сильно удобнее.

[Szewczyk]

Vindicar, Только в таком случае ведь обращение идет к заранее определенному полю(здесь ulongPtr), а в моем случае только во время выполнения программы я узнаю нужен ли мне bytePtr, wordPtr или же ulongPtr исходя из количества байт, в которое вмещается моя переменная n.

[Vindicar]

Szewczyk, я про это писал в своём ответе.

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

Т.е. у тебя при каждом(!) обращении к массиву будет switch (item_type), а в ветках - обращения к нужному полю.

[Xiran]

Можно еще округлить n до ближайшей степени двойки