lowbit(n)意思即为找出n在二进制表示下最后一位1即其后面的0所组成的数值,别的东西算法书上有,这里提出一个重要的公式
lowbit(n)=n&(~n+1)=n&(-n),这个有什么用啦,如果你知道了lowbit(n),那么你把n-lowbit(n)赋给n,在lowbit(n)就可以知道n二进制下倒数第二个1所表示的数值
以此类推,你就可求出n的每一个二进制下的1所表示的数值,这样再到表中查询也可以获得这些1分别在第几位
下面上一个重要的代码
int H[];
for(int i=;i<;i++) H[(1ll<<i)%]=i;//打表预处理,建立二进制数上每一个1代表的数值与其位数相对应
while(cin<<n)
{
while(n>)
{
cout<<H[(n&-n)%]<<"";
n-=n&-n;//遍历二进制下每一个数字1
}
cout<<endl;
}
下面在上一道题
思路大概是,每一个箱子的容量都可以表示成一个多项式f(n)=2^n+1,现在就是把铁块的总数拆成一些多项式的和,且这些多项式不能够重复。那么我们假设要用i个箱子,如果用x减去i后相当于把每个箱子的容量减1,那么剩下的都是由2^n组成的。所以剩下的数值如果转成二进制下的时候,能够有恰好有i个1,那么就说明是可以刚好用几个箱子把在这个铁块的值分了的
#include<stdio.h>
#include<iostream>
#include<string.h>
using namespace std;
int T,n;
int clac(int x)
{
int num=;
while(x)
{
num++;
x-=x&-x;
}
return num;
}
int main()
{
scanf("%d",&T);
while(T--)
{
scanf("%d",&n);
int flag=;
for(int i=;i<;i++)
{
if(n-i<) break;
if(clac(n-i)==i)
{
flag=;
break;
}
if(flag)
puts("YES");
else
puts("NO");
}
}
return ;
}