[더블릿 - 6] 비밀 번호(고2)/koi_number

프로그램 명: koi_number

제한시간: 1 초

KOI 보안회사에서는 자동으로 비밀번호를 만드는 시스템을 연구하고 있다. 주어진 하나의 양의 정수에 대하여 다음의 원칙에 따라 두 수를 만들어 비밀번호를 정하려고 한다.

하나의 주어진 양의 정수 A 에 대하여 비밀번호를 위한 두 수를 만드는 방법은 다음과 같다.

1. A 의 이진수 표현에서 나오는 1의 개수 x 를 찾는다.
2. A 보다 작은수 중에서 그 수의 이진수 표현에서 1의 개수가 x 와 같고 A 에 가장 가까운 수를 하나 찾는다.
3. A 보다 큰수 중에서 그 수의 이진수 표현에서 1의 개수가 x 와 같고 A 에 가장 가까운 수를 하나 찾는다.

예를 들어, 주어진 수 A 가 43이면, 이 수의 이진수 표현은 101011₂ 이다. 이 이진수는 1의 개수가 4이다. 그러므로 43보다 작고 43에 가장 가까우며 이진수 표현에서 1의 개수가 4인 수는 39=100111₂이다. 또한 43보다 크고 43에 가장 가까우며 이진수 표현에서 1의 개수가 4인 수는 45=101101₂이다.

이 두 수를 찾아 출력하는 프로그램을 작성하시오. 프로그램의 실행시간은 1초를 넘을 수 없다. 부분 점수는 없다.

입력 형식

입력의 첫 번째 줄에는 하나의 양의 정수 A 가 주어진다. 단, 1 <= A <= 10¹⁸이다.

출력 형식

주어진 수 보다 작은 수 중에서 이진수의 1의 개수가 같으며 가장 가까운 수와, 주어진 수 보다 큰 수 중에서 이진수의 1의 개수가 같으며 가장 가까운 수를 한 줄에 빈칸을 사이에 두고 출력한다. 만약 그러한 수가 존재하지 않으면 그 수에 대해서는 0 을 출력한다.

입력과 출력의 예

입력 

43

출력

39 45

입력 

7

출력 

0 11

출처:koi 2011 지역본선 고등 2

못풀겠어서 구글에서 검색을 좀 했다. 키워트는 next number same bits 검색해보니 글들이 많아서 쉽게 자료를 찾을 수 있었고 많은 도움이 되었다. 이 문제가 비트연산을 사용해서 푸는것이란건 짐작했지만 처음에 내가 짜던 것과는 거리가 많았다. 알아두면 좋은 비트연산이 많으므로 두고두고 보면 좋을것 같다. 경과 시간은 좀 느리지만 코드사이즈가 젤 작은것에 만족한다. 내가 정리한 내용은 다음 링크를 참조
비트수가 같은 다음 수(Next Higher or Lower Number with same number of binary bits set)

#include <iostream>

using namespace std;typedef long long t;t A,B;t F(t x){t a=x&-x,b=a+x,c=((x^b)>>2)/a;return B=b|c;}int main(){cin>>A;cout<<(~F(~A)==-1?0:~B)<<" "<<F(A);return 0;}