Индексирование по Хэммингу
Предположим, у нас есть целое число bitsize n=4;
Проблема, которую я описываю, заключается в том, как вы будете индексировать число в позиции массива на основе веса Хэмминга и его значения, зная bitsize, Например, массив с 16 элементами для размера 4 будет / может выглядеть так:
|0|1|2|4|8|3|5|6|9|10|12|7|11|13|14|15|
Где элементы сгруппированы по весу Хэмминга (необходимо) и отсортированы по размеру (не обязательно). Сортировка не требуется, если вы можете взять, например, 3(0011), выполнить некоторые операции и получить индекс 5, 5(0101) -> 6 и т. Д.
Все комбинации n биты будут присутствовать и не будет дублирования. Например, размер бит 3 будет иметь массив:
|0|1|2|4|3|5|6|7|
Я бы предпочел иметь решение без петель. Или любые документы, которые обсуждают аналогичные решения. Или, наконец, просто выбросить любые идеи о том, как вы могли бы сделать это.
2 ответа
Обратите внимание, что вы можете перечислять числа (в порядке подсчета) с одинаковым весом Хэмминга, используя следующие функции:
int next(int n) { // get the next one with same # of bits set
int lo = n & -n; // lowest one bit
int lz = (n + lo) & ~n; // lowest zero bit above lo
n |= lz; // add lz to the set
n &= ~(lz - 1); // reset bits below lz
n |= (lz / lo / 2) - 1; // put back right number of bits at end
return n;
}
int prev(int n) { // get the prev one with same # of bits set
int y = ~n;
y &= -y; // lowest zero bit
n &= ~(y-1); // reset all bits below y
int z = n & -n; // lowest set bit
n &= ~z; // clear z bit
n |= (z - z / (2*y)); // add requried number of bits below z
return n;
}
Как пример, повторяющееся применение prev() на x = 5678:
0: 00000001011000101110 (5678)
1: 00000001011000101101 (5677)
2: 00000001011000101011 (5675)
3: 00000001011000100111 (5671)
4: 00000001011000011110 (5662)
5: 00000001011000011101 (5661)
6: 00000001011000011011 (5659)
.....
Следовательно, теоретически вы можете вычислить индекс числа путем повторного применения этого. Однако это может занять очень много времени. Лучшим подходом было бы "перепрыгнуть" через некоторые комбинации.
Есть 2 правила:
1. if the number starts with: ..XXX10..01..1 we can replace it by ..XXX0..01..1
adding corresponding number of combinations
2. if the number starts with: ..XXX1..10..0 again replace it by XXX0..01..1 with corresponding number of combinations
Следующий алгоритм вычисляет индекс числа среди чисел с одинаковым весом Хемминга (я не беспокоился о быстрой реализации биномиального):
#define LOG2(x) (__builtin_ffs(x)-1)
int C(int n, int k) { // simple implementation of binomial
int c = n - k;
if(k < c)
std::swap(k,c);
if(c == 0)
return 1;
if(k == n-1)
return n;
int b = k+1;
for(int i = k+2; i <= n; i++)
b = b*i;
for(int i = 2; i <= c; i++)
b = b / i;
return b;
}
int position_jumping(unsigned x) {
int index = 0;
while(1) {
if(x & 1) { // rule 1: x is of the form: ..XXX10..01..1
unsigned y = ~x;
unsigned lo = y & -y; // lowest zero bit
unsigned xz = x & ~(lo-1); // reset all bits below lo
unsigned lz = xz & -xz; // lowest one bit after lo
if(lz == 0) // we are in the first position!
return index;
int nn = LOG2(lz), kk = LOG2(lo)+1;
index += C(nn, kk); // C(n-1,k) where n = log lz and k = log lo + 1
x &= ~lz; //! clear lz bit
x |= lo; //! add lo
} else { // rule 2: x is of the form: ..XXX1..10..0
int lo = x & -x; // lowest set bit
int lz = (x + lo) & ~x; // lowest zero bit above lo
x &= ~(lz-1); // clear all bits below lz
int sh = lz / lo;
if(lz == 0) // special case meaning that lo is in the last position
sh=((1<<31) / lo)*2;
x |= sh-1;
int nn = LOG2(lz), kk = LOG2(sh);
if(nn == 0)
nn = 32;
index += C(nn, kk);
}
std::cout << "x: " << std::bitset<20>(x).to_string() << "; pos: " << index << "\n";
}
}
Например, учитывая число x = 5678, алгоритм вычислит свой индекс всего за 4 итерации:
x: 00000001011000100111; pos: 4
x: 00000001011000001111; pos: 9
x: 00000001010000011111; pos: 135
x: 00000001000000111111; pos: 345
x: 00000000000001111111; pos: 1137
Обратите внимание, что 1137 - это позиция 5678 в группе чисел с одинаковым весом Хэмминга. Следовательно, вам нужно будет сместить этот индекс соответственно, чтобы учесть все числа с меньшими весами Хэмминга
Вот концептуальная работа, только чтобы начать обсуждение.
Первый шаг сложнее всего - решается с помощью аппроксимации для расчета факториалов.
Есть еще яркие идеи?
#include <stdio.h>
#include <math.h>
//gamma function using Lanczos approximation formula
//output result in log base e
//use exp() to convert back
//has a nice side effect: can store large values in small [power of e] form
double logGamma(double x)
{
double tmp = (x-0.5) * log(x+4.5) - (x+4.5);
double ser = 1.0 + 76.18009173 / (x+0) - 86.50532033 / (x+1)
+ 24.01409822 / (x+2) - 1.231739516 / (x+3)
+ 0.00120858003 / (x+4) - 0.00000536382 / (x+5);
return tmp + log(ser * sqrt(2*M_PI) );
}
//result from logGamma() are actually (n-1)!
double combination(int n, int r)
{
return exp(logGamma(n+1)-( logGamma(r+1) + logGamma(n-r+1) ));
}
//primitive hamming weight counter
int hWeight(int x)
{
int count, y;
for (count=0, y=x; y; count++)
y &= y-1;
return count;
}
//-------------------------------------------------------------------------------------
//recursively find the previous group's "hamming weight member count" and sum them
int rCummGroupCount(int bitsize, int hw)
{
if (hw <= 0 || hw == bitsize)
return 1;
else
return round(combination(bitsize, hw)) + rCummGroupCount(bitsize,hw-1);
}
//-------------------------------------------------------------------------------------
int main(int argc, char* argv[])
{
int bitsize = 4, integer = 14;
int hw = hWeight(integer);
int groupStartIndex = rCummGroupCount(bitsize,hw-1);
printf("bitsize: %d\n", bitsize);
printf("integer: %d hamming weight: %d\n", integer, hw);
printf("group start index: %d\n", groupStartIndex);
}
выход:
размер: 4
целое число: 14 вес Хэмминга: 3
индекс начала группы: 11