1

给定一个无符号整数 A（32 位）和另一个无符号整数 B，其中 B 的二进制形式表示 A 的 10 个“最不可靠”位，扩展 A 的所有 1024 个潜在值的最快方法是什么？我希望在 C 中做到这一点。

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

例如，假设

A = 2323409845  
B = 1145324694

它们的二进制表示是：

a=10001010011111000110101110110101

b=01000100010001000100010010010110

B 表示 A 的 10 个最不可靠的位。因此，在 B 中设置为 1 的每个位表示 A 中的一个不可靠位。

我想计算通过切换 A 中的这 10 个位中的任何一个而创建的所有 1024 个可能值。

4

3 回答 3

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)（甚至可能在现有循环内）并将这些位“传播”到必要的位置。

于 2011-11-29T01:41:19.133 回答
1

这基本上遵循了 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;

屏蔽掉不可靠的位以确保对包含一些不可靠位的整数进行 ORing 并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来确定是否打开每个不可靠位，利用整数遍历最低 10 位的所有可能性这一0事实1023。

  return values;
}

最后，返回我们构建的数组。这是一个简短的主要内容，可用于使用您的问题中给出A的值来测试它：B

int main()
{
  int *values = getValues(0x8A7C6BB5, 0x44444496);
  int i;
  for(i = 0;i < 1024;i++)
    printf("%X\n", values[i]);
}
于 2011-11-29T05:18:13.957 回答
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 进行硬编码——它将完全基于b.

使用整数向量指令并行化这个算法也是一件相对简单的事情。

于 2011-11-29T07:27:48.827 回答