在C++中将32位数字拆分为字节的最快方法

Question

我正在编写一段代码，旨在对CLSID结构进行数据压缩。我将它们存储为128位整数的压缩流。然而，相关代码必须能够将无效的CLSIDs放入流中。为了做到这一点，我将它们保留为一个大字符串。在磁盘上，它看起来像这样：

+--------------------------+-----------------+------------------------+
|                          |                 |                        |
| Length of Invalid String | Invalid String  | Compressed Data Stream |
|                          |                 |                        |
+--------------------------+-----------------+------------------------+

为了编码字符串的长度，我需要逐字节输出作为字符串长度的32位整数。以下是我的当前代码：

std::vector<BYTE> compressedBytes;
DWORD invalidLength = (DWORD) invalidClsids.length();
compressedBytes.push_back((BYTE)  invalidLength        & 0x000000FF);
compressedBytes.push_back((BYTE) (invalidLength >>= 8) & 0x000000FF));
compressedBytes.push_back((BYTE) (invalidLength >>= 8) & 0x000000FF));
compressedBytes.push_back((BYTE) (invalidLength >>= 8));

这段代码不会被频繁调用，但在解码阶段需要有类似的结构被调用数千次。我想知道这是否是最有效的方法，或者是否有更好的方法？

谢谢大家！

Billy3

编辑： 在查看了一些答案后，我创建了这个小测试程序来测试哪个是最快的：

// temp.cpp : Defines the entry point for the console application.
//

#include "stdafx.h"
#include <windows.h>
#include <ctime>
#include <iostream>
#include <vector>

void testAssignedShifts();
void testRawShifts();
void testUnion();

int _tmain(int argc, _TCHAR* argv[])
{
    std::clock_t startTime = std::clock();
    for (register unsigned __int32 forLoopTest = 0; forLoopTest < 0x008FFFFF; forLoopTest++)
    {
        testAssignedShifts();
    }
    std::clock_t assignedShiftsFinishedTime = std::clock();
    for (register unsigned __int32 forLoopTest = 0; forLoopTest < 0x008FFFFF; forLoopTest++)
    {
        testRawShifts();
    }
    std::clock_t rawShiftsFinishedTime = std::clock();
    for (register unsigned __int32 forLoopTest = 0; forLoopTest < 0x008FFFFF; forLoopTest++)
    {
        testUnion();
    }
    std::clock_t unionFinishedTime = std::clock();
    std::printf(
        "Execution time for assigned shifts: %08u clocks\n"
        "Execution time for raw shifts:      %08u clocks\n"
        "Execution time for union:           %08u clocks\n\n",
        assignedShiftsFinishedTime - startTime,
        rawShiftsFinishedTime - assignedShiftsFinishedTime,
        unionFinishedTime - rawShiftsFinishedTime);
    startTime = std::clock();
    for (register unsigned __int32 forLoopTest = 0; forLoopTest < 0x008FFFFF; forLoopTest++)
    {
        testAssignedShifts();
    }
    assignedShiftsFinishedTime = std::clock();
    for (register unsigned __int32 forLoopTest = 0; forLoopTest < 0x008FFFFF; forLoopTest++)
    {
        testRawShifts();
    }
    rawShiftsFinishedTime = std::clock();
    for (register unsigned __int32 forLoopTest = 0; forLoopTest < 0x008FFFFF; forLoopTest++)
    {
        testUnion();
    }
    unionFinishedTime = std::clock();
    std::printf(
        "Execution time for assigned shifts: %08u clocks\n"
        "Execution time for raw shifts:      %08u clocks\n"
        "Execution time for union:           %08u clocks\n\n"
        "Finished. Terminate!\n\n",
        assignedShiftsFinishedTime - startTime,
        rawShiftsFinishedTime - assignedShiftsFinishedTime,
        unionFinishedTime - rawShiftsFinishedTime);

    system("pause");
    return 0;
}

void testAssignedShifts()
{
    std::string invalidClsids("This is a test string");
    std::vector<BYTE> compressedBytes;
    DWORD invalidLength = (DWORD) invalidClsids.length();
    compressedBytes.push_back((BYTE)  invalidLength);
    compressedBytes.push_back((BYTE) (invalidLength >>= 8));
    compressedBytes.push_back((BYTE) (invalidLength >>= 8));
    compressedBytes.push_back((BYTE) (invalidLength >>= 8));
}
void testRawShifts()
{
    std::string invalidClsids("This is a test string");
    std::vector<BYTE> compressedBytes;
    DWORD invalidLength = (DWORD) invalidClsids.length();
    compressedBytes.push_back((BYTE) invalidLength);
    compressedBytes.push_back((BYTE) (invalidLength >>  8));
    compressedBytes.push_back((BYTE) (invalidLength >>  16));
    compressedBytes.push_back((BYTE) (invalidLength >>  24));
}

typedef union _choice
{
    DWORD dwordVal;
    BYTE bytes[4];
} choice;

