BitSet有关问题

BitSet问题

BitSet问题

    Given an integer, print the next smallest andnext largest number

 that have the same number of 1 bits in their binaryrepresentation.

基本思路

     参照字典序问题  1 2 3 4 5 -> 1 2 3 5 4 

    同理

           101101011-> 101101101 (next) ascending

           101101011->101100111(pre)descending

具体实现：

bool nextOne(const bitset<N>& bs, bitset<N>& next,int n){if(0 > n)return false;//1.从后向前扫描，寻找01序对    int i, cnt_0 = 0;for(i = n-1; i > 0; --i){if(!bs.test(i)) ++cnt_0;if(!bs.test(i-1) && bs.test(i))break;}if(i <= 0)return false;next = bs;//2.交换i-1与i位next[i-1] = 1; next[i] = 0;++cnt_0;//3.升序for(int j = 0; i < n; ++i){if(j < cnt_0){next[i] = 0;++j;}else{next[i] = 1;}}//ascendingreturn true;}bool preOne(const bitset<N>& bs, bitset<N>& pre,int n){if(0 > n)return false;//1.从后向前扫描，寻找10序对1000    int i, cnt_1 = 0;for(i = n-1; i > 0; --i){if(bs.test(i)) ++cnt_1;if(bs.test(i-1) && !bs.test(i))break;}if(i <= 0)return false;pre = bs;pre[i-1] = 0; pre[i] = 1;++cnt_1;for(int j = 0; i < n; ++i){if(j < cnt_1){pre[i] = 1;++j;}else{pre[i] = 0;}}//descendingreturn true;}