* Given a number m find the next higher number r , that has same number of 1-bits.
* Ex : 3 (0000011) => 5(0000101)
* 6(0000110) => 9(0001001)
* 11(0001011) => 13(0001101)
* 23(0010111) => 27(0011011)
* 24(0011000) => 33(0100001)
* 44(0101100) => 49(0110001)
* 46(0101110) => 51(00110011)
1st Thinking(Algorithm)
1.count number of set bits in given number .
2. start from that number in loop & count number of set bits in all number > n untill we found the same set bits in any number, once found stop.
but problem with this algorithm is that it will take too much time for bignumber
O(N) where N is number of iteration untill we find number > N with same number of set bits.
2nd Solution (Most Optimized)
# Observations I
* Look at the input and the outputs again and see if you can make some algorithm out of it
* 3 (0000011) => 5(0000101)
* 6(0000110) => 9(0001001)
* 11(0001011) => 13(0001101)
* 23(0010111) => 27(0011011)
* 24(0011000) => 33(0100001)
* 44(0101100) => 49(0110001)
* 46(0101110) => 51(00110011)
# Observations II
* Hint : Now concentrate on the highlighted parts of input
* 3 (0000 011 ) => 5(0000 101 )
* 6(000 0110 ) => 9(000 1001 )
* 11(0001 011 ) => 13(0001 101 )
* 23(001 0111 ) => 27(001 1011 )
* 24(0 011000 ) => 33(0 100001 )
* 44(01 01100 ) => 49(01 10001 )
* 46(01 01110 ) => 51(01 10011 )
# Observations III
* As you can see,
o the non-highlighted part is same in i/p and o/p as well
o And the highlighted part is consecutive 1’s from the least-significant side (right hand side)
* 3 (0000 011 ) => 5(0000 101 )
* 6(000 0110 ) => 9(000 1001 )
* 11(0001 011 ) => 13(0001 101 )
* 23(001 0111 ) => 27(001 1011 )
* 24(0 011000 ) => 33(0 100001 )
* 44(01 01100 ) => 49(01 10001 )
* 46(01 01110 ) => 51(01 10011 )
# Observations IV
* As you can see, the non-highlighted part is same in i/p and o/p as well
* 3 (0000 011 ) => 5(0000 101 )
* 6(000 0110 ) => 9(000 1001 )
* 11(0001 011 ) => 13(0001 101 )
* 23(001 0111 ) => 27(001 1011 )
* 24(0 011000 ) => 33(0 100001 )
* 44(01 01100 ) => 49(01 10001 )
* 46(01 01110 ) => 51(01 10011 )
# Observations V
* Now lets just look at what changed
* 011 => 101
* 0110 => 1001
* 011 => 101
* 0111 => 1011
* 011000 => 100001
* 01100 => 10001
* 01110 => 10011
* Do you see a pattern?
# Observations VI
* Yes, as you have rightly observed, left hand side is :
o A 0 followed by
o One or more 1’s (say x) followed by
o Zero or more 0’s (say y)
* Is changed to
o A 1 followed by
o (y+1) zeroes followed by
o (x-1) 1’s
* 0 11 => 1 0 1
* 0 11 000 => 1 0 000 1
Algorithm
# Now let’s frame the algorithm
* Given a bit-pattern, start from right, find successive zeroes (xxxx01111 0000 )
* Followed by zeroes find successive 1’s (xxxx0 1111 0000 )
* Stop on hitting a zero (xxxx 0 1111 0000 )
* Interchange that zero with a 1 from successive 1’s (xxxx 1 0 111 0000 )
* Now move the remaining 1’s to extreme right, filling the gap with zeroes (xxxx 1 0 0000 111 )
# Doing it programmatically in C
* unsigned snoob(unsigned x) {
o unsigned smallest, ripple, ones;
o // x = xxx0 1111 0000
o smallest = x & -x; // 0000 0001 0000
o ripple = x + smallest; // xxx1 0000 0000
o ones = x ^ ripple; // 0001 1111 0000
o ones = (ones >> 2)/smallest; // 0000 0000 0111
o return ripple | ones; // xxx1 0000 0111
* }
Working Code:
#include
using namespace std;
typedef unsigned int uint_t;
// this function returns next higher number with same number of set bits as x.
uint_t snoob(uint_t x)
{
uint_t rightOne;
uint_t nextHigherOneBit;
uint_t rightOnesPattern;
uint_t next = 0;
if(x)
{
// right most set bit
rightOne = x & -(signed)x;
// reset the pattern and set next higher bit
// left part of x will be here
nextHigherOneBit = x + rightOne;
// nextHigherOneBit is now part [D] of the above explanation.
// isolate the pattern
rightOnesPattern = x ^ nextHigherOneBit;
// right adjust pattern
rightOnesPattern = (rightOnesPattern)/rightOne;
// correction factor
rightOnesPattern >>= 2;
// rightOnesPattern is now part [A] of the above explanation.
// integrate new pattern (Add [D] and [A])
next = nextHigherOneBit | rightOnesPattern;
}
return next;
}
int main()
{
int x = 156;
cout<<"Next higher number with same number of set bits is "<
getchar();
return 0;
}
Time Complexity O(1)
Space Complexity O(1)
Run Here https://ideone.com/8R2N2
Source http://www.gowrikumar.com
No comments :
Post a Comment