a132 - 10931 - Parity

🔗 前往 ZeroJudge 原題

題目描述

題目要求計算一個整數的「同位元」，定義為其二進位表示法中 1 的個數除以 2 的餘數。輸入為一系列整數，直到輸入 0 為止。對於每個輸入整數，輸出其二進位表示和同位元。

解題思路

解題思路是將輸入的整數轉換為二進位表示，然後計算二進位中 1 的個數，最後計算 1 的個數除以 2 的餘數。程式碼中，使用迴圈不斷將整數除以 2，並將餘數（0 或 1）添加到字串中，同時計算 1 的個數。最後，將二進位字串反轉輸出，並輸出同位元。

複雜度分析

• 時間複雜度: O(log n)，其中 n 是輸入整數。因為迴圈的次數與輸入整數的二進位表示的長度成正比，而二進位表示的長度與 log n 成正比。
• 空間複雜度: O(log n)，因為需要一個字串來儲存二進位表示，其長度與 log n 成正比。

程式碼

#include <iostream>
#include <string>
using namespace std;
int main(){
	long long int a;
	while(cin >> a){
		if(a==0)break;
		string ans;
		int n=0;
		while(a>0){
			ans+=a%2+48;
			if(a%2==1)
				n++;
			a/=2;
		}
		cout << "The parity of " ;
		for(int i=ans.length()-1;i>=0;i--)
			cout << ans[i];
		cout << " is " << n << " (mod 2).\n";
	}
}