Пусть есть некоторые значения о которых известно только то, что они <= 10^6
.
Принимая во внимание этот факт - берём массив c int ами и храним. Но как быть если не хочется использовать лишние байты (пусть sizeof(int) == 4
) типа int
- тоесть в данном случае можно обойтись и 3 байтами, так как 10^6 < 2^24
. Как такое реализовать ??
-
В это мире люди не производят процессоров с 20 битными регистрами. Хотя можно попробовать упаковку 3 значений битовыми сдвигами и маской в один 64 битный регистр. Но там все равно останется 4 бита лишних, которые будут тормозить всю систему.– igumnov10 июл 2015 в 19:55
-
Значит заведите char* массив, по 3 байта берите и приводите их к int– Алексей Саровский10 июл 2015 в 19:58
-
Хотя на самом деле есть еще один изощренный вариант в котором все выровненно. Можно хранить первые старшие 16 бит первых четырех чисел в 64 битном регистре и оставшиеся в 4 бита четырех чисел в 16 битном. Но это все означает сильную головную боль с упаковкой и распаковкой.– igumnov10 июл 2015 в 20:10
-
@АлексейСаровский а можно подробней про "берите по 3 байта" ??– ampawd10 июл 2015 в 20:17
-
@arammis stackoverflow.com/a/2682737/4569791– zenden2k10 июл 2015 в 20:20
2 ответа
Хранение N
24 битовых целых можно организовать в банальном массиве unsigned char data[N * 3]
(подразумевая 8-битный unsigned char
).
Чтение числа с индексом i
из массива делается просто как
unsigned value = 0;
memcpy(&value, &data[i * 3], 3);
а запись как
memcpy(&data[i * 3], &value, 3);
Для того, чтобы поддержать знаковые числа в формате 2's-compliment, если это нужно, придется сделать еще расширение знака при чтении и все. (Т.е. размножить старший бит 3-го по значимости байта на весь старший по значимости байт.)
Вышеприведенные копирования специфичны для little-endian платформ, и для big-endian платформ будут несколько иными.
-
будет работать только для little-endian машин (напр. с проц. Intel), но не для big-endian (напр. SPARC), так что для portability лучше использовать что-то вроде value = (((int)data[i*3+2]) << 16) | (((int)data[i*3 + 1]) << 8) | ((int)data[i*3])– ivan.ukr14 июл 2015 в 5:14
Ну, например, вы храните по три байта на индекс и преобразуете индексы сами.
struct Int24Container
{
int8_t* payload;
size_t size;
};
int24c_init(Int24Container* cont, size_t size)
{
cont->payload = (int8_t*)malloc(3 * size);
cont->size = size;
}
int24c_destroy(Int24Container* cont)
{
delete cont->payload;
}
int32_t in24c_get(Int24Container* cont, size_t idx)
{
return cont -> payload[idx] |
(cont -> payload[idx + 1] << 8) |
(cont -> payload[idx + 2] << 16);
}
void in24c_set(Int24Container* cont, size_t idx, int32_t x)
{
cont -> payload[idx] = x & 0xff;
cont -> payload[idx + 1] = (x >> 8) & 0xff;
cont -> payload[idx + 2] = (x >> 16) & 0xff;
}
Если хотите в стиле C++, можно сделать так, как делает vector<bool>
.
class Int24Container
{
vector<int8_t> payload;
public:
Int24Container(size_t size) : payload(size * 3) { }
class reference
{
Int24Container& cont;
size_t idx;
public:
reference(Int24Container& cont, size_t idx) : cont(cont), idx(idx) {}
reference(const reference& ref) : cont(ref.cont), idx(ref.idx) {}
reference& operator = (int x)
{
cont.payload[idx] = x & 0xff;
cont.payload[idx + 1] = (x >> 8) & 0xff;
cont.payload[idx + 2] = (x >> 16) & 0xff;
return *this;
}
reference& operator = (const reference& ref)
{
cont.payload[idx] = ref.cont.payload[idx];
cont.payload[idx + 1] = ref.cont.payload[idx + 1];
cont.payload[idx + 2] = ref.cont.payload[idx + 2];
return *this;
}
operator int() const
{
return cont.payload[idx] |
(cont.payload[idx + 1] << 8) |
(cont.payload[idx + 2] << 16);
}
};
reference operator[] (int index)
{
return reference(*this, index * 3);
}
};
Вместо побайтового копирования стоит попробовать использовать memcpy
, это может оказаться быстрее.