在 C、Ruby 或 PHP 中,如何获取位数组中所有设置位的偏移量。例如:
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}
最明显的解决方案是首先做一个反向的 Find first set 以了解长度,然后遍历位,保存偏移量/索引。然而,这似乎不是很聪明。像 FFSR 这样多次减法可能会更好。
我想出了这个。我已经使用二进制移位运算来确定是否存在二进制“1”或“0”。可能您可以使用此代码作为您的起点。
#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;
}
这是一个扩展版本,它也打印二进制表示:
#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;
}