Самый быстрый способ вычислить возможные значения unsigned int с N ненадежными битами? - PullRequest
Новая
       6

Самый быстрый способ вычислить возможные значения unsigned int с N ненадежными битами?

1 голос
/ 29 ноября 2011

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

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

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

A = 2323409845  
B = 1145324694

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

a=10001010011111000110101110110101

b=01000100010001000100010010010110

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

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

Ответы [ 3 ]

2 голосов
/ 29 ноября 2011

Нет гарантий, что это, безусловно, «самый быстрый», но это то, что я бы сделал. Сначала просеять фиксированные биты: 

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) (возможно, даже внутри существующего цикла) и «разложить» биты в требуемые позиции.

1 голос
/ 29 ноября 2011

Вы можете перебирать 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.

Также сравнительно просто распараллелить этот алгоритм с помощью целочисленных векторных инструкций.

1 голос
/ 29 ноября 2011

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

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, чтобы определить, следует ли включать каждый ненадежный бит, используя тот факт, что целые числа от 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]);
}
...