单字节布尔.为什么？

Question

在C++中,为什么bool需要一个字节来存储true或false,其中只有一个位足够,例如0表示false,1表示true表示？(为什么Java也需要一个字节？)

其次,使用以下内容会更安全多少？

struct Bool {
    bool trueOrFalse : 1;
};

第三,即使它是安全的,上述现场技术真的会有所帮助吗？因为我听说我们在那里节省空间,但是编译器生成的代码访问它们比访问基元所生成的代码更大更慢.

Answer 1

为什么bool需要一个字节来存储真或假只有一位就足够了

因为C++中的每个对象都必须是可单独寻址的^*(也就是说,你必须能够指向它).您无法寻址单个位(至少不能用于传统硬件).

使用以下内容更安全多少？

这是"安全的",但并没有取得多大成就.

上面的现场技术真的会有所帮助吗？

不,出于与上述相同的原因;)

但仍然使用编译器生成的代码来访问它们比访问基元所生成的代码更大更慢.

是的,这是真的.在大多数平台上,这需要访问包含的字节(或int其他),然后执行位移和位掩码操作以访问相关位.

如果您真的关心内存使用情况,可以使用std::bitsetC++或BitSetJava中的包装.

_{*除了少数例外.}

Answer 2

使用单个位要慢得多,分配起来要复杂得多.在C/C++中,无法获得一位的地址,因此您无法做到&trueOrFalse这一点.

Java有一个BitSet和EnumSet,它们都使用位图.如果你的数字非常少,那可能没什么区别.例如,对象必须是至少字节对齐的,而在HotSpot中是8字节对齐的(在C++中,new对象可以是8到16字节对齐)这意味着保存几位可能不会节省任何空间.

至少在Java中,Bits并不快,除非它们更好地适应缓存.

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

Answer 3

如果你只想存储一位信息,那么没有什么比a更紧凑char,这是C/C++中最小的可寻址存储单元.(根据实现情况,a bool可能与a 具有相同的大小,char但允许更大.)

charC标准保证A 至少保持8位,但它也可以包含更多位.确切的数字可通过(C)或(C++)中CHAR_BIT定义的宏获得.今天,最常见的是你不能依赖它(见这里).但是,在POSIX兼容系统和Windows上,它保证为8 .limits.hclimitsCHAR_BIT == 8

虽然不可能减少单个标志的内存占用,但当然可以组合多个标志.除了手动执行所有位操作外,还有一些替代方法:

• 如果你知道编译时的位数
  1. 位域(如你的问题).但请注意,不保证字段的排序,这可能导致可移植性问题.
  2. std::bitset
• 如果只在运行时知道大小
  1. boost::dynamic_bitset
  2. 如果你必须处理大的bitvectors,看看BitMagic库.它支持压缩并且经过大量调整.

正如其他人已经指出的那样,节省几位并不总是一个好主意.可能的缺点是:

1. 代码不太可读
2. 由于额外的提取代码,降低了执行速度.
3. 出于同样的原因,代码大小的增加可能超过数据消耗的节省.
4. 多线程程序中的隐藏同步问题.例如,通过两个不同的线程翻转两个不同的比特可能导致竞争条件.相反,两个线程修改两个不同的基本类型对象(例如,char)总是安全的.

通常,当您处理大量数据时,它是有意义的,因为这样您将受益于对内存和缓存的较小压力.

Answer 4

为什么不将状态存储到一个字节？实际上没有测试过下面,但它应该给你一个想法.您甚至可以使用16或32个州的short或int.我相信我也有一个有效的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];

现在您可能想知道如何从128阵列访问索引4095.所以我们要做的就是简化它.4095向右移5位,技术上与32除以相同.所以4095/32 =向下舍入(127).所以我们在数组的索引127处.然后我们执行4095和31,它将把它强制转换为0到31之间的值.这只能用2减1.的幂.例如0,1,3,7,15,31,63,127,255,511,1023等...

所以现在我们可以访问该位置的位.正如您所看到的,这非常紧凑,并且在文件中有4096个布尔值:)这也将为二进制文件提供更快的读/写.我不知道这个BitSet的东西是什么,但它看起来像完全垃​​圾,因为字节,short,int,long已经在它们的位形式中技术上你可能也可以使用它们.然后创建一些复杂的类来访问内存中的各个位,这是我从阅读几篇文章中可以掌握的.

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

更多的信息.​​..

基本上,如果上面的内容有点令人困惑,那么这就是正在发生的事情的简化版本.

" byte "," short "," int "," long "类型都是具有不同范围的数据类型.

您可以查看此链接:http://msdn.microsoft.com/en-us/library/s3f49ktz(v = vs.80).aspx

查看每个的数据范围.

所以一个字节等于8位.所以一个4字节的int将是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.我们不是在31中有第5位.所以这只会返回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;
}

也可以将多个非单位又名bool值存储到int中.假设我们通常会写出如下所示的坐标位置.

int posX = 0;
int posY = 0;
int posZ = 0;

现在让我们说这些从未通过1023.所以0到1023是所有这些的最大距离.我选择1023用于其他目的,如前所述,您可以操纵"&"变量作为强制0到2 ^ N - 1值之间的值的方法.所以假设你的范围是0到1023.我们可以执行"value&1023",它总是一个0到1023之间的值,没有任何索引参数检查.请记住,如前所述,这只适用于2减1的幂.2 ^ 10 = 1024 - 1 = 1023.

例如,不再是if(value> = 0 && value <= 1023).

所以2 ^ 10 = 1024,这需要10位才能保持0到1023之间的数字.

所以10x3 = 30仍然小于或等于32.足以将所有这些值保存在int中.

所以我们可以执行以下操作.那么看看我们使用了多少比特.我们做0 + 10 + 20.我把0放在那里的原因是为了在视觉上向你展示2 ^ 0 = 1所以#*1 =#.我们需要y << 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,我们需要执行左移位然后和它.

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

你可能猜测Z与Y相同,但是我们使用20而不是10.

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

我希望无论谁看到这个都会发现它值得信息:).