Рекурсия виновата

[monster-bonster]

Привет уважаемые гуру.
Дана рекурсивно заданная функция

f(0) = 0;
f(2·x) = f(x);
f(2·x + 1) = f(x) + 1

Я написал рекурсивный вариант
и обнаружил что она работает медленно.
вот моя функция.

long f(long n)
{
        if (!n)
                return 0;
        else if (!(n%2))
                return f(n/2);
        else if (n%2)
                return f(n/2)+1;
}

помогите написать нерекурсивный вариант.

[monster-bonster]

И какое время работы этой функции? (я думаю что log n)

[Abstraction]

Я написал рекурсивный вариант
и обнаружил что она работает медленно.

Как обнаружили?

И какое время работы этой функции? (я думаю что log n)

O(logN). Правильно думаете.

помогите написать нерекурсивный вариант.

Первое действие: перевести рекурсивную форму в хвостовую рекурсию.

long _f(long n, long ret)
{
        if (!n)
                return ret;
        else if (!(n%2))
                return _f(n/2, ret);
        else if (n%2)
                return _f(n/2, ret+1);
}

long f(long n) {return _f(n, 0)};

Чуть упростить...

long _f(long n, long ret)
{
        if (!n)
                return ret;
        return _f(n/2, (n%2) ? ret+1 : ret);
}

long f(long n) {return _f(n, 0)};

Второе действие: превратить хвостовую рекурсию в цикл.

long f(long n) {
  long ret = 0;
  while(n){
    if(n%2) ++ret;
    n /= 2;
  }
  return ret;
}

Чуть отполировать и убрать ветвление...

long f(long n) {
  long ret = 0;
  for(; n!=0; n>>=1) ret+=n&1;
  return ret;
}

[monster-bonster]

А нет еще более быстрой функции? Я заметил
что эта функция возвращает количество нечетных
чисел до числа n+1.

[Abstraction]

А нет еще более быстрой функции? Я заметил
что эта функция возвращает количество нечетных
чисел до числа n+1.

Чего-о-о? Для n=128 результат будет 1. Что, до 129 всего одно нечётное число? И эта функция, вообще-то, слишком быстрая, чтобы выполняться сколько-нибудь заметное время на хоть сколько-нибудь современном процессоре - так что ещё раз: как Вы меряете скорость?
Впрочем, хотите быстрее - пожалуйста:

long f(long n) {
  int ret = 0;
  static int add[] = {0, 1, 1, 2, 1, 2, 2, 3, 1, 2, 2, 3, 2, 3, 3, 4};
  for(; n!=0; n>>=4) ret+=add[n&0xF];
  return ret;
}

Можно увеличить add до 256 элементов - ускоритесь ещё в два раза, но за счёт памяти.