一个如下的内存分配方法，初始分配2^n条记录，然后按倍增的方式。 当达到2^(n+m)时，改为每次分配2^(n+m)的方式进行。 在这种分配方法下，给定记录编号，算出记录所属的内存块及其在内存块中的偏移。

CalculatePositionByIndex.cc

#include <iostream>
#include <iomanip>

/*
一个如下的内存分配方法，初始分配2^n条记录，然后按倍增的方式。
当达到2^(n+m)时，改为每次分配2^(n+m)的方式进行。

在这种分配方法下，给定记录编号，算出记录所属的内存块及其在内存块中的偏移。

 */
unsigned int NextPowerOf2(unsigned int n)
{
  n--;
  n |= n >> 1;
  n |= n >> 2;
  n |= n >> 4;
  n |= n >> 8;
  n |= n >> 16;
  n++;
  return n;
}

int GetMSB(int i) {
  int c = 0;
  while (i) {
    i >>= 1;
    c++;
  }
  return c;
}

int main(int argc, char **argv) {
  for (int i = 0; i < 64; i++) {
    int pos;
    int n = 1;
    int m = 4;
    int b = GetMSB(NextPowerOf2((i >> (n - 1)) + 3)) - 3;
    if (b < m) {
      std::cout << i << "," << b << "," <<  i - (((1 << b) - 1) << n) << std::endl;
    } else {
      int maxb = (((1 << m) - 1) << n);
      if (m == 0) n++;
      std::cout << i << "," << (i - maxb) / (1 << (m + n - 1)) << "," << (i - maxb) % (1 << (m + n - 1))  << std::endl;
    }
  }
  return 0;
}