Given a number x, find next number with same number of 1 bits in it’s binary representation.
For 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).
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
Working Code:
#include<stdio.h>
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)
More Example:
The Algorithm Flow:
C Code:
Create 32 Bit numbers (signed or unsigned doesn't matter, the
highest bit will never be set anyway) and each number must have a given
number of Bits set
For 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).
1st Approach:
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/swap 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 programatically in C
* unsigned snoob(unsigned x) {
o unsigned smallest, ripple, ones;
o // x = xxx0 1111 0000
o smallest = x & -x; // 0000 0001 0000------------remove all ones except the right most
o ripple = x + smallest; // xxx1 0000 0000 ------Swap the 1 and zero
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<stdio.h>
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)
More Example:
The Algorithm Flow:
x = 15610 x = 10011100(2) 10011100 00011100 - right most string of 1's in x 00000011 - right shifted pattern except left most bit ------> [A] 00010000 - isolated left most bit of right most 1's pattern 00100000 - shiftleft-ed the isolated bit by one position ------> [B] 10000000 - left part of x, excluding right most 1's pattern ------> [C] 10100000 - add B and C (OR operation) ------> [D] 10100011 - add A and D which is required number 163(10)
C Code:
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;// right most set bit // 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. rightOnesPattern = x ^ nextHigherOneBit;// isolate the pattern rightOnesPattern = (rightOnesPattern)/rightOne;// right adjust pattern rightOnesPattern >>= 2; // correction factor // rightOnesPattern is now part [A] of the above explanation. // integrate new pattern (Add [D] and [A]) next = nextHigherOneBit | rightOnesPattern; } return next;}Variation:
Reference:http://stackoverflow.com/questions/506807/creating-multiple-numbers-with-certain-number-of-bits-sethttp://stackoverflow.com/questions/7451922/bitwise-shift-to-generate-all-possible-permutations-in-c?lq=1
Nice explanation ...thnx..
ReplyDelete