/*==============================================================================
  Лабораторна робота №5. Завдання 1. Варіант 19.
  Тема: рекурсивні функції.

  Умова (таблиця 5.1, варіант 19): увести ціле число n в десятковій системі
  числення з клавіатури. Перевести його у двійкову систему. Знайти кількість
  одиниць у двійковому представленні числа n, використовуючи рекурентне
  означення функції f(n), де символ & означує операцію побітового логічного
  множення:

                  | 0,                     n = 0
           f(n) = |
                  | 1 + f(n & (n - 1)),    n != 0

  Реалізувати рекурсивний та ітеративний варіанти розв'язку, порівняти
  ефективність, визначивши глибину рекурсії та кількість ітерацій циклу.

  Виконав: Одарчук Олексій, КНУ імені Тараса Шевченка, ФІТ, група ІПЗ-11.

  Компілятор: gcc -std=c17
==============================================================================*/

#include <stdio.h>

/* Глобальні лічильники характеристик виконання. Рекурсивна функція має
   відповідати рекурентному означенню з умови задачі, тому службових
   параметрів-лічильників вона не має, а лічильники оголошено глобально. */
unsigned long long g_recursiveCalls = 0; /* кількість викликів рекурсивної функції */
int g_currentDepth = 0;                  /* поточна глибина вкладеності викликів  */
int g_maxDepth = 0;                      /* максимальна досягнута глибина рекурсії */

/*------------------------------------------------------------------------------
  countBitsRecursive — кількість одиничних бітів числа за рекурентним
                       означенням f(n) з умови варіанта.

  Ідея операції n & (n - 1): віднімання одиниці інвертує наймолодший
  одиничний біт та всі нулі праворуч від нього; побітове множення з вихідним
  числом лишає всі старші біти незмінними і гасить саме цей один біт.
  Отже кожен виклик прибирає рівно одну одиницю, і кількість викликів
  дорівнює кількості одиниць. Це алгоритм Кернігана.

  Параметри: n [вхідний] — число, біти якого підраховуються.
  Повертає : кількість одиничних бітів числа n.

  Умова завершення рекурсії: n = 0 — одиничних бітів не лишилось.
  Глибина рекурсії дорівнює кількості одиниць у двійковому записі плюс один
  (завершальний виклик з n = 0).
------------------------------------------------------------------------------*/
int countBitsRecursive(unsigned int n)
{
    ++g_recursiveCalls;
    ++g_currentDepth;
    if (g_currentDepth > g_maxDepth)
        g_maxDepth = g_currentDepth;

    int result;
    if (n == 0)
        result = 0; /* умова завершення рекурсії */
    else
        result = 1 + countBitsRecursive(n & (n - 1));

    --g_currentDepth;
    return result;
}

/*------------------------------------------------------------------------------
  countBitsIterative — те саме обчислення циклом.

  Параметри:
      n          [вхідний]  — число, біти якого підраховуються;
      iterations [вихідний] — адреса лічильника ітерацій циклу.

  Повертає: кількість одиничних бітів числа n.

  Локальні змінні:
      count — накопичувана кількість одиниць;
      rest  — залишок числа з ще не погашеними одиничними бітами.
------------------------------------------------------------------------------*/
int countBitsIterative(unsigned int n, unsigned long long *iterations)
{
    int count = 0;
    unsigned int rest = n;

    *iterations = 0;

    while (rest != 0) {
        rest &= rest - 1; /* погасити наймолодший одиничний біт */
        ++count;
        ++(*iterations);
    }

    return count;
}

/*------------------------------------------------------------------------------
  printBinaryRecursive — вивести двійкове представлення числа.

  Рекурсія тут природна: молодший розряд обчислюється першим (n % 2),
  а виводитись має останнім. Рекурсивний виклик для старшої частини числа
  розміщено ДО виведення розряду, тому розряди друкуються у правильному
  порядку без використання масиву чи рядка.

  Параметри: n [вхідний] — число, що виводиться у двійковій системі.

  Умова завершення рекурсії: n = 0 — старших розрядів більше немає.
------------------------------------------------------------------------------*/
void printBinaryRecursive(unsigned int n)
{
    if (n == 0)
        return;

    printBinaryRecursive(n / 2);
    printf("%u", n % 2);
}

/*------------------------------------------------------------------------------
  Головна функція. Читає число, виводить його двійкове представлення,
  обчислює кількість одиниць двома способами та порівнює їх ефективність.

  Локальні змінні:
      n            — введене число;
      recResult    — результат рекурсивного обчислення;
      iterResult   — результат ітеративного обчислення;
      iterations   — кількість ітерацій циклу.
------------------------------------------------------------------------------*/
int main()
{
    printf("Лабораторна робота №5, завдання 1 (варіант 19)\n");
    printf("Виконав: студент групи ІПЗ-11 Одарчук Олексій\n");
    printf("Кількість одиниць у двійковому записі числа за означенням\n");
    printf("    f(n) = 0,                  якщо n = 0\n");
    printf("    f(n) = 1 + f(n & (n-1)),   якщо n != 0\n\n");

    long long input = 0;
    printf("Уведіть ціле невід'ємне число n: ");

    while (scanf("%lld", &input) != 1 || input < 0 || input > 4294967295LL) {
        if (feof(stdin)) {
            printf("\nВхідні дані вичерпано.\n");
            return 1;
        }
        int c;
        /* очищення буфера клавіатури */
        while ((c = getchar()) != '\n' && c != EOF) {
        }
        printf("Помилка: потрібне ціле число від 0 до 4294967295. Повторіть: ");
    }

    const unsigned int n = (unsigned int)input;

    printf("\nЧисло у десятковій системі: %u\n", n);
    printf("Число у двійковій системі:  ");
    if (n == 0)
        printf("0");
    else
        printBinaryRecursive(n);
    printf("\n");

    /* Рекурсивний варіант. */
    g_recursiveCalls = 0;
    g_currentDepth = 0;
    g_maxDepth = 0;
    const int recResult = countBitsRecursive(n);

    /* Ітеративний варіант. */
    unsigned long long iterations = 0;
    const int iterResult = countBitsIterative(n, &iterations);

    printf("\nРезультат\n");
    printf("  Кількість одиниць (рекурсія):  %d\n", recResult);
    printf("  Кількість одиниць (ітерація):  %d\n", iterResult);
    printf("  Результати %s\n",
           recResult == iterResult ? "збігаються" : "РОЗБІГАЮТЬСЯ — помилка");

    printf("\nПорівняння ефективності\n");
    printf("  Викликів рекурсивної функції: %llu\n", g_recursiveCalls);
    printf("  Глибина рекурсії:             %d\n", g_maxDepth);
    printf("  Ітерацій циклу:               %llu\n", iterations);

    return 0;
}