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.
Finally, output the variable that stores the answer. Please note that since time is limited for this problem, it's recommended to avoid using #include and instead use #include along with scanf and printf for input and output.
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