将多个 int 值存储到一个变量中 - C++

Question

我正在进行算法竞赛，我正在尝试优化我的代码。也许我想做的事情很愚蠢而且不可能，但我想知道。

我有这些要求：

一个库存可以包含 4 种不同类型的物品。此库存不能包含超过 10 个项目（包括所有类型）。有效库存示例：1 / 1 / 1 / 0。无效库存示例：11 / 0 / 0 / 0 或 5 / 5 / 5 / 0
我有一些 recepe 可以消耗物品或将物品添加到我的库存中。这自库存以来，recepe 不能添加或消耗超过 10 个项目不能超过 10 个项目。有效接收示例：-1 / -2 / 3 / 0.无效recepe示例：-6 / -6 / +12 / 0

目前，我将库存和收据存储为 4 个整数。然后我可以执行一些操作，例如：

ApplyRecepe: Inventory(1/1/1/0).Apply(Recepe(-1/1/0/0)) = Inventory(0/2/1/0)
CanAfford: Iventory(1/1/0/0).CanAfford(Recepe(-2/1/0/0)) = False

我想知道是否可以（如果可以，如何）将库存/收据的 4 个值存储到一个整数中并对其执行先前的操作，这比比较/添加更快我现在正在做的 4 个整数。

我想到了这样的库存：

int32:XXXX(第一类项目数)-YYYY(第二类项目数)-ZZZ(第三类项目数)-WWW(第四类项目数)

但是我有两个问题：

我不知道如何处理可能的负值
在我看来，这比仅将 4 个整数相加要慢得多，因为我必须对库存和 recepe 进行位移以获得我想要的值，然后继续进行相加。

Answer 1

特别是如果您正在学习，尝试为 vectorization 实现您自己的助手 class 并因此加深您对 C++ 数据的理解是一个不错的机会，即使您的用例可能不保证该技术。

你想利用的洞察力是算术运算似乎对位移是不变的，如果人们考虑了讨厌的进位位和标志的影响（例如二进制补码）。但正是由于后面这些因素，正如@Botje 建议的那样，使用一些标准化基础类型（如 int8_t[] 会更好。

首先，实现以下功能。（我的 C++ 生锈了，考虑这个伪代码。）

int8_t* add(int8_t[], int8_t[], size_t);
int8_t* multiply(int8_t[], int8_t[], size_t);
int8_t* zeroes(size_t); // additive identity
int8_t* ones(size_t); // multiplicative identity

同时考虑：

您想如何处理上溢和下溢？让他们去，要求开发商谨慎行事？或者抛出异常？
也许您想确定数组的大小并避免处理动态 size_t？
也许您想深入了解重载运算符？

像这样的练习的最终结果，但经过概括和完善，类似于 Armadillo. But you'll understand it on a whole different level by doing the exercise yourself first. Also, if all this makes sense so far, you can now take a look at ——在某些情况下，甚至编译器也可以为您矢量化。

正如@Botje 提到的那样，Bitpacking 是超越此的又一步。您甚至不会像 int8_t 或 int4_t 这样的整数类型那样安全和方便。这还意味着您编写的代码可能不再与平台无关。我建议在深入研究之前至少完成矢量化练习。

Answer 2

Storing multiple int values into one variable

这里有两个选择：

数组。这样做的好处是您可以迭代元素：

int variable[] {
    1,
    1,
    1,
    0,
};

或class。这样做的好处是可以命名成员：

struct {
    int X;
    int Y;
    int Z;
    int W;
} variable {
    1,
    1,
    1,
    0,
};

Then I am able to perform some operations like:

那些看起来像 SIMD 向量运算（单指令多数据）。在这种情况下，数组是可行的方法。由于操作数的数量在您的描述中似乎是常数且很小，因此执行它们的有效方法是对 CPU ¹.

进行向量运算

在 C++ 中没有直接使用 SIMD 操作的标准方法。为了让编译器有最佳机会使用它们，需要遵循以下步骤：

确保您使用的 CPU 支持您需要的操作。 AVX-2 指令集及其扩展广泛支持整数向量运算。
确保您告诉编译器应该针对该体系结构优化程序。
确保告诉编译器执行向量化优化。
确保整数按照操作的要求充分对齐。这可以通过 alignas.
确保整数个数在编译时已知。

如果您担心依赖优化器的前景，那么您可能更愿意使用编译器可能提供的向量扩展。语言扩展的使用自然会以对其他编译器的可移植性为代价。这是 GCC 的示例：

constexpr int count = 4;
using v4si = int __attribute__ ((vector_size (sizeof(int) * count)));

#include <iostream>

int main()
{
    v4si inventory { 1, 1, 1, 0};
    v4si recepe    {-1, 1, 0, 0};

    v4si applied = inventory + recepe;

    for (int i = 0; i < count; i++) {
        std::cout << applied[i] << ", ";
    }
}

¹如果操作数的数量很大，那么GPU等专用向量处理器可能会更快。

Answer 3

这将是一个非答案，只是为了展示您在进行位打包时遇到的问题。

为了简单起见，假设食谱只能从库存中移除，并且只能包含正值（您可以使用二进制补码表示负数，但它会占用更多位，并增加使用位的复杂性- 压缩数字）。

然后您有 11 个可能的项目值，因此每个项目需要 4 位。然后可以在一个 uint16 中表示四个项目。

所以，假设您的库存有 10、4、6、9 件商品；这将是 uint16_t inv = 0b1010'0100'0110'1001.

然后，包含 2,2,2,2 项或 uint16_t rec = 0b0010'0010'0010'0010 的食谱。

inv - rec 将为 8、2、4、7 项提供 0b1000'0010'0100'0111。

到目前为止，还不错。在进行计算之前，无需进行移位和屏蔽以获取各个值。耶。

现在，包含 6、6、6、6 项的食谱将是 0b0110'0110'0110'0110，为 3、14、0、3 项提供 inv - rec = 0b0011'1110'0000'0011。

糟糕。

算术会起作用，但仅如果您事先检查各个 4 位结果没有超出范围；在此示例中，这意味着您事先知道库存中有足够的物品来填充食谱。

例如，您可以通过以下方式获得库存中的第三项：(inv >> 4) & 0b1111 或 (inv << 8) >> 12 进行检查。

对于测试，您将得到如下表达式：

if ((inv >> 4) & 0b1111 >= (rec >> 4) & 0b1111)

或者，比较“到位”的 4 位：

if (inv & 0b0000000011110000 >= rec & 0b0000000011110000)

每个 4 位部分。

这些都是可以做到的，但是你愿意吗？在编译器完成工作后，它可能不会比其他答案中建议的更快，而且它肯定不会更具可读性。

当你在食谱中允许使用负数（二进制补码或其他）时，情况会变得更加糟糕，尤其是当你想对它们进行位移时。

因此，位打包非常适合存储，在极少数情况下，您甚至可以在不解压位的情况下进行数学运算，但我不会尝试去那里（除非您非常性能和内存受限）。

话虽如此，尝试让它工作可能会很有趣；总是这样。

将多个 int 值存储到一个变量中 - C++

Storing multiple int values into one variable - C++

c++

bit-shift