a414 - 位元運算之進位篇

🔗 前往 ZeroJudge 原題

題目描述

題目要求計算一個十進制正整數 N 加 1 後，在二進制表示下需要進行多少次進位。

解題思路

題目要求計算 N+1 的二進制表示中進位的次數。我們可以通過迭代的方式來模擬二進制加法，每次檢查 N 的最低位是否為 1。如果最低位是 1，則進位次數加 1，然後將 N 右移一位。如果最低位是 0，則直接右移一位，不進行進位。這個過程一直持續到 N 變為 0。

複雜度分析

• 時間複雜度: O(log N) (因為 N 每次右移一位，最多需要 log N 次迭代)
• 空間複雜度: O(1) (只使用了常數個變數)

程式碼

#include <iostream>
using namespace std;
int main(){
	long long int a=0,ans=0;
	while(scanf("%lld",&a) && a){
		if(a>0){
			while(a%2==1){
				ans++;
				a/=2;
			}
			printf("%d\n",ans);
			ans=0;
		}
	}
}