void testUnion()
{
    std::string invalidClsids("This is a test string");
    std::vector<BYTE> compressedBytes;
    choice invalidLength;
    invalidLength.dwordVal = (DWORD) invalidClsids.length();
    compressedBytes.push_back(invalidLength.bytes[0]);
    compressedBytes.push_back(invalidLength.bytes[1]);
    compressedBytes.push_back(invalidLength.bytes[2]);
    compressedBytes.push_back(invalidLength.bytes[3]);
}

运行几次后会得到以下结果：

Execution time for assigned shifts: 00012484 clocks
Execution time for raw shifts:      00012578 clocks
Execution time for union:           00013172 clocks

Execution time for assigned shifts: 00012594 clocks
Execution time for raw shifts:      00013140 clocks
Execution time for union:           00012782 clocks

Execution time for assigned shifts: 00012500 clocks
Execution time for raw shifts:      00012515 clocks
Execution time for union:           00012531 clocks

Execution time for assigned shifts: 00012391 clocks
Execution time for raw shifts:      00012469 clocks
Execution time for union:           00012500 clocks

Execution time for assigned shifts: 00012500 clocks
Execution time for raw shifts:      00012562 clocks
Execution time for union:           00012422 clocks

Execution time for assigned shifts: 00012484 clocks
Execution time for raw shifts:      00012407 clocks
Execution time for union:           00012468 clocks

看起来分配班次和工会之间存在平衡。由于我稍后需要这个值，所以选择工会！谢谢！

Billy3

- Billy ONeal

---

叹气。你放弃了一个完美的方法，用一种在可移植性方面更糟糕的东西代替它。 - starblue

如果你非常关心时间，我建议忘记联合/移位差异--你只需要计算出向量将增长多少字节，并在开始时调用reserve()一次，以避免多次向量重新分配，这样会获得更大的优势。 - j_random_hacker

@starblue：实际上我倾向于同意这一点，特别是考虑到联合体并没有提供任何可观察的加速。即使在这种情况下我们已经确定这是特定于Windows的代码，但今天是这样--谁知道它将来会在哪里运行... - j_random_hacker

Answer 1

这可能是你能得到的最优化的方式了。位运算是处理器上可用的最快速度之一。

将 >>=8 >>= 8 缩减为 >> 16, >> 24 可能会更快，因为可以减少赋值操作。

此外，我认为你不需要 & - 因为你正在转换为 BYTE（应该是 8 位字符），它会适当地被截断。（是吗？如果我错了请纠正我）

总的来说，这些都是非常微小的改变。进行性能分析以查看是否真的有所不同:P

- v3.

---

如果优化器被打开，赋值和 & 0xFF 都不太可能有所区别（它们应该被优化掉）。如果优化器关闭了，讨论什么最有效也没有实际意义。 - SoapBox

这个值得加一，因为它是唯一的与字节序无关的方法，通常这是做事情的最佳方式。 - j_random_hacker

Answer 2

只需使用联合：

assert(sizeof (DWORD) == sizeof (BYTE[4]));   // Sanity check

union either {
    DWORD dw;
    struct {
         BYTE b[4];
    } bytes;
};

either invalidLength;
invalidLength.dw = (DWORD) invalidClsids.length();
compressedBytes.push_back(either.bytes.b[0]);
compressedBytes.push_back(either.bytes.b[1]);
compressedBytes.push_back(either.bytes.b[2]);
compressedBytes.push_back(either.bytes.b[3]);

注意：与原问题中的位移方法不同，此代码生成的输出结果取决于字节序。 这只有在从一个计算机上运行的程序的输出将在具有不同字节序的计算机上读取时才有影响——但由于使用这种方法似乎没有可测量的速度增加，所以最好使用更便携的位移方法，以防万一。

- j_random_hacker

---

我得到的印象是使用联合体作为强制转换是错误的。联合体最好用于节省内存的方式，当您只需要一次使用一个大型项目时，不必将两个大型项目存储在内存中。 - Ed.

此外，如果这段代码可能会被移植，请确保您理解字节序问题... - Michael Burr

@Ed：实际上你的理解是错误的：C++标准明确允许“重新解释”联合体的内容（3.10.15）——导致未定义行为的是将指向X的指针强制转换为指向Y的指针（其中X和Y是不相关的类型），然后对其进行解引用。 - j_random_hacker

@Ed：将X强制转换为Y，其中X和Y是不相关的类型，会破坏C++的别名假设，即Y对象只能由静态类型Y*（或Y的基类指针）指向。这种假设对于生成优化代码非常重要。 - j_random_hacker

@BillyONeal：有点道理。字节序依赖性只有在输出被读取的机器具有不同的字节序时才重要，这在这种情况下可能不太可能发生（CLSIDs有点暗示了Windows，现在只在小端CPU上运行）。 - j_random_hacker

Answer 3

你应该进行测量而不是猜测任何潜在的改进，但我的第一个想法是，做一个联合操作可能会更快，具体如下：

typedef union {
    DWORD d;
    struct {
        BYTE b0;
        BYTE b1;
        BYTE b2;
        BYTE b3;
    } b;
} DWB;

