基于汉明权重的索引 [英] Hamming weight based indexing

问题描述

假设我们有一个 bitsize n=4;
我所描述的问题是如何根据汉明权重及其值(知道 bitsize)将数字索引到数组位置.例如.一个包含 16 个元素的 bitsize 4 的数组将/可能如下所示:

Assume we have a integer of bitsize n=4;
The problem I am describing is how you would go about indexing a number to an array position based on the Hamming weight and its value knowing the bitsize. E.g. An array with 16 elements for bitsize 4 would/could look like this:

|0|1|2|4|8|3|5|6|9|10|12|7|11|13|14|15|

其中元素按其汉明权重(必要)分组并根据大小(非必要)排序.只要您可以进行排序，就没有必要进行排序.3(0011) 做一些操作，得到索引 5、5(0101) -> 6 等

Where elements are grouped by their Hamming weight(necessary) and sorted based on size(not necessary). Sorting is not necessary as long as you can take e.g. 3(0011) do some operations and get back index 5, 5(0101) -> 6 etc.

n 位的所有组合都将存在并且不会有重复.例如.3 的位大小将包含数组:

All combinations of n bits will be present and there will be no duplication. E.g. bitsize of 3 would have the array:

|0|1|2|4|3|5|6|7|

我最好有一个没有循环的解决方案.或任何讨论类似解决方案的论文.或者最后只是抛出关于如何去做的任何想法.

I would preferably have a solution without loops. Or any papers that discuss simillar solutions. Or finally just throw out any ides on how you could go about doing that.

推荐答案

请注意，您可以使用以下函数枚举具有相同汉明权重的数字(按计数顺序):

Note that you can enumerate numbers (in counting order) with the same hamming weight using the following functions:

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

例如，在 x = 5678 上重复应用 prev():

As an example, repititive application of prev() on x = 5678:

0: 00000001011000101110 (5678)
1: 00000001011000101101 (5677)
2: 00000001011000101011 (5675)
3: 00000001011000100111 (5671)
4: 00000001011000011110 (5662)
5: 00000001011000011101 (5661)
6: 00000001011000011011 (5659)
.....

因此理论上你可以通过重复应用来计算一个数字的索引这.但是，这可能需要很长时间.更好的方法是跳过"某些组合.

Hence theoretically you can compute the index of a number by repititive application of this. However this can take very long. The better approach would be to "jump" over some combinations.

有两条规则:

 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 

以下算法计算具有相同汉明权重的数字中的数字的索引(我不关心二项式的快速实现):

The following algorithm computes the index of a number among the numbers with the same Hamming weight (i did not bother about fast implementation of binomial):

#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 << "
";
  }
 }

例如，给定数字 x=5678该算法将在 4 次迭代中计算其索引:

For example, given the number x=5678 the algorithm will compute its index in just 4 iterations:

  x: 00000001011000100111; pos: 4
  x: 00000001011000001111; pos: 9
  x: 00000001010000011111; pos: 135
  x: 00000001000000111111; pos: 345
  x: 00000000000001111111; pos: 1137

请注意，1137 是 5678 在具有相同汉明权的数字组中的位置.因此，您必须相应地移动该指数以考虑具有较小汉明权重的所有数字

Note that 1137 is the position of 5678 within the group of numbers with the same Hamming weight. Hence you would have to shift this index accordingly to account for all the numbers with smaller Hamming weights

这篇关于基于汉明权重的索引的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！