ZeroJudge A414: 位元運算之進位篇

一個數在電腦裡遞增時需要進位幾次?

範例測資

範例輸入範例輸出
EOF 輸入,每一行有一個十進制正整數 N (1 <= N <= 2147483647)。輸入的最後一行有一個 0,代表輸入的結束,請勿對 0 做任何處理。對於每個正整數 N ,請輸出以二進制計算 N+1 時所需的進位次數。
1
4
7
17
0
1
0
3
1

解題思路

使用While迴圈將N轉換成二進制並直接進行判斷。因為使用While迴圈轉二進制這個方式會從二進制結果的最右邊開始計算,剛剛好符合題目的要求,所以就是判斷目前得到的數字是否為1,如果是1的話答案就加1,如果是0的話就直接把While迴圈Break。

舉例:
  • 「4」的二進制是「100」,+1 的時候會變成「101」不需要進位。
  • 「7」的二進制是「111」,+1 的時候會變成「1000」,需要進位3次,因為從右到左有連續三個1。

最後輸出存答案的變數即可。要注意的是本題時間給的很緊,所以不建議使用#include <iostream>而是直接使用#include <stdio.h>然後用scanf和printf進行輸入和輸出 (詳情請見範例程式碼)。

範例程式碼-ZeroJudge A414: 位元運算之進位篇

#include <stdio.h>
using namespace std;

int main() {
    int N;
    while (scanf("%d", &N) && N != 0)
    {
        int count = 0;
        while(N % 2 == 1)
        {
            ++count;
            N /= 2;
        }
        printf("%d\n", count);
    }
}

//A414
//Dr. SeanXD

發佈留言