nyoj 412 Same binary weight (bitset 류 활용)

1738 단어 종류poj
bitset 클래스:http://blog.163.com/lixiangqiu_9202/blog/static/53575037201251121331412/
Same binary weight
시간 제한:
300 ms  |  메모리 제한:
65535 KB
난이도:
3
묘사 하 다.
The binary weight of a positive  integer is the number of 1's in its binary representation.for example,the decmial number 1 has a binary weight of 1,and the decimal number 1717 (which is 11010110101 in binary) has a binary weight of 7.Give a positive integer N,return the smallest integer greater than N that has the same binary weight as N.N will be between 1 and 1000000000,inclusive,the result is guaranteed to fit in a signed 32-bit interget.
입력
The input has multicases and each case contains a integer N.
출력
For each case,output the smallest integer greater than N that has the same binary weight as N.
샘플 입력
1717
4
7
12
555555

샘플 출력
1718
8
11
17
555557

근원
topcoder
업로드 자
낙 괴 영
생각:
1. 오른쪽 에서 왼쪽으로 1 대 01 로 위 치 를 바꾼다.
2. 오른쪽 에 있 는 모든 1 을 맨 오른쪽으로 이동
#include<iostream>
#include<string.h>
#include<algorithm>
#include<stdio.h>
#include<bitset>
using namespace std;

int main()
{
    int n;
    while(cin>>n)
    {
        bitset<32>tp(n);
        int i,j,cnt=0;
        for(i=0;i<32;++i)
        {
            if(tp[i]) ++cnt;
            if(tp[i]&&!tp[i+1])
            {
                tp[i]=false;
                tp[i+1]=true;
                j=i;
                break;
            }
        }

        --cnt;
        for(i=0;i<cnt;++i) tp[i]=true;

        while(i<j) tp[i++] =0;

        cout<<tp.to_ulong()<<endl;
    }
}

좋은 웹페이지 즐겨찾기