无论是按位还是64位范围内的整数的任何函数,它们是实现它的更快方法。我已经实现了。
/*
Find F(i)=abs(a(i)-b(i))
a(i)=number of 1's in even position
b(i)=number of 1's in odd position
for an integer i, where i fits in 64-bit
*/
//function calculate the above equation
//returns the answer
long long int F(long long int k)
{
//size of array is taken for 64-bit number
int a[64]={0},i,a,b;
long long int m;
m=k;
//convert long long int into binary
for(i=63;i>-1;i--)
{
if(m==1||m==0)
{
a[i]=m;
break; //exit the for loop
}
a[i]=m%2; //storing bit by bit
m/=2;
}
// initialized with a value of zero
a=0;
b=0;
//find first bit having 1
int f;
for(i=0;i<64;i++)
{
if(a[i]==1)
{
f=i;
break;
}
}
//calculating the number of 1's in even and odd positions
for(i=f;i<64;i++)
{
if(a[i]==1)
{
if((63-f)%2==0)
{
a++; //1's in even positions
}
else
{
b++; //1's in odd positions
}
}
}
//return the answer
return abs(a-b);
}
所以基本上我想做的是通过使用mod 2的简单方法来转换其二进制表示形式的整数。然后执行一个任务,以其二进制表示形式从左到右找到第一个1,并且指针位于第一个数。现在使用第一个1的索引来计算1的奇数和偶数位置的数量。最后返回总的偶数和奇数位置1的绝对差。
最佳答案
一种简单的方法:
#include <stdint.h>
int absdiffevenoddpopcount(uint64_t x) {
uint64_t a = x & 0x5555555555555555;
uint64_t b = x & ~0x5555555555555555;
while(a && b) {
a &= a - 1;
b &= b - 1;
}
x = a ? a : b;
int r = 0;
while(x) {
x &= x - 1;
r++;
}
return r;
}
无论如何,此页面收集了此类位hacks:https://graphics.stanford.edu/~seander/bithacks.html
同样,某些处理器具有特殊的指令,对于(位数)人口计数而言,它们可能会更快,通常编译器会将其作为内置函数提供给C。
关于c++ - 在二进制表示形式中,数字的偶数和奇数位置1的个数是多少?,我们在Stack Overflow上找到一个类似的问题:https://stackoverflow.com/questions/25814786/