How can I get the offsets of all set bits in a bitarray?

Question

In C, Ruby or PHP, how can I get the offsets of all set bits in an bitarray. E.g.:

Bitarray:  1 0 0 1 0
Offset:    5 4 3 2 1
Yields 2 and 5.

10001 => {1,5}
11 => {1,2}
1001001 => {1,4,7}

The most obvious solution would be to first do a reversed Find first set to know the length and then loop through the bits, saving the offset/index. However this does not seem very smart. Something like FFSR multiple times with subtraction might be better.

Answer 1

I came up with this. I've used binary shift operation to find out if there is binary "1" or "0". Probably you could use this code as your starting point.

#include <stdio.h>

int main()
{
    int number;
    int counter = 1;

    printf("Please input the number to get the offsets: ");
    scanf("%d", &number);

    printf("The required positions of ones: ");
    while ((number != 0))
    {
        if ((number % 2) != 0)
        {
            number = number >> 1;
            printf("%d", counter);
        }
        else 
        {
            number = number >> 1;
        }   

        counter++;  
    }

    return 0;
}

Here is an extended version that prints binary representation as well:

#include <stdio.h>
#include <strings.h>

char* rev(char* str);

int main()
{
    int number, temp;
    int counter = 1;
    char str[32] = "";

    printf("Please input the number to get the offsets: ");
    scanf("%d", &number);
    temp = number;

    printf("Binary representation: ");
    while ((temp != 0))
    {
        if ((temp % 2) != 0)
        {
            temp = temp >> 1;
            strncat(str, "1", 1);
        }
        else 
        {
            temp = temp >> 1;
            strncat(str, "0", 1);
        }       
    }
    printf("%s", rev(str));

    printf("\nThe required positions of ones: ");
    while ((number != 0))
    {
        if ((number % 2) != 0)
        {
            number = number >> 1;
            printf("%d", counter);
        }
        else 
        {
            number = number >> 1;
        }   

        counter++;  
    }

    getch();
    getch();
    return 0;
}    

char* rev(char* str)
{
  int end= strlen(str) - 1;
  int start = 0;

  while( start<end )
  {
    str[start] ^= str[end];
    str[end] ^=   str[start];
    str[start]^= str[end];

    ++start;
    --end;
  }

  return str;
}