std::vector<BYTE> compBytes;
DWB invLen;
invLen.d = (DWORD) invalidClsids.length();
compBytes.push_back(invalidLength.b.b3);
compBytes.push_back(invalidLength.b.b2);
compBytes.push_back(invalidLength.b.b1);
compBytes.push_back(invalidLength.b.b0);

可能这是推回操作的正确顺序，但请检查一下 - 这取决于CPU的字节序。

- paxdiablo

---

这段代码有潜力比其他联合答案更好，因为您可以使用ifdefs反转b0-b3的顺序，然后此代码将在小端和大端机器上产生相同的输出。 - SoapBox

完全同意“测量一切”的观点。在这种情况下，我的猜测是向量重新分配将完全超过位移和联合之间的任何差异 - 因此，如果您可以提前确定compBytes将占用多少字节并保留（）那么多，那就是您可能会大获成功的地方。 - j_random_hacker

@Soapbox：很酷的想法！另一方面，严格来说，符合标准的编译器可能会在DWB.b中每个BYTE之间引入任意数量的填充，而对于4个BYTE的数组则不允许这样做。但这只是一个小问题；实际上，每个编译器都有一种机制来压缩结构体。 - j_random_hacker

Answer 4

一个真正快速的方法是，将DWORD*（单元素数组）视为BYTE*（4个元素数组）。代码也更易读。

警告：我没有编译过这个代码。

警告：这将使您的代码依赖于字节顺序。

std::vector<BYTE> compressedBytes;
DWORD invalidLength = (DWORD) invalidClsids.length();
BYTE* lengthParts = &invalidLength;
static const int kLenghtPartsLength = sizeof(DWORD) / sizeof(BYTE);
for(int i = 0; i < kLenghtPartsLength; ++i)
    compressedBytes.push_back(lengthParts[i]);

- Ed.

---

注意：这与i_random_hacker提供的“联合”答案具有相同的结果。 - SoapBox

假设BYTE是某种（可能是有符号或无符号）char类型，C++标准保证这里不会发生未定义的行为 - 尽管与联合一样，它仍然是实现定义的行为（正如您指出的那样，在这里有效地意味着字节顺序依赖性）。 - j_random_hacker

@SoapBox 在汇编中的结果可能是相同的，但正如我在 j_random_hacker 的解决方案中提到的那样，我有一种反对使用联合作为强制转换的偏见。 - Ed.

Answer 5

compressedBytes.push_back(either.bytes.b[0]);
compressedBytes.push_back(either.bytes.b[1]);
compressedBytes.push_back(either.bytes.b[2]);
compressedBytes.push_back(either.bytes.b[3]);

有一种更聪明、更快的方法！让我们看看这段代码在做什么，以及如何改进它。

这段代码是将整数逐字节序列化。对于每个字节，它都会调用push_back函数，该函数会检查内部向量缓冲区中的可用空间。如果没有足够的空间容纳另一个字节，则会发生内存重新分配（提示：很慢！）。当然，重新分配不会经常发生（重新分配通常是通过将现有缓冲区加倍来完成的）。然后，新字节被复制并且内部大小增加了一个。

vector<> 标准要求其内部缓冲区是连续的。vector<> 还具有 operator& () 和 operator[] ()。

因此，这是你可以想到的最佳代码：

std::string invalidClsids("This is a test string");
std::vector<BYTE> compressedBytes;
DWORD invalidLength = (DWORD) invalidClsids.length();
compressedBytes.resize(sizeof(DWORD)); // You probably want to make this much larger, to avoid resizing later.
// compressedBytes is as large as the length we want to serialize.
BYTE* p = &compressedBytes[0]; // This is valid code and designed by the standard for such cases. p points to a buffer that is at least as large as a DWORD.
*((DWORD*)p) = invalidLength;  // Copy all bytes in one go!

可以使用&compressedBytes[0]语句一次完成上述转换，但速度不会更快。这样更易读。

注意！以这种方式进行序列化（甚至使用联合方法）是端点依赖的。也就是说，在Intel/AMD处理器上，最不重要的字节将首先出现，而在大端机器（PowerPC、Motorola...）上，最重要的字节将首先出现。如果您想保持中立，您必须使用数学方法（移位）。

- Ash

---

+1。是的，信不信由你，这比逐个从联合中加载字节更“非标准”，而且几乎肯定更快（但再次强调：要测量一切）。 - j_random_hacker

Answer 6

也许可以获得32位变量指针，将其转换为char指针并读取char，然后将指针加上+1并读取下一个char..只是理论:)我不知道它是否有效。

- wh1sp3r

Answer 7

你必须一个字节一个字节地做吗？有没有一种方法可以直接使用memcpy()将整个32位一次性复制到流中？如果你有要写入流的缓冲区的地址，那么你能否直接复制到该地址中？

- Furious Coder

---

不幸的是，是的。我将向量作为演示样本代码放置...但我正在通过它传递字节表示。 - Billy ONeal