[for문]1의 위치 (1일차)

프로그램 명: bit_pos

제한시간: 1 초

양의 정수 n 을 입력으로 받아 이 수를 이진수로 나타내었을 때 1 이 나타나는 위치를 구하는 것이 문제이다.

수를 이진수로 나타내었을 때 가장 오른쪽의 자리를 LSB(Least Significant Bit)라 한다. LSB 를 0 번 위치로 간주한다.

입력

양의 정수 n 이 입력으로 주어진다. ( 1 <= n <= 10^6 )

출력

1 이 나타나는 위치를 모두 출력한다.

입출력 예

입력

13

출력

0 2 3 

출처: Central European Programming Contest 

[문제 풀이]

이 문제의 경우 10진수를 2진수로 바꾼 후에 1이 나타나는 위치를 찾는 문제입니다.

주어진 예제에서 13의 경우 2진수로 바꾸면 1101 이 됩니다.

문제에서 제일 오른쪽에서부터 0으로 시작한다 하였으니, 

현재 1이 나타나는 위치는 오른쪽에서부터 순서대로 0, 2, 3이 됩니다.

3	2	1	0
1	1	0	1

[소스코드 설명]

저는 짝수일 때와 홀수 일때에 대해서 따로 생각을 했습니다.

홀수 : 0001(1), 0011(3), 0101(5), 0111(7), 1001(9), 1011(11), 1101(13), ...

짝수 : 0010(2), 0100(4), 0110(6), 1000(8), 1010(10), 1100(12), 1110(14), ...

혹시 규칙이 보이시나요?

홀수의 경우 0의 자리가 무조건 1로 끝나고, 짝수의 경우 0의 자리가 무조건 0으로 끝나게 됩니다.

그래서 저는 "isFirst" 라는 것을 선언해서 홀수면서 처음나누어지는 것에 대해서는 무조건 1임을 나타내서 출력할 때 0도 포함이 되게 하였습니다.(1011)

그 다음 10진수를 2진수로 바꾸는 것을 손으로 직접 해보시면 아시겠지만, N값이 1이 될 때까지 계속 나눕니다. 따라서 N이 1이되면 break;로 계산을 멈추게 하였습니다.

그리고 2진수로 바꾸는 것이기 때문에 한 번 계산이 끝날 때마다 N값을 N/2로 갱신해주었습니다.

//bit_pos
#include <iostream>

using namespace std;
int n;

int main(){
	int ans=0;
	bool isFirst = true;

	cin >> n;	//13
	
	do{
		if (n%2 != 0){
			if(isFirst){
				isFirst = false;
			}
			else
				cout << " ";
			cout << ans;
		}
		ans++;
		if(n == 1)
			break;

		n = n/2;

	}while(true);

	cout << endl;
	return 0;
}