C/C++ 基本类型的值是如何物理存储的?
How are the values of fundamental C/C++ types physically stored?
我正在玩状态-space,这需要非常有效地存储探索状态。这意味着,我需要将多个信息存储在一个尽可能小的变量中。
让我们举一个非常简单的例子:假设我想存储两个坐标。我可以创建一个包含两个整数的结构,但每个整数都是(如果我错了请纠正我)32b。但是我的两个坐标都不大于15。对于零,它是 16 = 2^4 个不同的值,这意味着我只需要 8b 来存储它们。因此,通过一些按位运算符的魔法,我可以将这两个值存储在一个 char
:
中
unsigned int x, y; // initialized!!!!!
char my_code = (x << 4) | y;
当然,只有 x
和 y
存储在 "straight-code" 中时,此代码才有效(我不确定这个名称。 它是数字的简单二进制表示,从最大位 2^n 到 2^1 )
所以我的问题是:哪些二进制代码用于存储哪些基本 C/C++ 变量?
编辑: 过早优化?不,我当前的任务很小,正在为更大的问题做准备,我需要存储从 0 到 7 的 4 个坐标。这些坐标是 8x8 板上的位置。所以我需要跟踪许多独特的组合 - 因为 state-space 搜索是基于生成新的状态,这些状态还没有被探索过。
无法存储多个整数并使用自定义比较器函数和 set
。对于像这样的大问题,我的记忆会流失并且跟踪我已经访问过的内容也不是一件好事。具有可能组合大小的位集可能是最好的方法。 (你可能会说,我描述的那个问题对于那么大的位集来说太大了,但是有一个巧妙的技巧来处理它,这个问题不重要。)所以,我需要某种 "hash",它可以是创建了许多方法 - 使用模块化算术(一种类型的答案)或按位运算。这两种解决方案之间的复杂性对于今天的计算机来说并没有太大区别。因为好奇,所以想用更奇特的第二种方式。但是为了让它起作用,我需要知道数字是如何存储在二进制级别的——如果有一些真实的编码,那我的想法绝对无法使用。
我的问题也不是关于变量的大小 - 这些都有很好的记录。
Of course, this code will work only, if x
and y
are stored in "straight-code"
我猜您要查找的字词是 endianness。但是,无论系统的字节顺序如何,(x << 4) | y
都会为您提供相同的值。数学 endian-agnostic。数学只是数学。唯一的区别是内存布局是什么 - 对于单个字节,即使这样也无关紧要。
我们可以举个例子。假设 x
是 0x0A0B0C0D
,y
是 0x01020304
。如果你的系统是 big-endian,这意味着内存布局是:
x : 0A 0B 0C 0D
y : 01 02 03 04
x << 4 : A0 B0 C0 D0
(x << 4) | y : A1 B2 C3 D4
to char : D4
如果是小端:
x : 0D 0C 0B 0A
y : 04 03 02 01
x << 4 : D0 C0 B0 A0
(x << 4) | y : D4 C3 B2 A1
to char : D4
无论如何,0xD4
。
尽管如此,您确实需要担心的一件事是实际转换为 char
。来自 [conv.integral]:
If the destination type is unsigned, the resulting value is the least unsigned integer congruent to the source
integer (modulo 2n where n is the number of bits used to represent the unsigned type). [ Note: In a two’s
complement representation, this conversion is conceptual and there is no change in the bit pattern (if there
is no truncation). —end note ]
If the destination type is signed, the value is unchanged if it can be represented in the destination type;
otherwise, the value is implementation-defined.
如果 char
是无符号的,那部分是明确定义的。如果它被签名,它不是。所以更喜欢使用 unsigned char
作为 my_code
.
C 不强制要求 short
、int
或 long
的大小;它指定了它们必须能够表示的值的范围。 unsigned int
必须能够表示 至少 0 到 65535 范围内的值,这意味着它必须 至少 16 位宽,尽管它可能(而且经常)更宽。带符号的 int
必须表示 至少 范围 -32767 到 32767。请注意,C 不要求二进制补码表示,这就是为什么较低的值是 -32767 而不是 - 32768。
此外,除了值位之外,这些类型可能还有 填充位 。我从来没有研究过在整数类型中使用填充位的实现。
整数值使用常规二进制表示形式存储在值位中(即,N 位,最左边的位是最高有效位)。
C99 添加了 stdint.h
header,它定义了具有精确宽度且没有填充位的整数类型。如果您的值确实在 0 到 15 之间,那么我建议您对每个值使用 uint8_t
(8 位,无符号)。由于这些类型适合单个字节,因此不会有任何字节顺序问题。
C/C++ 标准不强制 integral types 的特定表示。实际上,标准允许三种不同的表示形式——二进制补码、个数补码和带符号的幅度表示法。幸运的是,正数在所有表示中看起来都一样。
无论如何,您不必关心它——只需避免位操作运算符,如下所示。如果你的坐标范围是[0, N),你可以把它们打包成更宽的数据类型如:
code = N * x + y;
或
code = N * N * x + N * y + z;
对于 N = 16,您可以将两个坐标打包成一个 unsigned char
作为:
unsigned char code = 16*x + y;
不要尝试自己破解。编译器完全有能力直接这样做:
struct Packed {
unsigned x : 4;
unsigned y : 4;
};
最好有几百万,不然省的不划算
我正在玩状态-space,这需要非常有效地存储探索状态。这意味着,我需要将多个信息存储在一个尽可能小的变量中。
让我们举一个非常简单的例子:假设我想存储两个坐标。我可以创建一个包含两个整数的结构,但每个整数都是(如果我错了请纠正我)32b。但是我的两个坐标都不大于15。对于零,它是 16 = 2^4 个不同的值,这意味着我只需要 8b 来存储它们。因此,通过一些按位运算符的魔法,我可以将这两个值存储在一个 char
:
unsigned int x, y; // initialized!!!!!
char my_code = (x << 4) | y;
当然,只有 x
和 y
存储在 "straight-code" 中时,此代码才有效(我不确定这个名称。 它是数字的简单二进制表示,从最大位 2^n 到 2^1 )
所以我的问题是:哪些二进制代码用于存储哪些基本 C/C++ 变量?
编辑: 过早优化?不,我当前的任务很小,正在为更大的问题做准备,我需要存储从 0 到 7 的 4 个坐标。这些坐标是 8x8 板上的位置。所以我需要跟踪许多独特的组合 - 因为 state-space 搜索是基于生成新的状态,这些状态还没有被探索过。
无法存储多个整数并使用自定义比较器函数和 set
。对于像这样的大问题,我的记忆会流失并且跟踪我已经访问过的内容也不是一件好事。具有可能组合大小的位集可能是最好的方法。 (你可能会说,我描述的那个问题对于那么大的位集来说太大了,但是有一个巧妙的技巧来处理它,这个问题不重要。)所以,我需要某种 "hash",它可以是创建了许多方法 - 使用模块化算术(一种类型的答案)或按位运算。这两种解决方案之间的复杂性对于今天的计算机来说并没有太大区别。因为好奇,所以想用更奇特的第二种方式。但是为了让它起作用,我需要知道数字是如何存储在二进制级别的——如果有一些真实的编码,那我的想法绝对无法使用。
我的问题也不是关于变量的大小 - 这些都有很好的记录。
Of course, this code will work only, if
x
andy
are stored in "straight-code"
我猜您要查找的字词是 endianness。但是,无论系统的字节顺序如何,(x << 4) | y
都会为您提供相同的值。数学 endian-agnostic。数学只是数学。唯一的区别是内存布局是什么 - 对于单个字节,即使这样也无关紧要。
我们可以举个例子。假设 x
是 0x0A0B0C0D
,y
是 0x01020304
。如果你的系统是 big-endian,这意味着内存布局是:
x : 0A 0B 0C 0D
y : 01 02 03 04
x << 4 : A0 B0 C0 D0
(x << 4) | y : A1 B2 C3 D4
to char : D4
如果是小端:
x : 0D 0C 0B 0A
y : 04 03 02 01
x << 4 : D0 C0 B0 A0
(x << 4) | y : D4 C3 B2 A1
to char : D4
无论如何,0xD4
。
尽管如此,您确实需要担心的一件事是实际转换为 char
。来自 [conv.integral]:
If the destination type is unsigned, the resulting value is the least unsigned integer congruent to the source integer (modulo 2n where n is the number of bits used to represent the unsigned type). [ Note: In a two’s complement representation, this conversion is conceptual and there is no change in the bit pattern (if there is no truncation). —end note ]
If the destination type is signed, the value is unchanged if it can be represented in the destination type; otherwise, the value is implementation-defined.
如果 char
是无符号的,那部分是明确定义的。如果它被签名,它不是。所以更喜欢使用 unsigned char
作为 my_code
.
C 不强制要求 short
、int
或 long
的大小;它指定了它们必须能够表示的值的范围。 unsigned int
必须能够表示 至少 0 到 65535 范围内的值,这意味着它必须 至少 16 位宽,尽管它可能(而且经常)更宽。带符号的 int
必须表示 至少 范围 -32767 到 32767。请注意,C 不要求二进制补码表示,这就是为什么较低的值是 -32767 而不是 - 32768。
此外,除了值位之外,这些类型可能还有 填充位 。我从来没有研究过在整数类型中使用填充位的实现。
整数值使用常规二进制表示形式存储在值位中(即,N 位,最左边的位是最高有效位)。
C99 添加了 stdint.h
header,它定义了具有精确宽度且没有填充位的整数类型。如果您的值确实在 0 到 15 之间,那么我建议您对每个值使用 uint8_t
(8 位,无符号)。由于这些类型适合单个字节,因此不会有任何字节顺序问题。
C/C++ 标准不强制 integral types 的特定表示。实际上,标准允许三种不同的表示形式——二进制补码、个数补码和带符号的幅度表示法。幸运的是,正数在所有表示中看起来都一样。
无论如何,您不必关心它——只需避免位操作运算符,如下所示。如果你的坐标范围是[0, N),你可以把它们打包成更宽的数据类型如:
code = N * x + y;
或
code = N * N * x + N * y + z;
对于 N = 16,您可以将两个坐标打包成一个 unsigned char
作为:
unsigned char code = 16*x + y;
不要尝试自己破解。编译器完全有能力直接这样做:
struct Packed {
unsigned x : 4;
unsigned y : 4;
};
最好有几百万,不然省的不划算