Convert an Int to an array of Ints indicating positions of bits in C [closed]

Closed. This question needs details or clarity. It is not currently accepting answers. 开发者_Python百科

---

Want to improve this question? Add details and clarify the problem by editing this post.

Closed 9 years ago.

Improve this question

So if I had an int, say 0000100101101001, it should be turned to an array like {0,3,5,6,8,11}. I am using a convoluted system using clz (count leading zeros) and bit masks to do it now, but something better should exist I suspect.

I'm on an i7 and using gcc, use of SIMD/SSE builtins considered a good thing.

---

How about this (should work for unsigned integers):

while (x) {
    /* Store rightmost 1-bit in your array. */
    arr[i++] = x & (-x);

    /* Turn off rightmost 1-bit. */
    x = x & (x - 1);
}

I suspect there are better ways to do it.

---

You can do something like:

void bit2arr(int *result, size_t len, unsigned val) {
  int count = 0;
  while (val && len) {
    // add bit to array if needed
    if (val & 1) {
      *result++ = count;
      --len; // Don't overflow output
    }

    // Increment counter regardless
    ++count;

    // remove bit and bitshift
    val &= (~0 ^ 1);
    val >>= 1;
  }
}

To take one bit at a time and save the position to an array if it's non-zero.

I used it with:

#include <stdio.h>
#include <string.h>

static const unsigned val = 2409;

int main() {
  int result[32];
  memset(result, 0, sizeof(result));

  bit2arr(result, 32, val);

  for (int i = 0; i < 32; ++i) {
    printf("%s%d", i ? ", " : "", result[i]);
  }
  printf("\n");
  return 0;
}

Which gave:

0, 3, 5, 6, 8, 11, 0...

It should be easy enough to make the function return the size of the resultant array.

---

size_t bit2arr(char *result, unsigned val) {
size_t pos, cnt;

for (pos=cnt=0; val; val >>=1, pos++) {
   if (val & 1) result [cnt++] = pos;
   }

return cnt; /* number of 1 bits := number of valid positions in result[] */
}