Что делает эта рекурсивная функция?

@BigBoss97 · Регистрация: 04.01.2017

Добрый день. Можете подсказать, что делает эта функция? Явно связана с двоичной системой, но не могу понять, что именно.

C++

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

@Herji · 14.02.2018, 21:11

BigBoss97, возвращает ((кол-во единиц в двоичной записи десятичного числа) +1)

Байт · 14.02.2018, 21:15

Кажется, подсчитывает количество единичных разрядов в двоичном представлении числа. +1.
Не самый удачный алгоритм.

@outoftime · 15.02.2018, 00:32

Сообщение от Байт

Не самый удачный алгоритм.

Согласен.

BigBoss97,

C++

std::size_t f(int n)
{
    std::size_t count = 0;
    while (n) count += n & 1, n >>= 1;
    return count + 1;
}

Хотел показать итеративный метод... всё равно как-то... калично.

@Herji · 15.02.2018, 01:01

Сообщение от outoftime

+ 1

Мне кажется +1 тут изначально - костыль

Добавлено через 23 минуты
есть же еще готовое:

C++

1
2
3

    int x = 1023;
    std::bitset<64> a(x);
    std::cout << a.count();

@outoftime · 15.02.2018, 01:12

Сообщение от Herji

Мне кажется +1 тут изначально - костыль

Как и мне, решил просто сделать как в оригинале, просто интеративно.

А на счет std::bitset это да. Можно, кстати, не объявлять переменную. Временного объекта будет достаточно.

C++

1	std::cout << std::bitset<32>(x).count();

int всё еще 32-х битный, вроде как.

Байт · 15.02.2018, 12:15

C++

count = 0;
while(n) {
  count++;
  n = n &(n-1);
}

Старый бандитский прием

Добавлено через 10 минут
Но есть и круче. См. Рейнгольд, Нивергельт, Део "Комбинаторные алгоритмы"

@GbaLog- · 15.02.2018, 12:18

Сообщение от outoftime

int всё еще 32-х битный

это зависит от платформы.
по стандарту int должен быть как минимум 16 бит.
http://en.cppreference.com/w/cpp/language/types

Байт · 15.02.2018, 12:25

Сообщение от GbaLog-

это зависит от платформы.

Скорее, от транслятора.

@Herji 299 / 208 / 174 Регистрация: 11.05.2016 Сообщений: 655
	14.02.2018, 21:11	2
	Сообщение было отмечено BigBoss97 как решение Решение BigBoss97, возвращает ((кол-во единиц в двоичной записи десятичного числа) +1) 1

Байт Диссидент 27316 / 17038 / 3765 Регистрация: 24.12.2010 Сообщений: 38,366
	14.02.2018, 21:15	3
	Кажется, подсчитывает количество единичных разрядов в двоичном представлении числа. +1. Не самый удачный алгоритм. 2

@GbaLog- Любитель чаепитий 3734 / 1793 / 563 Регистрация: 24.08.2014 Сообщений: 5,998 Записей в блоге: 1
	15.02.2018, 12:18	8
	Сообщение от outoftime int всё еще 32-х битный это зависит от платформы. по стандарту `int` должен быть как минимум 16 бит. http://en.cppreference.com/w/cpp/language/types 1

Байт Диссидент 27316 / 17038 / 3765 Регистрация: 24.12.2010 Сообщений: 38,366
	15.02.2018, 12:25	9
	Сообщение от GbaLog- это зависит от платформы. Скорее, от транслятора. 0

Опции темы

Что делает эта рекурсивная функция?

Решение