ZeroJudge A414: 位元運算之進位篇

題目敘述

題目採EOF收資料直到N=0，每筆資料有一個正整數N。要求輸出以二進制計算 N+1 時所需的進位次數，以白話文來講的話就是計算N轉換成二進制之後從最右邊到左邊有幾個連續的1，因為二進制數字只要目前的位數是1加一之後就會需要進位。

範例輸入

1

4

7

17

0

範例輸出

1

0

3

1

解題思路

使用While迴圈將N轉換成二進制的字串，但是這樣子會有TLE的情況出現，所以不將二進制結果存進字串中，而是在While迴圈裡直接進行判斷。因為使用While迴圈轉二進制這個方式會從二進制結果的最右邊開始計算，剛剛好符合題目的要求，所以就是判斷目前得到的數字是否為1，如果是1的話答案就加1，如果是0的話就直接把While迴圈break掉以節省時間。最後輸出存答案的變數即可。要注意的是本題時間給的很緊，所以不建議使用#include <iostream>而是直接使用#include <stdio.h>然後用scanf和printf進行輸入和輸出 (詳情請見範例程式碼)。

解題程式碼如下 (僅供參考)：

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