Самый быстрый способ рассчитать возможные значения без знака Int с n ненадежными битами?

Question

Учитывая беспигнированный int a (32 -битный) и еще один безписанный int b, где бинарная форма B обозначает 10 «наименьших надежных» битов A, какой самый быстрый способ расширить все 1024 потенциальных значений A? Я хочу сделать это в C.

Например, Uint B гарантированно всегда будет иметь 10 1 и 22 0 в его двоичной форме (10 наименее надежные биты).

Например, скажем

A = 2323409845  
B = 1145324694

Их бинарные представления:

a=10001010011111000110101110110101

b=01000100010001000100010010010110

B обозначает 10 наименее надежные биты A. Таким образом, каждый бит, который установлен на 1 в B, обозначает ненадежный бит в A.

Я хотел бы рассчитать все 1024 возможных значений, созданных путем переключения любых из этих 10 бит по А.

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

Это следует, по сути, технику, используемой Керреком, но выявляет сложные части:

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