java - 一字节布尔值。为什么？

Question

在 C++ 中，为什么 bool 需要一个字节来存储真或假，而只有一位就足够了，比如 0 代表假，1 代表真？（为什么 Java 也需要一个字节？）

其次，使用以下内容有多安全？

struct Bool {
    bool trueOrFalse : 1;
};

第三，就算是安全的，上面的野外技术真的有用吗？因为我听说我们在那里节省了空间，但是编译器生成的访问它们的代码仍然比生成的访问原语的代码更大更慢。

Answer 1

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

因为 C++ 中的每个对象都必须是可单独寻址的^*（也就是说，您必须能够拥有指向它的指针）。您不能寻址单个位（至少不能在传统硬件上）。

使用以下内容有多安全？

它是“安全的”，但收效甚微。

上述现场技术真的有用吗？

不，出于与上述相同的原因；）

但是编译器生成的访问它们的代码仍然比生成的访问原语的代码更大且更慢。

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

---

如果您真的关心内存使用情况，您可以std::bitset在 C++ 或BitSetJava 中使用 a ，它们会打包位。

---

_{* 除少数例外。}

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++ 中最小的可寻址内存单元。（根据实现， abool可能与 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. 如果您必须处理大型位向量，请查看BitMagic 库。它支持压缩并经过大量调整。

正如其他人已经指出的那样，节省一些位并不总是一个好主意。可能的缺点是：

1. 可读性较差的代码
2. 由于额外的提取代码而降低了执行速度。
3. 出于同样的原因，代码大小的增加可能会超过数据消耗的节省。
4. 多线程程序中隐藏的同步问题。例如，两个不同的线程翻转两个不同的位可能会导致竞争条件。相反，两个线程修改两个不同的原始类型对象（例如，char）总是安全的。

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

Answer 4

为什么不将状态存储到一个字节？还没有实际测试过以下内容，但它应该给你一个想法。您甚至可以将 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];

现在您可能想知道如何从 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 的东西是什么，但它看起来像完全垃​​圾，因为 byte、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 还是 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。所以执行“|” 在该位打开的情况下返回该值。如果它已经打开，则不会进行任何更改。我们使用“|=”将变量实际设置为该返回值。

而不是做->“值=值| 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^10 = 1024 - 1 = 1023。

例如，如果（值 >= 0 && 值 <= 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;
}

我希望任何看到这个的人都会发现值得一读的信息:)。

Answer 5

如果你真的想使用 1 位，你可以使用 char 来存储 8 个布尔值，并使用 bitshift 来获得你想要的值。我怀疑它会更快，而且它可能会让你很头疼，但从技术上讲这是可能的。

附带说明一下，这样的尝试可能对没有大量内存可用于变量但确实具有比您需要的更多处理能力的系统有用。我非常怀疑你是否会需要它。