用n个不可靠的位计算未符号int的可能值的最快方法？

Question

给定未签名的int a（32位）和另一个未签名的int b，其中b的二进制符号表示A的10个“最不可靠”位，什么是扩展A的所有1024个潜在值的最快方法？我想在C中这样做。

例如，uint B保证在其二进制形式（10最不可靠的位）中始终具有10 1和22 0。

例如，假设

A = 2323409845  
B = 1145324694

他们的二进制表示：

a=10001010011111000110101110110101

b=01000100010001000100010010010110

b表示A的10位最低可靠位。因此，每个位置为B中的位表示A中的位。

我想计算通过在A中切换10位的所有10位创建的所有1024个可能的值。

Answer 1

您可以通过1024个不同的位置进行迭代 b 像这样：

unsigned long b = 1145324694;
unsigned long c;

c = 0;
do {
    printf("%#.8lx\n", c & b);
    c = (c | ~b) + 1;
} while (c);

使用这些修改 a 您可以使用XOR：

unsigned long a = 2323409845;
unsigned long b = 1145324694;
unsigned long c;

c = 0;
do {
    printf("%#.8lx\n", a ^ (c & b));
    c = (c | ~b) + 1;
} while (c);

此方法具有您不需要预先计算任何表的优点，并且您不需要编码1024-它将完全基于1位的数量循环 b.

使用整数向量指令并行化该算法也是相对简单的问题。

Answer 2

不能保证这是“最快的”，但这就是我要做的。首先，筛分固定位：

uint32_t const reliable_mask = ~B;
uint32_t const reliable_value = A & reliable_mask;

现在，我将预处理1024个不可靠位的可能值：

uint32_t const unreliables[1024] = /* ... */

最后，我只是或所有这些：

for (size_t i = 0; i != 1024; ++i)
{
   uint32_t const val = reliable_value | unreliables[i];
}

为了获得不可靠的位，您可以旋转 [0, 1024) （甚至可能在现有循环内）并将其“散布”到必要位置。

Answer 3

这实际上是Kerrek使用的技术，但充实了困难的部分：

int* getValues(int value, int unreliable_bits)
{
  int unreliables[10];
  int *values = malloc(1024 * sizeof(int));
  int i = 0;
  int mask;

功能定义和一些可变声明。这里， value 是你的 A 和 unreliable_bits 是你的 B.

  value &= ~unreliable_bits;

掩盖不可靠的位，以确保一个整数包含一些不可靠的位和 value 将产生我们想要的。

  for(mask = 1;i < 10;mask <<= 1)
  {
    if(mask & unreliable_bits)
      unreliables[i++] = mask;
  }

在这里，我们将每个不可靠的位用于以后使用的个人int。

  for(i = 0;i < 1024;i++)
  {
    int some_unreliables = 0;
    int j;
    for(j = 0;j < 10;j++)
    {   
      if(i & (1 << j)) 
        some_unreliables |= unreliables[j];
    }   
    values[i] = value | some_unreliables;
  }

功能的肉。外循环在我们想要的每个输出上。然后，我们使用循环变量的最低10位 i 确定是否打开每个不可靠的位，使用整数 0 至 1023 经历最低10位的所有可能性。

  return values;
}

最后，返回我们构建的数组。这是一个简短的主，可用于用值进行测试 A 和 B 在您的问题中给出：

int main()
{
  int *values = getValues(0x8A7C6BB5, 0x44444496);
  int i;
  for(i = 0;i < 1024;i++)
    printf("%X\n", values[i]);
}