[백준] 24500번 blobblush

https://www.acmicpc.net/problem/24500

24500번: blobblush

 

배타적 논리합은 둘 중 하나의 비트만 1일 때 1이 된다.

7(0111) ⊕ 2(0010) = 5(0101)

배타적 논리합의 결과는 두 수의 최상위 비트보다 더 큰 수가 나올 수 없다.8(1000) 과 8 보다 아래의 수의 배타적 논리합의 최대값은 15(1111)가 최대임을 알 수 있다.

 

또한 1000은 그 아래에 0111이 존재하고, 1010과 같은 수도 그 아래에 0101과 같은 수가 존재하기 때문에 최상위 비트까지 1로만 구성되어 있는 수를 최대 2장으로 만들 수 있다.1000 ⊕ 0111 = 1111 , 1010 ⊕ 0101 = 1111처음 주어지는 수가 이미 7(111) 1로만 구성되어 있다면 해당 수가 최대 값임을 알 수 있고처음 주어지는 수가 1로만 구성되어 있지 않다면 그 수를 flip한 수와 배타적 논리합을 하여 최대 값을  구할 수 있다.1000 ⊕ 0111(1000의 flip) = 1111

 

 

#include<iostream>
#include<algorithm>
#include<vector>
#include<map>
using namespace std;

int arr[100000];
int flip[100000];
int bitSize = 0;

void tran(unsigned long long N) {
	if (N == 0) {
		arr[bitSize] = 0;
		bitSize++;
		return;
	}
	
	while (N > 0) {
		if (N % 2 == 1) {
			N = N / 2;
			arr[bitSize] = 1;
		}
		else {
			N = N / 2;
			arr[bitSize] = 0;
		}
		bitSize++;
	}

	

}

void bitflip() {
	for (int i = 0; i < bitSize; i++) {
		if (arr[i] == 0) {
			flip[i] = 1;
		}
		else {
			flip[i] = 0;
		}
	}
}

unsigned long long reTran() {
	unsigned long long sum = 0;
	unsigned long long gop = 1;

	for (int i = 0; i < bitSize; i++) {
		if (flip[i] == 1) {
			sum = sum + gop * flip[i];
			gop = gop * 2;
		}
		else {
			gop = gop * 2;
		}
	}

	return sum;
}



int main() {
	ios::sync_with_stdio(false);
	cin.tie(NULL);

	unsigned long long N;
	cin >> N;

	tran(N);
	
	

	int flag = 1;

	for (int i = 0; i < bitSize; i++) {
		if (arr[i] == 0) {
			flag = 0;
			break;
		}
	}

	if (flag == 1) {
		cout << 1 << '\n';
		cout << N;
		return 0;
	}

	bitflip();

	unsigned long long result = reTran();


	cout << 2 << '\n';
	cout << result << " " << N;



	


	
}