sol(1 x) = x - 2 * (popcount(x) - 1) - popcount(x ^ (x - 1))

In GCC you have the builtin function __builtin_popcount. For MSVC, the builtin __popcnt doesn't seem to be available on the server, but you can easily find an O(1) implementation on the Internet.

Hi,

How can it be proved, deduced?

Thanks.

    public static void main(String[] args) throws FileNotFoundException {
        InputStream is = System.in;
        Scanner sc = new Scanner(new InputStreamReader(is));
        int distance = from1toN(sc.nextInt()) - from1toN(sc.nextInt());
        if (distance>0)
            System.out.println(distance);
        else
            System.out.println(-distance);
    }

    static int from1toN(int n) {
        int j = Long.bitCount(n)-1;
        return n - j - j - thefirstIndexOfOne(n);
    }

    static int thefirstIndexOfOne(int n) {
        int inx = 1;
        while(n>0) {
            if ((n&1)==1) break;
            n/=2;
            inx++;
        }
        return inx;
    }

N xor (N-1) = the first index of one of N - you learn something everyday

        1 1 0
        1 2 0
        1 3 0
        1 4 1    4 - 2*(c_of_ones[100]-1) - 3 (TO level, leafs level=1)
        1 5 2
        1 6 2
        1 7 2
        1 8 4    8 - 2*(c_of_ones[1000]-1) - 4 (TO level, leafs level=1)
        1 9 6
        1 10 6    10 - 2*(c_of_ones[1010]-1) - 2 (TO level, leafs level=1)
        1 11 6    11 - 2*(c_of_ones[1011]-1) - 1 (TO level, leafs level=1)
        1 12 7    12 - 2*(c_of_ones[1100]-1) - 3 (TO level, leafs level=1)
        1 13 8
        1 14 8
        1 15 8
        1 16 11

        int j = Long.bitCount(n)-1;
                return n - j - j - thefirstIndexOfOne(n);

                   16
                8
           4         12
         2___6       10    14
        1_3 5_7 _ 9_11 13_15 _

Edited by author 18.09.2015 11:47