У меня есть 64-битное число (но используются только 42 младших разряда), и мне нужно вычислить сумму 4 битов в n, n+m, n+m*2 и n+m*3 (примечание: все, что может дать сумму> 4, недопустимо) для некоторого фиксированного m и каждого значения n, которое помещает все биты в число
в качестве примера, используя m=3 и учитывая 16-битное число
0010 1011 0110 0001
Мне нужно вычислить
2, 3, 1, 2, 3, 0, 3
У кого-нибудь есть (крутые) идеи о том, как это сделать? Я в порядке с немного вертеться.
В настоящее время моя мысль состоит в том, чтобы сделать сдвинутые по битам копии входных данных для выравнивания суммируемых значений, а затем построить логическое дерево для суммирования 4x 1 бит.
v1 = In;
v2 = In<<3;
v3 = In<<6;
v4 = In<<9;
a1 = v1 ^ v2;
a2 = v1 & v2;
b1 = v3 ^ v4;
b2 = v3 & v4;
c2 = a1 & b1;
d2 = a2 ^ b2;
o1 = a1 ^ b1;
o2 = c2 ^ d2;
o4 = a2 & b2;
Это в конечном итоге приводит к разбросу битов результата по 3 разным целым числам, ну да ладно.
редактировать: как это происходит, мне нужна гистограмма сумм, поэтому счетчик битов из o4, o2&o1, o2 и o1 дает мне то, что я хочу.
второе решение использует идеальную хеш-функцию
arr = [0, 1, 1, 2, 1, 2, 2, 3, 1, 2, 2, 3, 2, 3, 3, 4];
for(int i = 0; i < N; i++)
{
out[i] = arr[(In & 0b1001001001) % 30];
In >>= 1;
}
Это работает, отмечая, что 4 выбранных бита могут принимать только 16 шаблонов и что (путем догадки и проверки) они могут быть хэшированы в 0-15 с использованием мода 30. Оттуда таблица вычисленных значений дает необходимую сумму , Поскольку это происходит только 3 из 4 шагов, мне нужно работать таким образом.
приписка
Правильный козырь быстро. Быстрые козыри ясно. Я ожидаю, что пробежу миллионы раз.