UVa 11121 Base -2 （数论 & -2进制 & 补足思想）

UVa 11121 Base -2 （数论 & -2进制 & 补足思想）2014-07-29 csdn博客 synapse711121 - Base -2
Time limit: 3.000 seconds
http://uva.onlinejudge.org/index.php？option=com_onlinejudge&Itemid=8&category=115&page=show_problem&problem=2062

The creator of the universe works in mysterious ways. But
he uses a base ten counting system and likes round numbers.

Scott Adams

Everyone knows about base-2 （binary） integers and base-10 （decimal） integers, but what about base -2？ An integer n written in base -2 is a sequence of digits （bi）, writen right-to-left. Each of which is either 0 or 1 （no negative digits！）, and the following equality must hold.

n = b0 + b1（-2） + b2（-2）2 + b3（-2）3 + ...

The cool thing is that every integer （including the negative ones） has a unique base--2 representation, with no minus sign required. Your task is to find this representation.

Input
The first line of input gives the number of cases, N （at most 10000）. N test cases follow. Each one is a line containing a decimal integer in the range from -1,000,000,000 to 1,000,000,000.

Output
For each test case, output one line containing "Case #x:" followed by the same integer, written in base -2 with no leading zeros.
Sample Input Output for Sample Input

-2

0 Case #1: 1

Case #2: 11011

Case #3: 10

Case #4: 0

思路：

一种思路是：不妨拿我们在算二进制中做的那样，只做下小修改就行。

另一种思路有点巧妙：如果二进制对应那一位p是1，则将n+=1<<（p+1），最终n化为了正规的二进制。（速度更快）

way 1：

/*0.045s*/#include <cstdio>int array[40];int main（）{int T, n, i, j, CASE =0 0;scanf（"%d", &T）;while （T--）{scanf（"%d", &n）;printf（"Case #%d: ", ++CASE）;if （n == 0）puts（"0"）;else{i = 0;while （n）{array[i++] = n & 1;n = （n - （n & 1）） / -2;}for （j = i - 1; j >= 0; j--）printf（"%d", array[j]）;putchar（10）;}}}

way 2：

/*0.019s*/#include<cstdio>#include<cstdlib>typedef long long ll;const ll one = 1;int main（）{ll n, bit;///非常不巧需要1<<32，所以用long longint T, cas = 0, p;scanf（"%d", &T）;while （T--）{scanf（"%lld", &n）;printf（"Case #%d: ", ++cas）;if （n == 0）{puts（"0"）;continue;}///n转化成2进制意义下的np = （n > 0 ？ 1 : 0）;///起始n = abs（n）;bit = one << p;while （p <= 32）{if （bit & n）n += one << （p + 1）;///修正p += 2;bit = one << p;}///去前导零for （bit = one << 31; （bit & n） == 0; bit >>= 1）;///求二进制while （bit）{putchar（bit & n ？ "1" : "0"）;bit >>= 1;}putchar（10）;}return 0;}