汉明重量索引

Question

汉明重量索引

13

假设我们有一个整数 bitsize n=4;
我描述的问题是，如何根据 Hamming 权重和其值以及已知的 bitsize，将数字索引到数组位置。例如，对于 bitsize 为 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|

我希望有一个不需要循环的解决方案。或者任何讨论相似方案的文献。最后，只需提出任何关于如何实现它的想法。

- 1-----1

2

我不确定我理解你想要实现什么。在CUDA中，您可以使用__popc()内置函数确定整数的汉明重量，该函数在较新的GPU上实现为快速硬件指令，并在其他情况下映射到有效的软件仿真。然后，您可以使用__popc()的输出来索引表示查找表的数组。 - njuffa

现在的问题是，我正在随机访问内存，也就是到处拉取内存。我想按照它们的popcount将内存分组，因为我只为每个内核和以下内核请求特定popcount (_popc(x) <= z) 的内存。因此，通过拥有一个函数f，该函数从popcount和值转换为数组中的索引，我将不会受到随机访问的惩罚。您描述的查找表还需要一个函数，该函数接受值并返回索引，这是相同的问题。我正在使用大型数组，例如2^n，其中n>20，因此空间受限。 - 1-----1

转换 n <-> index 需要快速吗？ - Daniel Fischer

越快越好，但“慢”也可以，它应该避免任何内存操作并进行算术运算。我认为我有一个解决方案，但需要先吃饭。 - 1-----1

嗯，我的想法是：1.给定宽度的整数数量少于位设置。2.计算有多少比其小但具有相同位数的数字存在。3.相加。时间复杂度为O((log width)^a)，其中a为1或2，记不清了。可能对您的目的来说太慢了。 - Daniel Fischer

我想到了，只是第一步我不知道如何计算。它是 zigma(i=1,b-1)pick(i,n)，其中 b == 当前位数，n == 最大位数。如何用 O(~1) 的操作来实现呢？ - 1-----1

2个回答

1

这是一个概念性的工作，只是为了开始讨论。
第一步是最难的-使用近似计算阶乘来解决问题。
还有更好的想法吗？

Ideone链接

#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

- cctan

看起来不错，但有没有一种方法可以迭代rCummGroupCount？ Lanczos逼近公式有多精确？ - 1-----1

1

@ks6g10 需要一些时间来研究精度问题和递归的rCummGroupCount。不过，使用查找表来计算阶乘会更简单，你可以考虑一下这个方法。 - cctan

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- user1545642 · Accepted Answer

请注意，您可以使用以下函数枚举具有相同海明重量的数字（按计数顺序）：

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()：

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

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

有两个规则：

 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在具有相同汉明重量的数字组中的位置。因此，您需要相应地移动此索引，以考虑所有具有较小汉明重量的数字。