用负二进制表示一个数，如21=1+4+16，当num>21时最大用64-32表示32，否则最大用16即可，当num=31时，31-32=-1，在转入处理负数的函数中
1 /*0.003s*/ 2 #include <iostream> 3 #include<cstdio> 4 #include<cstring> 5 #include<cmath> 6 using namespace std; 7 8 int num,T,cas=1; 9 char ans[40]; 10 11 void neg(int num); 12 13 void not_neg(int num)//处理正数 14 { 15 long long m=1,e=2,n=0; 16 while(num>m) 17 { 18 m=(m<<2)+1;//m=2^0+2^2+...+2^2n 19 e<<=2;//2^2n+1 20 n+=2; 21 } 22 while(num>1) 23 { 24 m>>=2;e>>=2; 25 if(num>m+e)//num>2^0+2^2+...+2^2(n-1)+2^2n-1时用2^2n 26 { 27 ans[n--]='1'; 28 n--; 29 num-=e<<1; 30 } 31 else if(num>m)//否则用-2^2n-1 + 2^2n 32 { 33 ans[n--]='1'; 34 ans[n--]='1'; 35 num-=e; 36 } 37 else n-=2; 38 } 39 if(num<0) neg(num);//正负交替 40 else if(num==1) ans[0]='1'; 41 } 42 43 void neg(int num)//处理负数 44 { 45 num=-num;//转化为正数，类似正数处理 46 long long m=2,e=4,n=1; 47 while(num>m) 48 { 49 m=(m<<2)+2; 50 e<<=2; 51 n+=2; 52 } 53 while(num>2) 54 { 55 m>>=2;e>>=2; 56 if(num>m+e) 57 { 58 ans[n--]='1'; 59 n--; 60 num-=e<<1; 61 } 62 else if(num>m) 63 { 64 ans[n--]='1'; 65 ans[n--]='1'; 66 num-=e; 67 } 68 else n-=2; 69 } 70 if(num<0) not_neg(-num);//正负交替 71 else if(num==2) ans[1]='1'; 72 else if(num==1) ans[0]=ans[1]='1'; 73 } 74 int main() 75 { 76 scanf("%d",&T); 77 while(T--) 78 { 79 scanf("%d",&num); 80 printf("Case #%d: ",cas++); 81 memset(ans,'0',sizeof(ans));//初始化所有字符为‘0’，之后只需置1即可 82 num>0?not_neg(num):neg(num); 83 int i=39; 84 while(ans[i]=='0'&&i>0) i--;//i>0至少留一位，全部为0时也符合 85 /* num=0; 86 for(int j=0;j<=i;j++) 87 j&1?num-=(1<<j)*(ans[j]-'0'):num+=(1<<j)*(ans[j]-'0'); 88 printf("num=%d ",num);//检验 89 */ 90 for(;i>=0;i--) 91 putchar(ans[i]); 92 printf(" "); 93 } 94 return 0; 95 }
n%(-2)如果等于-1,则商+1(n+2^(i+1)),a[i]=1,否则不变
1 #include <cstdio> 2 #include <queue> 3 #include <cstring> 4 #include <iostream> 5 #include <cstdlib> 6 #include <algorithm> 7 #include <vector> 8 #include <map> 9 #include <set> 10 #include <ctime> 11 #include <cmath> 12 #include <cctype> 13 #define MAX 100000 14 #define LL long long 15 using namespace std; 16 int n,cas=1,T; 17 char a[40]; 18 int main() 19 { 20 //freopen("/home/user/桌面/in","r",stdin); 21 scanf("%d",&T); 22 while(T--) 23 { 24 scanf("%d",&n); 25 int i=-1; 26 a[0]='0'; 27 while(n) 28 { 29 a[++i]=n%(-2); 30 n/=-2; 31 if(a[i]<0) 32 { 33 n++; 34 a[i]=1; 35 } 36 a[i]+='0'; 37 } 38 printf("Case #%d: ",cas++); 39 i=max(i,0); 40 for(;i>=0;i--) printf("%c",a[i]); 41 printf(" "); 42 } 43 //printf("time=%.3lf",(double)clock()/CLOCKS_PER_SEC); 44 return 0; 45 }