RANDOMIZED ALGORITHMS 5

QUESTION

Given a number x, find next number with same number of 1 bits in its binary representation.\n\nFor example, consider x = 12, whose binary representation is 1100 (excluding leading zeros on 32 bit machine). It contains two logic 1 bits. The next higher number with two logic 1 bits is 17 (100012).

ANSWER

#include<iostream>
 
using namespace std;
 
typedef unsigned int uint_t;
 

uint_t snoob(uint_t x)
{
 
  uint_t rightOne;
  uint_t nextHigherOneBit;
  uint_t rightOnesPattern;
 
  uint_t next = 0;
 
  if(x)
  {
 
    
    rightOne = x & -(signed)x;
 
   
    nextHigherOneBit = x + rightOne;
 
    
    rightOnesPattern = x ^ nextHigherOneBit;
 
    
    rightOnesPattern = (rightOnesPattern)/rightOne;
 
   
    rightOnesPattern >>= 2;
 
    
 
    next = nextHigherOneBit | rightOnesPattern;
  }
 
  return next;
}
 
int main()
{
  int x;
  cin>>x;
  cout<<snoob(x);
 
  getchar();
  return 0;
}
Ads Blocker Image Powered by Code Help Pro

Ads Blocker Detected!!!

We have detected that you are using extensions to block ads. Please support us by disabling these ads blocker.