프로그래밍/컴퓨터 알고리즘

[BOJ] 3460 - 이진수 풀이

포도알77 2019. 4. 3. 22:57

1. 문제

문제

양의 정수 n이 주어졌을 때, 이를 이진수로 나타냈을 때 1의 위치를 모두 찾는 프로그램을 작성하시오. 최하위 비트(least significant bit, lsb)의 위치는 0이다.

입력

 

첫째 줄에 테스트 케이스의 개수 T가 주어진다. 각 테스트 케이스는 한 줄로 이루어져 있고, n이 주어진다. (1 ≤ T ≤ 10, 1 ≤ n ≤ 10

6

)

출력

 

각 테스트 케이스에 대해서, 1의 위치를 공백으로 구분해서 출력한다. 위치가 낮은 것부터 출력한다.

예제 입력

1

13

예제 출력

0 2 3

힌트

 
[출처 : BOJ, 문제에 대한 모든 권리는 BOJ(acmicpc.net, startlink)에 있음]

 

2. 해답

 이 문제는 정수를 어떻게 이진수로 표현하고 있는지, 그리고 비트와이즈 연산을 활용할 수 있는지 물어보는 문제이다.
간단하게 right shift와 비트와이즈 and &를 통하여 답을 구할 수 있다.
 
#include <bits/stdc++.h>
using namespace std;
int main()
{
	int n;
	scanf("%d",&n);
	while(n--){
		int x;
		scanf("%d",&x);
		int idx=0;
		while(x){
			if(x&1)printf("%d ",idx);
			x>>=1;
			++idx;
		}
		puts("");
	}
}

 

페이스북으로 공유카카오톡으로 공유카카오스토리로 공유트위터로 공유URL 복사