#UVa：11121－Base -2

這題可以先將輸入的數字的絕對值換成2進位制，例如：7 => 111、-7 => 111。再來從小到大看看它由哪些2的幾次方組成，如果該次方與輸入的數字同號時，換成base(-2)的時候，也一樣會有該次方；如果該次方與輸入的數字不同號時，換成base(-2)的時候，就需要該次方與該次方+1兩個所組成。

例如：7 = 111 有2^0、2^1、2^2。

• 2^0 -> (-2)^0 直接換過來即可。
• 2^1 -> ((-2)^1 + (-2)^2) 該次方+該次方的下一個次方即可組成。
• 2^2 -> (-2)^2 直接換過來即可。

加起來會有 1個(-2)^0，1個(-2)^1，2個(-2)^2，2個(-2)^2要進位，但是對於base(-2)又得再利用(-2)^3+(-2)^4才能組起來，所以答案就會是 11011 。

P.S. 進位的地方用or運算是因為當你發覺要有2個(-2)^奇數次方(假設a)時(以N為正數為例，反之則反)，根據上述做法要用2個(-2)^(a+1)次方和2個(-2)^a，2個(-2)^(a+1)和2個(-2)^a = 1個(-2)^(a+1) + 0個(-2)^a，而(-2)^a次方會因為%(Mod)的關係變為0，而進位只需要確定要不要就可以了，如此才使用or。

C++(0.084)

/*******************************************************/
/* UVa 11121 Base -2                                   */
/* Author: Maplewing [at] knightzone.studio            */
/* Version: 2012/01/17                                 */
/*******************************************************/
#include<iostream>
#include<cstdio>
#include<cmath>
using namespace std;

int main(){
  int N, num, carry, sign, digit;
  while( scanf( "%d", &N ) != EOF ){
    for( int x = 1 ; x <= N ; x++ ){
      scanf( "%d", &num );
      printf( "Case #%d: ", x );
      if( num == 0 ){
        printf( "0\n" );
        continue;
      }

      int bits[50] = {0};
      sign = num;
      num = abs(num);
      digit = 0;
      while( num ){
        bits[digit++] = num%2;
        num /= 2;
      }

      carry = 0;
      for( int i = 0 ; i < digit || carry ; i++ ){
        if( i >= digit ) digit = i+1;
        bits[i] += carry;
        carry = 0;
        if( i%2 && (sign > 0) && bits[i] ){
          carry |= 1;
          digit = max( digit, i+2 );
        }
        else if( !(i%2) && (sign < 0) && bits[i] ){
          carry |= 1;
          digit = max( digit, i+2 );
        }
        carry = carry || bits[i] / 2;
        bits[i] %= 2;
      }

      for( int i = digit-1 ; i >= 0 ; i-- )
        printf( "%d", bits[i] );
      printf( "\n" );
    }
  }
  return 0;
}