Q:

Algorithm for finding the smallest +ve integer greater than a given number that has the same binary weight as given integer

The binary weight of a positive integer is the number of 1's in its binary representation. For example, the decimal number 1 has a binary weight of 1, and the decimal number 7 (which is 111 in binary) has a binary weight of 3.
Given a positive integer N, find the smallest integer greater than N that has the same binary weight as N.
public static int compute(int number)   {
    int  count = 0, nextNumber;
    char[] arr =  Integer.toBinaryString(number).toCharArray();
    for(int i =0 ; i < arr.length ;++i) {
        if(arr[i] == '1')
            ++count;
    }
    nextNumber = findNextNumber(number,count);
    return nextNumber;
}
public static int findNextNumber(int number, int weight) {
    char[] arr;
    boolean flag = true;
    int count;
    while (flag) {
        // increment number and convert it into char array
        arr = Integer.toBinaryString(++number).toCharArray();
        count = 0;
        for(int i =0 ; i < arr.length; ++i) {
            if(arr[i] == '1')
                ++count;
        }
        if(count == weight) {
            flag = false;
        }
    }

    return number;
}

My solution works fine but it's complexity seems to be O(NlogN).Can this be achieved in O(N) or O(log N) by some other approach ?

A:

This operation is sometimes called "snoob". Here is a bunch of approaches from the Hacker's Delight book. Probably the best would be to use Integer.numberOfTrailingZeros which likely compiles to a hardware instruction (untested):
int snoob1(int x) {
   int smallest, ripple, ones;  // x = xxx0 1111 0000
   smallest = x & -x;           //     0000 0001 0000
   ripple = x + smallest;       //     xxx1 0000 0000
   ones = x ^ ripple;           //     0001 1111 0000
   ones = ones >>> (2 + Integer.numberOfTrailingZeros(x)); //     0000 0000 0111
   return ripple | ones;        //     xxx1 0000 0111
}

(there might also be an issue with possible overflow in the "2+" part, since in Java shift counts are modulo 32)

