Нахождение общего количества битов от 1 до n

Question

Напишите алгоритм, чтобы найти F(n) количество бит, установленное в 1, во всех числах от 1 до n для любого заданного значения n.

Сложность должна быть O(log n)

Например:

1: 001
2: 010
3: 011
4: 100
5: 101
6: 110

So

F(1) = 1,  
F(2) = F(1) + 1 = 2,
F(3) = F(2) + 2 = 4,
F(4) = F(3) + 1 = 5,
etc.

Я могу только разработать алгоритм O(n).

Answer 1

это закодировано в Java ...
логика: скажем, число 34, двоичный равный муравей 10010, который можно записать как 10000 + 10. 10000 имеет 4 нуля, поэтому число всех 1 до этого числа равно 2 ^ 4 (причина ниже). таким образом, количество составляет 2 ^ 4 + 2 ^ 1 + 1 (число само по себе). так что ответ 35.
* для двоичного числа 10000. общее количество комбинаций заполнения 4 мест составляет 2 * 2 * 2 * 2x2 (один или ноль). Таким образом, общее количество комбинаций равно 2 * 2 * 2 * 2.

public static int getOnesCount(int number) {
    String binary = Integer.toBinaryString(number);
    return getOnesCount(binary);
}

private static int getOnesCount(String binary) {
    int i = binary.length();

    if (i>0 && binary.charAt(0) == '1') {
        return gePowerof2(i) + getOnesCount(binary.substring(1));
    }else if(i==0)
        return 1;
    else
        return getOnesCount(binary.substring(1));

}
//can be replaced with any default power function
private static int gePowerof2(int i){
    int count = 1;
    while(i>1){
        count*=2;
        i--;
    }
    return count;
}

Answer 2

Вот функция Java

private static int[] findx(int i) {
    //find the biggest power of two number that is smaller than i
    int c = 0;
    int pow2 = 1;
    while((pow2<< 1) <= i) {
        c++;
        pow2 = pow2 << 1;
    }
    return new int[] {c, pow2};
}

public static int TotalBits2(int number) {
    if(number == 0) {
        return 0;
    }
    int[] xAndPow = findx(number);
    int x = xAndPow[0];
    return x*(xAndPow[1] >> 1) + TotalBits2(number - xAndPow[1]) + number - xAndPow[1] + 1;
}