Given an integer N. Devise an algorithm to find out the smallest integer greater than N having the same number of bits set as that of N. (When a bit is 1, we say it is set)
Click here to see the solution.
p.s. - For Remarks please hit the given link once. For Hint, hit it twice and for the solution, hit it thrice.
Courtesy: Vibhaj
Hints: Try to find out general formula for number having same number of set bits.
Hit again for solution |
|
Solution: Suppose N has last x bits 0 and then y bits 1, then in general the next number having same number of set bits is given by N + 2^(y-1) + 2^x - 1
-> Now 2^x is given by N&-N
-> Suppose M = N + 2^x
-> Similarly 2^(x+y) is given by M&-M
-> So we get 2^(y-1) by (2^(x+y)/2^x >> 1)
Complexity :
Time : O(1)
Space : O(1)
Code :
int next_equal_setbits(int N){
int K1 = N & -N; int M = N + K1;
int K2 = M & -M;
return K2 + ((K2/K1)>>1) - 1;
}
|
|
|
Posts
