uva 11121 - Base -2（负进制转换）

题目连接：uva 11121 - Base -2

题目大意：给出一个十进制的数，将这个数转换成-2进制的数。

解题思路：进制转化是一种很简单的题型，可是对于负数的进制来说我就很陌生了，研究了蛮久的，这里分享一下。

首先要了解如何将一个-2进制的数转换成十进制数，历7对应的-2进制数即为11011；

1 * (-2) ^ 4 + 1 * (-2) ^ 3 + 0 * (-2) ^ 2 + 1 * (-2) ^ 1 + 1 * (-2) ^ 0 = 16 - 8 + 0 - 2 + 1 = 7(和2进制转10进制是一个道理）

其次n / (-2) = - (n / 2) ；当n ≥ 0时，n % (-2) = n % 2， 当n < 0时， n % (-2) = - (|n| % 2);这样写出来方便理解。

最后就是进制的转换了，10进制转2进制的大家都会，就是每次模2，取整。其实转-2进制也是一样的，每次模-2，取整，可是这里就涉及到符号的问题。

例： 以7为例子

a)7%(-2)=1, 7/(-2)=-3 --------- -3 * (-2) ^ 1 + 1 * (-2) ^ 0 = 6 + 1 = 7 ;-3、1

b)-3% (-2) = -1 -3/(-2) = 1---------- -1 *(-2) ^ 2 + (-1) * (-2) ^ 1 + 1 * (-2) ^ 0 = 4 + 2 + 1 = 7;1、-1、1

可是这里出现了-1，-1不能在这里面出现，所以只能尝试将等价的数值转移到高位，或是低位，可是转移到低位是要进位的，所以使不可取的，只能转向高位；现在假设当前为-1的位为当前位，那当当前位的高位增加1时，对应则是当前位的数值增加2，若要保持数值的不变，则要减去增加的数值，若减在高位上则没有改变，所以只能减在当前位上。

即 2、-1 - （-2）、1 （会出现模-2小于0的肯定是奇数为，奇数位要注意符号为负） 2 、 1、1

2 * (-2) ^ 2 + 1 * (-2) ^ 1 + 0 * (-2) ^ 0 = 8 - 2 + 1 = 7

重复执行a、b，直到取整为0，就可以得到答案。

归纳：其他的-bas进制，也是以同样的方式进行进制转换，只是对应的负数a，a + bas。

#include <stdio.h>#include <string.h>#include <math.h>const int tmp = -2;void base() {int n, i, num[105];memset(num, 0, sizeof(num));scanf("%d", &n);for (i = 0; n; i++) {num[i] = n % tmp;n = n / tmp;if (num[i] == -1) {num[i] = 1, n++;}}while (--i > 0) {printf("%d", num[i]);}printf("%d\n",  num[0]);}int main() {int cas, ti = 1;scanf("%d", &cas);while (cas--) {printf("Case #%d: ", ti++);base();}return 0;}