Next integer with same number of set bits

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)

Eg.
N = 10 (1010)
Next = 12 (1100)

Solution :

1. 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
2. Now 2^x is given by N&-N
3. Suppose M = N + 2^x
4. Similarly 2^(x+y) is given by M&-M
5. 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;

}