我的目标如下，
生成连续的值，使每个新的值从未生成，直到生成所有可能的值为止。此时，计数器再次开始相同的顺序。这里的要点是，所有可能的值是生成而无需重复的（直到周期耗尽）。序列是简单的0、1、2、3，还是其他顺序都没有关系。
例如，如果范围可以简单地用unsigned表示，则
void increment (unsigned &n) {++n;}
就足够了。但是，整数范围大于64位。例如，在一个地方，我需要生成256位序列。一个简单的实现就是以下内容，只是为了说明我要做的事情，
typedef std::array<uint64_t, 4> ctr_type;
static constexpr uint64_t max = ~((uint64_t) 0);
void increment (ctr_type &ctr)
{
if (ctr[0] < max) {++ctr[0]; return;}
if (ctr[1] < max) {++ctr[1]; return;}
if (ctr[2] < max) {++ctr[2]; return;}
if (ctr[3] < max) {++ctr[3]; return;}
ctr[0] = ctr[1] = ctr[2] = ctr[3] = 0;
}
因此，如果ctr从所有零开始，则首先将ctr[0]逐一增加，直到它达到max，然后再增加ctr[1]，依此类推。如果设置了所有256位，则将其重置为所有零，然后重新开始。
问题是，这种实现令人惊讶地慢。我当前的改进版本等于以下内容，
void increment (ctr_type &ctr)
{
std::size_t k = (!(~ctr[0])) + (!(~ctr[1])) + (!(~ctr[2])) + (!(~ctr[3]))
if (k < 4)
++ctr[k];
else
memset(ctr.data(), 0, 32);
}
如果仅使用上述increment函数来操纵计数器，并且始终以零开始，则ctr[k] == 0如果ctr[k - 1] == 0。因此，值 k将是小于最大值的第一个元素的索引。
我希望第一个会更快，因为分支错误预测只能在每2^64迭代中发生一次。第二个，尽管误导性误导性仅每2^256迭代一次，但不会有所作为。除了分支外，它需要四个位否定，四个布尔否定和三个添加。
的成本可能比第一个要高得多。然而，clang，gcc或Intel icpc生成第二个二进制文件，第二个都更快。
我的主要问题是，有人知道是否有任何更快的方法来实施这种计数器？只要算法生成256位的所有2^256组合，计数器是否从增加第一个整数开始或完全作为整数实现，都无关紧要。
。是什么使事情变得更复杂，我也需要非统一的增量。例如，每次计数器都会通过K递增K > 1，但几乎总是保持常数。我当前的实现类似于上述。
提供更多上下文，我正在使用这些计数器的一个地方是将它们用作AES-NI AESENC指令的输入。如此独特的128位整数（加载到__m128i中），经过指令的10个（或12或14，取决于密钥大小）之后，生成了独特的128-bits整数。如果我一次生成一个__m128i整数，那么increment的成本很小。但是，由于Aesenc的延迟很大，因此我通过块生成整数。例如，我可能有4个块ctr_type block[4]，初始化等于以下内容，
block[0]; // initialized to zero
block[1] = block[0]; increment(block[1]);
block[2] = block[1]; increment(block[2]);
block[3] = block[2]; increment(block[3]);
每次我需要新的输出时，每次increment block[i]乘4乘4，然后一次生成4个__m128i输出。通过交错指令，总的来说，我能够增加吞吐量，并在使用2个64位整数作为计数器和8个块时，将输出字节（CPB）的周期从6降低到0.9。但是，如果相反，使用4个32位整数作为计数器，则测量为每秒字节的吞吐量减少到一半。我知道，在X86-64上，在某些情况下，64位整数可能比32位更快。但是我没想到如此简单的增量操作会有如此大的不同。我已经仔细地对应用程序进行了基准测试，并且increment确实是程序降低了程序。由于将加载到__m128i中并将__m128i输出存储到可用的32位或64位整数中是通过对齐指针完成的，因此32位和64位版本之间的唯一区别是计数器的递增方式。我希望AES-NI期望将整数加载到__m128i之后，应主导性能。但是，当使用4或8个块时，显然不是这种情况。
因此，总而言之，我的主要问题是，如果有人知道一种改善上述反向实施的方法。
它不仅很慢，而且不可能。宇宙的总能量不足2^256位变化。这需要灰色计数器。
优化之前的下一件事是修复原始实现
void increment (ctr_type &ctr)
{
if (++ctr[0] != 0) return;
if (++ctr[1] != 0) return;
if (++ctr[2] != 0) return;
++ctr[3];
}
如果不允许每个ctr[i]溢出到零，则该周期仅为4*（2^32），例如0-9，19,29,39,49,...99，CC_29，199,299,...和1999,2999,3999,..., 9999。
作为对评论的答复 - 具有第一个溢出需要2^64迭代。慷慨大方，最高2^32迭代可以在一秒钟内进行，这意味着该程序应运行2^32秒以进行第一个执行。大约是136年。
编辑
如果真正想要的具有2^66个状态的原始实现，那么我建议将界面和功能更改为以下内容：
(*counter) += 1;
while (*counter == 0)
{
counter++; // Move to next word
if (counter > tail_of_array) {
counter = head_of_array;
memset(counter,0, 16);
break;
}
}
重点是，溢出仍然很少。几乎总是只有一个单词要增加。
如果您使用的是GCC或__int128的编译器，例如Clang或ICC
unsigned __int128 H = 0, L = 0;
L++;
if (L == 0) H++;
在没有__int128的系统上
std::array<uint64_t, 4> c[4]{};
c[0]++;
if (c[0] == 0)
{
c[1]++;
if (c[1] == 0)
{
c[2]++;
if (c[2] == 0)
{
c[3]++;
}
}
}
在内联装配中，使用随身携带标志进行此操作要容易得多。不幸的是，大多数高级语言都没有直接访问它的手段。有些编译器确实具有添加contrions的固有信息，例如gcc和 __builtin_addcll
无论如何，这是浪费时间，因为宇宙中的粒子总数仅为10 80 ，您甚至无法计算生活中的64位计数器
您的计数器版本都无法正确递增。实际上，您只是在计算UINT64_MAX 4次，然后再次以0重新开始，而不是计算到UINT256_MAX。从以下事实来看，您不必费心清除达到最大值的任何索引，直到所有这些索引达到最大值为止。如果您根据计数器达到所有位0的频率来衡量性能，那么这就是原因。因此，您的算法不会生成256位的所有组合，这是一个陈述的要求。
您提到"生成连续值，以便每个值在"
"之前，从未生成新的新产品要生成一组此类值，请查看线性一致生成器
序列x =（x*1 1）％（power_of_2），您考虑过，这只是顺序数字。
序列x =（x*13 137）％（2），这会生成具有可预测期（power_of_2-1）的唯一数字，而唯一数字看起来更"随机"，一种伪-随机的。您需要求助于任意的精度算术，以使其正常工作，也需要使用常数乘以乘法的所有欺骗。这将为您带来一个不错的开始方式。
您还抱怨您的简单代码是" slow"
在4.2 GHz频率，每个周期运行4个结构和使用AVX512矢量化，在64核计算机上，其程序的多线程版本除了增量以外什么都不做，您只能得到64x8x4*2 32 = 8796093022208每秒增量，即2 64 在25天内达到的增量。这篇文章很旧，您可能已经到达841632698362998292480，到现在为止，在这样的机器上运行这样的程序，您将在2年内光荣地达到168326539672596584960。
您还需要"直到生成所有可能的值" 。
您只能产生有限数量的值，这取决于您愿意为计算机供电的能量支付多少。正如其他回答中提到的，有128位或256位的数字，即使是世界上最富有的人，您也永远不会在这些条件发生的第一个情况之前缠绕：
- 摆脱钱
- 人类的结尾（没有人会得到您的软件的结果）
- 燃烧宇宙最后一个粒子的能量
多词添加可以通过使用三个模仿许多处理器上的三种添加说明的宏来轻松完成 Portable 时尚：
ADDcc添加了两个单词，如果他们未签名溢出，则将其设置为 ADDC添加了两个单词加携带（来自以前的添加）
ADDCcc添加两个单词加携带，如果他们的溢出未签名，则将其设置为
带有两个单词的多词加法使用最不重要的单词的ADDcc，然后是最重要的单词的ADCC。一个多字的添加，具有两个以上的单词序列序列ADDcc，ADDCcc，...，ADDC。MIPS体系结构是无条件代码的处理器体系结构，因此没有携带标志。下面显示的宏实现基本上遵循用于多词添加的MIPS处理器上使用的技术。
下面的ISO-C99代码显示了基于16位"单词"的32位计数器和64位计数器的操作。我选择数组作为基础数据结构，但例如，也可能使用struct。如果每个操作数仅包含几个单词，则使用struct的使用将更快，因为消除了数组索引的开销。一个人希望为每个"单词"使用最宽的整数类型，以获得最佳性能。在这个问题的示例中，可能是一个256位计数器，包括四个uint64_t组件。
#include <stdlib.h>
#include <stdio.h>
#include <stdint.h>
#define ADDCcc(a,b,cy,t0,t1)
(t0=(b)+cy, t1=(a), cy=t0<cy, t0=t0+t1, t1=t0<t1, cy=cy+t1, t0=t0)
#define ADDcc(a,b,cy,t0,t1)
(t0=(b), t1=(a), t0=t0+t1, cy=t0<t1, t0=t0)
#define ADDC(a,b,cy,t0,t1)
(t0=(b)+cy, t1=(a), t0+t1)
typedef uint16_t T;
/* increment a multi-word counter comprising n words */
void inc_array (T *counter, const T *increment, int n)
{
T cy, t0, t1;
counter [0] = ADDcc (counter [0], increment [0], cy, t0, t1);
for (int i = 1; i < (n - 1); i++) {
counter [i] = ADDCcc (counter [i], increment [i], cy, t0, t1);
}
counter [n-1] = ADDC (counter [n-1], increment [n-1], cy, t0, t1);
}
#define INCREMENT (10)
#define UINT32_ARRAY_LEN (2)
#define UINT64_ARRAY_LEN (4)
int main (void)
{
uint32_t count32 = 0, incr32 = INCREMENT;
T count_arr2 [UINT32_ARRAY_LEN] = {0};
T incr_arr2 [UINT32_ARRAY_LEN] = {INCREMENT};
do {
count32 = count32 + incr32;
inc_array (count_arr2, incr_arr2, UINT32_ARRAY_LEN);
} while (count32 < (0U - INCREMENT - 1));
printf ("count32 = %08x arr_count = %08xn",
count32, (((uint32_t)count_arr2 [1] << 16) +
((uint32_t)count_arr2 [0] << 0)));
uint64_t count64 = 0, incr64 = INCREMENT;
T count_arr4 [UINT64_ARRAY_LEN] = {0};
T incr_arr4 [UINT64_ARRAY_LEN] = {INCREMENT};
do {
count64 = count64 + incr64;
inc_array (count_arr4, incr_arr4, UINT64_ARRAY_LEN);
} while (count64 < 0xa987654321ULL);
printf ("count64 = %016llx arr_count = %016llxn",
count64, (((uint64_t)count_arr4 [3] << 48) +
((uint64_t)count_arr4 [2] << 32) +
((uint64_t)count_arr4 [1] << 16) +
((uint64_t)count_arr4 [0] << 0)));
return EXIT_SUCCESS;
}
count32 = fffffffa arr_count = fffffffa
count64 = 000000a987654326 arr_count = 000000a987654326
基于内联装配或专有扩展的不可支配的代码，可以执行大约两到三倍的速度。