Peel the ones, then 2^k mod 37

A nonnegative int $n$. How many $1$s does it have?

The brute loop always works. Smarter: take lowbit, that is the first $1$, count it, then n -= lowbit and repeat until $n = 0$.

int population(int n) {
  int p = 0;
  while (n > 0) {
    n -= n & -n;
    ++p;
  }
  return p;
}

Side note: C++ already has std::popcount.

Now I want the positions. Same peel. The remaining job: given a lowbit $m = 2^{k}$, recover $k$.

A fat table

Hash it. Build an array long enough that index $2^{k}$ stores $k$. I used $2^{20}$, which does not even cover every int, and every slot that is not a power of two is wasted.

std::array<int, (1 << 20) + 1> create_power_to_exponent_map_naive() {
  std::array<int, (1 << 20) + 1> power_to_exponent_map = {};
  for (int k = 0; k <= 20; ++k) {
    power_to_exponent_map[1 << k] = k;
  }
  return power_to_exponent_map;
}

Compress with 37

The claim is that the residues $2^{0}, 2^{1}, \ldots, 2^{35}$ are pairwise distinct modulo $37$:

So a table of length $37$ can store $k$ at index $2^{k} \bmod 37$. I only need $k \le 30$ for a 32-bit int, but the residues still live in $\{0, 1, \ldots, 36\}$, so the array stays size $37$.

std::array<int, 37> create_power_to_exponent_map() {
  std::array<int, 37> power_to_exponent_map = {};
  for (int k = 0; k <= 30; ++k) {
    power_to_exponent_map[static_cast<std::size_t>((1 << k) % 37)] = k;
  }
  return power_to_exponent_map;
}

const auto kPowerToExponentMap = create_power_to_exponent_map();

std::vector<int> find_bit_positions(int n) {
  std::vector<int> positions;
  while (n > 0) {
    int lowbit = n & (-n);
    int position = kPowerToExponentMap[static_cast<size_t>(lowbit % 37)];
    positions.push_back(position);
    n -= lowbit;
  }
  return positions;
}

Take n = 0b1110110. Peel: $2^{1}$, $2^{2}$, $2^{4}$, $2^{5}$, $2^{6}$. Already $2^{6} = 64 \equiv 27 \pmod{37}$, so the table is doing real compression — slot $27$ holds $6$.

Why no collisions

If $2^{i} \equiv 2^{j} \pmod{37}$ with $0 \le i < j$, then since $\gcd(2, 37) = 1$ we may cancel $2^{i}$ and obtain $2^{j-i} \equiv 1 \pmod{37}$. A collision is exactly when some positive exponent smaller than $36$ already yields $1$. That is the language of multiplicative order.

The coprimality hypothesis is not decoration: it guarantees that some power of $a$ is congruent to $1$, so a least such positive exponent exists. Note that $a^{0} \equiv 1 \pmod{n}$ is trivial and does not count — zero is not a positive integer.

Since $37$ is prime and $\gcd(2, 37) = 1$, Fermat’s little theorem applies.

Taking $a = 2$ and $p = 37$, the second form gives

So $\operatorname{ord}_{37}(2)$ exists, and it is at most $36$. Fermat does not say that $36$ is the least such exponent. If some $m < 36$ already satisfied $2^{m} \equiv 1 \pmod{37}$, the powers would collide. To pin the order down we need the following.

Apply this with $a = 2$ and $n = 37$. Fermat already gave $2^{36} \equiv 1 \pmod{37}$, so $\operatorname{ord}_{37}(2) \mid 36$. The positive divisors of $36$ are $1, 2, 3, 4, 6, 9, 12, 18, 36$. It remains to check that none of the proper ones works:

None of these is $1$. Therefore $\operatorname{ord}_{37}(2) = 36$, and

No collisions.