無信頼できないビットを使用して、署名されていないINTの可能な値を計算する最速の方法？

Question

署名されていないINT A（32ビット）と別の署名されていないINT Bを考えると、Bのバイナリ形式はAの10の「最も信頼性の低い」ビットを示します。私はCでこれをやろうとしています

たとえば、UINT Bは、バイナリ形式（10の信頼性の低いビット）に常に10 1と22 0を持つことが保証されています。

たとえば、言っておきましょう

A = 2323409845  
B = 1145324694

彼らのバイナリ表現は次のとおりです。

a=10001010011111000110101110110101

b=01000100010001000100010010010110

bは、Aの10の最も信頼性の低いビットを示します。したがって、bに1に設定されている各ビットは、Aで信頼性の低いビットを示します。

Aの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]);
}