海明重量基于索引 [英] Hamming weight based indexing

问题描述

假设我们有 bitsize N = 4的整数; 结果
我所描述的问题是，你将如何去索引一个数字，根据汉明权值，并将其值数组位置知道 bitsize 。例如。
与bitsize 4月16日元素的数组会/可能是这样的：

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 位的所有组合将是present会有没有重复。例如。
3 的bitsize将有数组：

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|

我想preferably有没有环路的解决方案。
或者说，讨论解决方案，呈三角任何文件。
终于还是刚刚抛出任何的IDE你怎么会去这样做。

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

作为一个例子，$ P $光伏repititive应用（）在X = 5678：

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)
.....

因此​​理论上可以通过repititive应用计算一个数的索引
这个。然而，这可能需要很长时间。更好的办法是跳过一些组合。

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.

有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 

下面的算法计算用的相同的汉明权重（我没有理会快速实现二项式）的数量中的一些指标：

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 << "\n";
  }
 }

例如，给定数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的组号与在相同汉明权重中的位置。因此，你必须该指数较小Hamming重​​量相应做出调整，考虑到所有的数字

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屋！