UVa 11121 Base -2 (数论 -2进制补足思想)

本文主要是介绍UVa 11121 Base -2 (数论 -2进制补足思想)，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

11121 - 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

（参考《Hacker's Delight》）

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 (b _i) , writen right-to-left. Each of which is either 0 or 1 (no negative digits!), and the following equality must hold.

n = b₀ + b₁(-2) + b₂(-2)² + b₃(-2)³ + ...

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

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;
}

这篇关于UVa 11121 Base -2 (数论 -2进制补足思想)的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！