5.3 Bits – next smallest and largest have the same No. of 1′s. | Ruobo [m2w]

http://www.slideshare.net/gkumar007/bits-next-higher-presentation
5.3 Bits – next smallest and largest have the same No. of 1′s. | Ruobo [m2w]
5.3 Given an integer, print the next smallest and next largest number that have the same number of 1 bits in their binary representation.
The Brute Force Approach:
An easy approach is simply brute force: count the number of 1’s in n, and then increment (or decrement) until you find a number with the same number of 1’s. Easy 
Observations:
»»If we “turn on” a 0, we need to “turn off” a 1
»»If we turn on a 0 at bit i and turn off a 1 at bit j, the number changes by 2^i – 2^j.
»»If we want to get a bigger number with the same number of 1s and 0s, i must be bigger than j.
Solution:

next smallest
1. Traverse from right to left. Once we’ve passed a 1, turn on the next 0. We’ve now increased the number by 2^i. Yikes! Example: xxxxx011100 becomes xxxxx111100
2. Turn off the one that’s just to the right side of that. We’re now bigger by 2^i – 2^(i-1) Example: xxxxx111100 becomes xxxxx101100
3. Make the number as small as possible by rearranging all the 1s to be as far right as possible: Example: xxxxx101100 becomes xxxxx100011

previous largest, we do the reverse.
1. Traverse from right to left. Once we’ve passed a zero, turn off the next 1. Example: xxxxx100011 becomes xxxxx000011.
2. Turn on the 0 that is directly to the right. Example: xxxxx000011 becomes xxxxx010011.
3. Make the number as big as possible by shifting all the ones as far to the left as possible. Example: xxxxx010011 becomes xxxxx011100 .

next smallest

xxxxx011100 ↓ find a 1, make next 0=1,

xxxxx101100 ↓ make last 1=0,

xxxxx100011   push all right 1's to right.

previous largest, we do the reverse.

xxxxx100011 ↓ find a 0, make next 1=0, and set its preivous 0=1

xxxxx010011 ↓ then push every 1's to the left.

xxxxx011100

Code from http://ms-amazon.blogspot.com/2013/06/given-number-print-nex-largest-number.html

 //check if bit at pos is 1 or 0
 bool isSet(int number , int pos)
 {
      if( (number & (1<<pos)) > 0)
          return true;
      return false;
 }

 //set Bit at index pos to 1
 int setBit(int number , int pos)
 {
     number |= 1<<pos;
     return number;
 }

 //set bit at index pos to 0
 int unsetBit(int number, int pos)
 {
     number &= ~(1<<pos);
     return number;
 }

 //Return Next Greater number
 int getNextGreater(int number)
 {
     if(number <= 0)
         return -1;
     int maxIndex;
     int countOnes = 0;
     int pos = 0;
    
     //Scan number from right to left bit.
     for(bool encounterFlag = false; pos < 32 ; pos++)
     {
             if(encounterFlag)
             {
                  if( !isSet(number , pos) )
                  {
                      // set first 0 bit after encounteredFlag is true 
                      number = setBit(number, pos);
                      // unset 1 bit immediately right of the above bit. 
                      number = unsetBit(number, --pos);
                      break;
                  }
                  else
                      continue;
             }
                  //As soon as a 1 is encountered, encounteredFlag is set.
             if( isSet(number , pos))
                  encounterFlag = true;
     }
    
     //Count no. of 1's after maxIndex.
     for(int i=pos -1; i>=0 ; i--)
     {
             if(isSet(number, i))
                 countOnes++;
     }
     //Pushing all 1's to left.
     for(int j=pos -1; j>= countOnes; j--)
         number = unsetBit(number, j);
    
     for(int k=countOnes-1 ; k>=0; k--)
         number = setBit(number, k);
    
     return number;
 }

 int getNextSmaller(int number)
 {
     if(number < 0)
         return -1;
     int maxIndex;
     int countOnes = 0;
     int pos = 0;
     for(bool encounterFlag = false; pos < 32; pos++)
     {
          if(encounterFlag)
          {
               if(isSet(number, pos))
               {
                   //After encounterFlag is set Turnoff next 1 Bit.
                   number = unsetBit(number, pos);
                   //Turn on 0 bit on right of this bit.
                   number = setBit(number, --pos);
                   break;
               }
               else
                   continue;
          }
          //Set encounter flag after first zero is encountered.
          if(!isSet(number,pos))
          {
               encounterFlag = true;
          }
         
     }
    
     //Count no. of 1's after maxIndex.
     for(int i=pos -1; i>=0 ; i--)
     {
          if(isSet(number, i))
              countOnes++;
     }
   
     //Pushing all 1's to left.
     for(int j=pos -1; j>= countOnes; j--)
         number = setBit(number, j);
    
     for(int k=countOnes-1 ; k>=0; k--)
         number = unsetBit(number, k);
    
     return number;
    
 }

 int main()
 {
     cout<<getNextGreater(18)<<endl;
     cout<<getNextSmaller(18)<<endl;
     system("pause");
 }

Better SolutionO(1) for Next higher number with same number of set bits http://www.geeksforgeeks.org/next-higher-number-with-same-number-of-set-bits/

Also refer to http://www.slideshare.net/gkumar007/bits-next-higher-presentation
Read full article from 5.3 Bits – next smallest and largest have the same No. of 1′s. | Ruobo [m2w]