How many times does a number need to carry when incremented in a computer?
Sample Inputs/Outputs
| Sample Input(s) | Sample Output(s) |
|---|---|
| EOF Input: Each line contains a decimal positive integer N (1 <= N <= 2147483647). The last line of input contains a 0, indicating the end of input. Do not process the input for 0. | For each positive integer N, output the number of carries required when calculating N+1 in binary. |
| 1 4 7 17 0 | 1 0 3 1 |
Thought Process
Use a while loop to convert N into binary and perform the calculation directly. Because using a while loop to convert to binary starts from the rightmost bit, it perfectly fits the requirement of the problem. So, check if the current digit obtained is 1, if yes, increment the answer by 1; if it is 0, break the while loop.
Example:
- The binary representation of "4" is "100." When adding 1, it becomes "101," which does not require a carry.
- The binary representation of "7" is "111." When adding 1, it becomes "1000," requiring 3 carries because there are three consecutive 1s from right to left.
最後輸出存答案的變數即可。要注意的是本題時間給的很緊，所以不建議使用#include <iostream>而是直接使用#include <stdio.h>然後用scanf和printf進行輸入和輸出 (詳情請見範例程式碼)。
Sample Code－ZeroJudge A414: Bit Calculation
#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