本文介绍了一种快速计算从0到n进行二进制加法时总进位次数的方法。通过使用n&(n-1)来计算二进制中1的数量，并结合进位原理，给出了一种高效的解决方案。
| Status | In/Out | TIME Limit | MEMORY Limit | Submit Times | Solved Users | JUDGE TYPE |
|---|---|---|---|---|---|---|
 | stdin/stdout | 3s | 8192K | 730 | 254 | Standard |
作为2进制的加法，从k加1变成k+1可能会出现若干进位。如1011加1就会有2个进位。给定n，从0开始不停地加1直到n，计算在此过程中总共会有多少次进位。
Input
输入的每一行有单独的一个值n。n=0标志输入结束Output
对于输入的每一行，使用单独一行输出对应结果。Sample Input
2 5 10 0
Sample Output
1 3 8
Problem Source: skywind
今天才知道用N&(N-1)可以去除掉最后一位的一，所以可以计算出一得个数，当然这道题可以用模拟来做，但用模拟做就没有意义了。
思路大概是先算出一的个数，接着用原来的数-1的个数就是进位的总数。想象下游N个1代表原来的数，多一个进位就少一个1，所以原来的数-现在1的个数就是进位数
#include<iostream>
int main()
{
int n;
//freopen("in.txt","r",stdin);
//freopen("out.txt","w",stdout);
while((scanf("%d",&n),n)!=0)
{
int num=0;
int t=n;
while(n)
{
num++;
n=n&(n-1);
}
printf("%d/n",t-num);
}
return 0;
}
扫一扫
631
被折叠的 条评论
为什么被折叠?
到【灌水乐园】发言
