Однобайтовый bool. Зачем?

Ответ 1

Почему bool требует одного байта для хранения true или false, где достаточно всего одного бита

Поскольку каждый объект в С++ должен быть индивидуально адресуемым ^* (то есть вы должны иметь указатель на него). Вы не можете адресовать отдельный бит (по крайней мере, не на обычном оборудовании).

Насколько безопаснее использовать следующее?

Он "безопасен", но он не достигает многого.

- это техника, используемая выше, действительно поможет?

Нет, по тем же причинам, что и выше;)

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

Да, это правда. На большинстве платформ это требует доступа к содержащемуся байту (или int или тому подобное), а затем выполнению операций смещения бит и бит-маски для доступа к соответствующему биту.

Если вы действительно обеспокоены использованием памяти, вы можете использовать std::bitset в С++ или BitSet в Java, которые упаковывают биты.

_{* За несколькими исключениями.}

Ответ 2

Использование одного бита намного медленнее и намного сложнее для выделения. В C/С++ нет способа получить адрес одного бита, поэтому вы не сможете сделать &trueOrFalse как бит.

В Java есть BitSet и EnumSet, которые используют растровые изображения. Если у вас очень малое число, это может не иметь большого значения. например объекты должны быть по крайней мере байт выровнены, а в HotSpot выровнены по 8 байт (в С++ a 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

для 4M

Flip time bits 4.1 ns, bytes 0.5, shorts 1.0, ints 2.3

и 40M

Flip time bits 6.2 ns, bytes 0.7, shorts 1.1, ints 2.4

Ответ 3

Если вы хотите хранить только один бит информации, нет ничего более компактного, чем char, который является наименьшим адресуемым блоком памяти в C/С++. (В зависимости от реализации, bool может иметь тот же размер, что и char, но должен быть больше.)

A char гарантируется стандартом C для хранения не менее 8 бит, однако он также может состоять из большего количества. Точное число доступно с помощью макроса CHAR_BIT, определенного в limits.h (в C) или climits (С++). Сегодня наиболее распространено, что CHAR_BIT == 8, но вы не можете положиться на него (см. here). Тем не менее, гарантируется, что он будет работать на совместимых с POSIX системах и на Windows.

Хотя невозможно уменьшить объем памяти для одного флага, конечно, можно комбинировать несколько флагов. Помимо выполнения всех бит-операций вручную, есть несколько альтернатив:

• Если вы знаете количество бит во время компиляции
  • bitfields (как в вашем вопросе). Но будьте осторожны, упорядочение полей не гарантируется, что может привести к проблемам с переносимостью.
  • std::bitset
• Если вы знаете размер только во время выполнения
  • boost::dynamic_bitset
  • Если вам приходится иметь дело с большими битвекторами, посмотрите на библиотеку BitMagic. Он поддерживает сжатие и сильно настраивается.

Как уже отмечали другие, сохранение нескольких бит не всегда является хорошей идеей. Возможные недостатки:

• Менее читаемый код
• Уменьшенная скорость выполнения из-за дополнительного кода извлечения.
• По той же причине увеличивается размер кода, что может перевесить экономию в потреблении данных.
• Скрытые проблемы синхронизации в многопоточных программах. Например, переворачивание двух разных бит двумя разными потоками может привести к состоянию гонки. Напротив, для двух потоков всегда безопасно изменять два разных объекта примитивных типов (например, char).

Как правило, это имеет смысл, когда вы имеете дело с огромными данными, потому что тогда вы получите меньшее давление на память и кеш.

Ответ 4

Почему бы вам просто не сохранить состояние в байт? На самом деле не протестировали ниже, но это должно дать вам представление. Вы можете даже использовать короткий или 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, но он похож на полный мусор, и поскольку байты, короткие, int, уже давно находятся в своих битовых формах, вы можете использовать их как есть. Затем создайте некоторый сложный класс для доступа к отдельным битам из памяти, что я мог бы понять, прочитав несколько сообщений.

boolean getState(int index)
{
    return (states[index >> 5] & 1 << (index & 0x1F)) != 0x0;
}

Дополнительная информация...

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

Типы " byte", " короткие", " int", " длинные" все типы данных, которые имеют разные диапазоны.

Вы можете просмотреть эту ссылку: 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. Что такое 1,2,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 ^ BIT, поэтому, когда мы делаем

Я быстро перейду к некоторым операторам. Мы недавно объяснили "&" . оператора. Теперь для "|" Оператор.

При выполнении следующих

int value = 31;
value |= 16;
value |= 16;
value |= 16;
value |= 16;

Значение будет равно 31. Это связано с тем, что бит 4 или 2 ^ 4 = 16 уже включен или установлен в 1. Так что выполнение "|" возвращает это значение с включенным битом. Если он уже включен, изменений не происходит. Мы используем "| =", чтобы фактически установить переменную на это возвращаемое значение.

Вместо выполнения → "value = value | 16;". Мы просто делаем "значение | = 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;
}

Сохранение нескольких не одиночных бит aka значений 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).

So 2 ^ 10 = 1024, для которого требуется 10 бит, чтобы удерживать число от 0 до 1023.

Итак, 10x3 = 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;

Теперь, если бы мы хотели, чтобы фактические позиции каждого?

Для x мы просто выполняем следующее.

int getX()
{ 
   return position & 1023;
}

Тогда для y нам нужно выполнить сдвиг левого бита, а затем AND.

int getY()
{ 
   return (position >> 10) & 1023;
}

Как вы можете догадаться, Z является тем же, что и Y, но вместо 10 мы используем 20.

int getZ()
{ 
   return (position >> 20) & 1023;
}

Я надеюсь, что кто-нибудь, кто его увидит, найдет нужную информацию:).

Ответ 5

Если вы действительно хотите использовать 1 бит, вы можете использовать char для хранения 8 булевых элементов и бит-дро, чтобы получить значение того, которое вы хотите. Я сомневаюсь, что это будет быстрее, и, вероятно, это даст вам много головных болей, работающих таким образом, но технически это возможно.

С другой стороны, попытка, подобная этой, может оказаться полезной для систем, которые не имеют большого количества памяти, доступной для переменных, но имеют некоторую большую вычислительную мощность, чем то, что вам нужно. Я очень сомневаюсь, что вам это когда-нибудь понадобится.