В C ++, почему bool требует один байт для хранения true или false, где для этого достаточно всего одного бита, например 0 для false и 1 для true? (Почему Java также требует один байт?)
Во-вторых, насколько безопаснее использовать следующее?
struct Bool {
bool trueOrFalse : 1;
};
В-третьих, даже если это безопасно, поможет ли вышеуказанная полевая техника? Поскольку я слышал, что мы экономим место там, но все же код, сгенерированный компилятором, для доступа к ним больше и медленнее, чем код, сгенерированный для доступа к примитивам.
Почему для bool требуется один байт для хранения значений true или false, когда достаточно одного бита
Потому что каждый объект в C ++ должен быть индивидуально адресуемым* (то есть вы должны иметь указатель на него). Вы не можете адресовать отдельный бит (по крайней мере, на обычном оборудовании).
Насколько безопаснее использовать следующее?
Это «безопасно», но это не достигает многого.
действительно ли вышеуказанная полевая техника действительно поможет?
Нет, по тем же причинам, что и выше;)
но все же код, сгенерированный компилятором для доступа к ним, больше и медленнее, чем код, сгенерированный для доступа к примитивам.
Да, это правда. На большинстве платформ это требует доступа к содержащемуся байту (или int
или что-то еще), а затем выполняет операции сдвига битов и маски битов, чтобы получить доступ к соответствующему биту.
Если вы действительно беспокоитесь об использовании памяти, вы можете использовать std::bitset
в C ++ или BitSet
в Java, которые упаковывают биты.
* За некоторыми исключениями.
Использование одного бита намного медленнее и намного сложнее для распределения. В C / C ++ нет способа получить адрес в один бит, поэтому вы не сможете сделать &trueOrFalse
как немного
В Java есть BitSet и EnumSet, которые используют растровые изображения. Если у вас очень небольшое количество, это может не иметь большого значения. например объекты должны быть выровнены по крайней мере на один байт, а в HotSpot выровнены на 8 байт (в C ++ new
Объект может быть выровнен от 8 до 16 байт) Это означает, что сохранение нескольких битов может не сэкономить места.
По крайней мере, в Java биты не быстрее, если они не помещаются в кэш лучше.
public static void main(String... ignored) {
BitSet bits = new BitSet(4000);
byte[] bytes = new byte[4000];
short[] shorts = new short[4000];
int[] ints = new int[4000];
for (int i = 0; i < 100; i++) {
long bitTime = timeFlip(bits) + timeFlip(bits);
long bytesTime = timeFlip(bytes) + timeFlip(bytes);
long shortsTime = timeFlip(shorts) + timeFlip(shorts);
long intsTime = timeFlip(ints) + timeFlip(ints);
System.out.printf("Flip time bits %.1f ns, bytes %.1f, shorts %.1f, ints %.1f%n",
bitTime / 2.0 / bits.size(), bytesTime / 2.0 / bytes.length,
shortsTime / 2.0 / shorts.length, intsTime / 2.0 / ints.length);
}
}
private static long timeFlip(BitSet bits) {
long start = System.nanoTime();
for (int i = 0, len = bits.size(); i < len; i++)
bits.flip(i);
return System.nanoTime() - start;
}
private static long timeFlip(short[] shorts) {
long start = System.nanoTime();
for (int i = 0, len = shorts.length; i < len; i++)
shorts[i] ^= 1;
return System.nanoTime() - start;
}
private static long timeFlip(byte[] bytes) {
long start = System.nanoTime();
for (int i = 0, len = bytes.length; i < len; i++)
bytes[i] ^= 1;
return System.nanoTime() - start;
}
private static long timeFlip(int[] ints) {
long start = System.nanoTime();
for (int i = 0, len = ints.length; i < len; i++)
ints[i] ^= 1;
return System.nanoTime() - start;
}
печать
Flip time bits 5.0 ns, bytes 0.6, shorts 0.6, ints 0.6
для размеров 40000 и 400K
Flip time bits 6.2 ns, bytes 0.7, shorts 0.8, ints 1.1
для 4М
Flip time bits 4.1 ns, bytes 0.5, shorts 1.0, ints 2.3
и 40М
Flip time bits 6.2 ns, bytes 0.7, shorts 1.1, ints 2.4
Если вы хотите хранить только один бит информации, нет ничего более компактного, чем char
, который является наименьшим адресным блоком памяти в C / C ++. (В зависимости от реализации, bool
может иметь такой же размер, как char
но это разрешено быть больше.)
char
стандарт C гарантирует, что он будет содержать не менее 8 бит, однако он также может состоять из большего числа. Точное число доступно через CHAR_BIT
макрос, определенный в limits.h
(в С) или climits
(C ++). Сегодня чаще всего CHAR_BIT == 8
но вы не можете на это полагаться (см. Вот). Однако в POSIX-совместимых системах и на Windows.
Хотя невозможно уменьшить объем памяти для одного флага, конечно, возможно объединить несколько флагов. Кроме того, делать все битовые операции вручную, Есть несколько альтернатив:
std::bitset
boost::dynamic_bitset
Как уже отмечали другие, сохранение нескольких битов не всегда хорошая идея. Возможные недостатки:
char
).Как правило, это имеет смысл, когда вы имеете дело с огромными данными, потому что тогда вы выиграете от меньшего давления на память и кеш.
Почему бы вам просто не сохранить состояние в байте? На самом деле не проверял ниже, но это должно дать вам представление. Вы даже можете использовать short или int для 16 или 32 состояний. Я верю, что у меня есть рабочий пример JAVA. Я опубликую это, когда найду.
__int8 state = 0x0;
bool getState(int bit)
{
return (state & (1 << bit)) != 0x0;
}
void setAllOnline(bool online)
{
state = -online;
}
void reverseState(int bit)
{
state ^= (1 << bit);
}
Хорошо, вот версия JAVA. С тех пор я сохранил значение Int. Если я правильно помню, даже использование байта в любом случае использовало бы 4 байта. И это, очевидно, не будет использоваться в качестве массива.
public class State
{
private int STATE;
public State() {
STATE = 0x0;
}
public State(int previous) {
STATE = previous;
}/*
* @Usage - Used along side the #setMultiple(int, boolean);
* @Returns the value of a single bit.
*/
public static int valueOf(int bit)
{
return 1 << bit;
}/*
* @Usage - Used along side the #setMultiple(int, boolean);
* @Returns the value of an array of bits.
*/
public static int valueOf(int... bits)
{
int value = 0x0;
for (int bit : bits)
value |= (1 << bit);
return value;
}/*
* @Returns the value currently stored or the values of all 32 bits.
*/
public int getValue()
{
return STATE;
}
/*
* @Usage - Turns all bits online or offline.
* @Return - <TRUE> if all states are online. Otherwise <FALSE>.
*/
public boolean setAll(boolean online)
{
STATE = online ? -1 : 0;
return online;
}/*
* @Usage - sets multiple bits at once to a specific state.
* @Warning - DO NOT SET BITS TO THIS! Use setMultiple(State.valueOf(#), boolean);
* @Return - <TRUE> if states were set to online. Otherwise <FALSE>.
*/
public boolean setMultiple(int value, boolean online)
{
STATE |= value;
if (!online)
STATE ^= value;
return online;
}/*
* @Usage - sets a single bit to a specific state.
* @Return - <TRUE> if this bit was set to online. Otherwise <FALSE>.
*/
public boolean set(int bit, boolean online)
{
STATE |= (1 << bit);
if(!online)
STATE ^= (1 << bit);
return online;
}/*
* @return = the new current state of this bit.
* @Usage = Good for situations that are reversed.
*/
public boolean reverse(int bit)
{
return (STATE ^= (1 << bit)) == (1 << bit);
}/*
* @return = <TRUE> if this bit is online. Otherwise <FALSE>.
*/
public boolean online(int bit)
{
int value = 1 << bit;
return (STATE & value) == value;
}/*
* @return = a String contains full debug information.
*/
@Override
public String toString()
{
StringBuilder sb = new StringBuilder();
sb.append("TOTAL VALUE: ");
sb.append(STATE);
for (int i = 0; i < 0x20; i++)
{
sb.append("\nState(");
sb.append(i);
sb.append("): ");
sb.append(online(i));
sb.append(", ValueOf: ");
sb.append(State.valueOf(i));
}
return sb.toString();
}
}
Также я должен отметить, что вам действительно не следует использовать специальный класс для этого, а просто хранить переменную в классе, который, скорее всего, будет его использовать. Если вы планируете иметь 100 или даже 1000 булевых значений, рассмотрите массив байтов.
Например. Пример ниже.
boolean[] states = new boolean[4096];
может быть преобразован в ниже.
int[] states = new int[128];
Теперь вам, наверное, интересно, как вы получите доступ к индексу 4095 из массива 128. Так что же это делать, если мы упростим это. 4095 сдвигается на 5 бит вправо, что технически аналогично делению на 32. Таким образом, 4095/32 = округлено (127). Итак, мы находимся в индексе 127 массива. Затем мы выполняем 4095 & 31, что приведёт его к значению от 0 до 31. Это будет работать только со степенями два минус 1. Например. 0,1,3,7,15,31,63,127,255,511,1023 и т. Д.
Так что теперь мы можем получить доступ к биту в этой позиции. Как вы можете видеть, это очень очень компактно и превосходит 4096 логических значений в файле 🙂 Это также обеспечит намного более быстрое чтение / запись в двоичный файл. Я понятия не имею, что это за BitSet, но он выглядит как полный мусор, и поскольку byte, short, int, long уже находятся в своих битовых формах, технически вы можете использовать их как есть. Затем я создаю некоторый сложный класс для доступа к отдельным битам из памяти, что я мог понять, прочитав несколько постов.
boolean getState(int index)
{
return (states[index >> 5] & 1 << (index & 0x1F)) != 0x0;
}
Дальнейшая информация…
В основном, если вышеизложенное немного сбивает с толку, вот упрощенная версия того, что происходит.
Типы «байт«,»короткая«,»ИНТ«,»долго«Все типы данных имеют разные диапазоны.
Вы можете просмотреть эту ссылку: http://msdn.microsoft.com/en-us/library/s3f49ktz(v=vs.80).aspx
Чтобы увидеть диапазоны данных каждого.
Таким образом, байт равен 8 битам. Таким образом, int, который составляет 4 байта, будет 32 битом.
Теперь нет простого способа выполнить какое-либо N мощность. Однако, благодаря сдвигу битов, мы можем имитировать его несколько. Выполняя 1 << N это равняется 1 * 2 ^ N. Так что, если мы сделали 2 << 2 ^ N мы будем делать 2 * 2 ^ N. Таким образом, чтобы выполнить полномочия двух всегда делать «1 << N».
Теперь мы знаем, что int будет иметь 32 бита, поэтому мы можем использовать каждый бит, чтобы их можно было просто проиндексировать.
Чтобы все было просто думать о «&«оператор как способ проверить, содержит ли значение биты другого значения. Итак, допустим, у нас было значение, равное 31. Чтобы добраться до 31., мы должны добавить следующие биты от 0 до 4. , 8 и 16. Все это в сумме до 31. Теперь, когда мы выполняем 31 & 16 это вернет 16, потому что бит 4, который равен 2 ^ 4 = 16. Находится в этом значении. Теперь скажем, мы выполнили 31 & 20, который проверяет, находятся ли биты 2 и 4 в этом значении. Это вернет 20, так как оба бита 2 и 4 находятся здесь 2 ^ 2 = 4 + 2 ^ 4 = 16 = 20. Теперь допустим, что мы сделали 31 & 48. Это проверка для битов 4 и 5. Ну, у нас нет бита 5 в 31. Таким образом, он вернет только 16. Он не вернет 0. Поэтому при выполнении нескольких проверок вы должны проверить, что он физически равен этому значению. Вместо проверки, равно ли оно 0.
Ниже приведено подтверждение того, что отдельный бит равен 0 или 1,0, что ложно, а 1 — истинно.
bool getState(int bit)
{
return (state & (1 << bit)) != 0x0;
}
Ниже приведен пример проверки двух значений, если они содержат эти биты. Думайте об этом, как будто каждый бит представлен как 2 ^ БИТ, поэтому, когда мы делаем
Я быстро перейду к некоторым операторам. Мы только недавно объяснили «&»оператор слегка. Теперь для оператора» | «.
При выполнении следующих
int value = 31;
value |= 16;
value |= 16;
value |= 16;
value |= 16;
Значение по-прежнему будет 31. Это связано с тем, что бит 4 или 2 ^ 4 = 16 уже включен или установлен на 1. Таким образом, выполнение «|» возвращает это значение с включенным этим битом. Если он уже включен, никаких изменений не производится. Мы используем «| =», чтобы фактически установить переменную в это возвращаемое значение.
Вместо того, чтобы делать -> «значение = значение | 16;». Мы просто делаем «value | = 16;».
Теперь давайте посмотрим немного дальше, как&» а также «|«может быть использовано.
/*
* This contains bits 0,1,2,3,4,8,9 turned on.
*/
const int CHECK = 1 | 2 | 4 | 8 | 16 | 256 | 512;
/*
* This is some value were we add bits 0 through 9, but we skip 0 and 8.
*/
int value = 2 | 4 | 8 | 16 | 32 | 64 | 128 | 512;
Поэтому, когда мы выполняем приведенный ниже код.
int return_code = value & CHECK;
Код возврата будет 2 + 4 + 8 + 16 + 512 = 542
Итак, мы проверяли 799, но мы получили 542. Это потому, что биты o и 8 находятся в автономном режиме, мы равны 256 + 1 = 257 и 799 — 257 = 542.
Вышесказанное — отличный, отличный способ проверить, скажем, мы делали видеоигру и хотели проверить, были ли нажаты те или иные кнопки, если была нажата какая-либо из них. Мы могли бы просто проверить каждый из этих битов с помощью одной проверки, и это было бы во много раз эффективнее, чем выполнение булевой проверки для каждого отдельного состояния.
Теперь допустим, что у нас есть логическое значение, которое всегда обращено.
Обычно вы делаете что-то вроде
bool state = false;
state = !state;
Ну, это может быть сделано с помощью битов, а также с использованием «^оператор.
Так же, как мы выполнили «1 << N «, чтобы выбрать все значение этого бита. Мы можем сделать то же самое с обратным. Так же, как мы показали, как» | = «хранит возврат, мы будем делать то же самое с» ^ = «. Так что, если этот бит включен, мы выключаем его. Если он выключен, мы включаем его.
void reverseState(int bit)
{
state ^= (1 << bit);
}
Вы даже можете вернуть его в текущее состояние. Если вы хотите вернуть предыдущее состояние, просто поменяйте местами «! =» На «==». Поэтому он выполняет реверсирование, а затем проверяет текущее состояние.
bool reverseAndGet(int bit)
{
return ((state ^= (1 << bit)) & (1 << bit)) != 0x0;
}
Сохранение нескольких не однобитовых, также известных как bool, значений в int также может быть выполнено. Допустим, мы обычно записываем нашу координатную позицию, как показано ниже.
int posX = 0;
int posY = 0;
int posZ = 0;
Теперь предположим, что они никогда не проходили 1023. Таким образом, от 0 до 1023 было максимальным расстоянием по всем этим. Я выбираю 1023 для других целей, как уже упоминалось ранее, вы можете манипулировать «&«переменная как способ заставить значение между 0 и 2 ^ N — 1 значениями. Итак, допустим, ваш диапазон был от 0 до 1023. Мы можем выполнить» значение & 1023 «, и это всегда будет значение между 0 и 1023 без каких-либо проверок параметров индекса. Имейте в виду, как упоминалось ранее, это работает только со степенями два минус один. 2 ^ 10 = 1024 — 1 = 1023.
Например. не более, если (значение> = 0 && значение <= 1023).
Таким образом, 2 ^ 10 = 1024, что требует 10 бит для хранения числа от 0 до 1023.
Таким образом, 10×3 = 30, который все еще меньше или равен 32. Достаточно для хранения всех этих значений в int.
Таким образом, мы можем выполнить следующее. Итак, чтобы увидеть, сколько бит мы использовали. Мы делаем 0 + 10 + 20. Причина, по которой я поставил 0, заключается в том, чтобы визуально показать вам, что 2 ^ 0 = 1, поэтому # * 1 = #. Причина, по которой мы нуждаемся в << 10 объясняется тем, что x использует до 10 битов, что составляет от 0 до 1023. Поэтому нам нужно умножить y на 1024, чтобы иметь уникальные значения для каждого. Затем Z нужно умножить на 2 ^ 20, что составляет 1 048 576.
int position = (x << 0) | (y << 10) | (z << 20);
Это делает сравнение быстро.
Теперь мы можем сделать
return this.position == position;
применяется к
return this.x == x && this.y == y && this.z == z;
Теперь, что, если мы хотели фактические позиции каждого?
Для х мы просто делаем следующее.
int getX()
{
return position & 1023;
}
Тогда для y нам нужно выполнить сдвиг влево, затем AND it.
int getY()
{
return (position >> 10) & 1023;
}
Как вы можете догадаться, Z такой же, как Y, но вместо 10 мы используем 20.
int getZ()
{
return (position >> 20) & 1023;
}
Я надеюсь, что любой, кто просматривает это, найдет, что стоит информации :).
Если вы действительно хотите использовать 1 бит, вы можете использовать символ для хранения 8 логических значений и битовый сдвиг, чтобы получить значение того, которое вам нужно. Я сомневаюсь, что это будет быстрее, и, вероятно, это даст вам много головной боли, работая таким образом, но технически это возможно.
Напомним, что подобная попытка может оказаться полезной для систем, которые не имеют много памяти для переменных, но обладают большей вычислительной мощностью, чем вам нужно. Я очень сомневаюсь, что вам это когда-нибудь понадобится.