2010年7月25日 星期日

575 - Skew Binary

當一數值以十進位表示時，第k位數表示10k(十進制由右至左編碼，最低有效位數為第0位)。例如：

\begin{displaymath}81307_{10} = 8 \times 10^4 + 1 \times 10^3 + 3 \times 10^2 + ... ...mes 10^1 + 7 \times 10 0 = 80000 + 1000 + 300 + 0 + 7 = 81307. \end{displaymath}

當一數值以二進制表示時，第k位數表示2k。例如：

\begin{displaymath}10011_2 = 1 \times 2^4 + 0 \times 2^3 + 0 \times 2^2 + 1 \times 2^1 + 1 \times 2^0 = 16 + 0 + 0 + 2 + 1 = 19. \end{displaymath}

當一數值以"斜偏二進制(Skew Binary)"表示時，第k位數表示 2k+1 - 1。除了最低非零的位數可能等於2之外，所有數值皆為0或1。例如：

\begin{displaymath}10120_{skew} = 1 \times (2^5 - 1) + 0 \times (2^4-1) + 1 \tim... ...2 \times (2^2-1) + 0 \times (2^1-1) = 31 + 0 + 7 + 6 + 0 = 44. \end{displaymath}

前十個斜偏二進制(skew binary)的數值為0, 1, 2, 10, 11, 12, 20, 100, 101, 102。(skew binary在某些領域特別有用，因為它使一數值加上1之後，最多只進位一次，但這方面的議題與本題目無關)

Input

輸入檔案有多列，每一列為一整數 n。假如 n=0 代表輸入結束，否則 n 為以斜偏二進制(skew binary)表示的非負整數。
對每一個輸入值，輸出它的十進制表示式。n 的十進位值最大可能到 231 - 1 = 2147483647。

Sample Input

10120
200000000000000000000000000000
10
1000000000000000000000000000000
11
100
11111000001110000101101102000
0

Sample Output

44
2147483646
3
2147483647
4
7
1041110737
原文出處

沒有留言:

張貼留言

訂閱： 張貼留言 (Atom)