Объяснение возврата по модулю

Question

Мне нужно пояснить следующий фрагмент кода:

Используется для преобразования десятичных чисел в код двоичных чисел: Это из учебника, но меня это озадачивает.

void binary(int);

void main(void) {
int number;

cout << "Please enter a positive integer: ";
cin >> number;
if (number < 0) 
    cout << "That is not a positive integer.\n";
else {
    cout << number << " converted to binary is: ";
    binary(number);
    cout << endl;
    //cin.get();
}
}

void binary(int number) {
int remainder;

if(number <= 1) {
    cout << number;
    return;
}

remainder = number%2;
binary(number >> 1);    
cout << remainder;
//cin.get();
}

Я использовал точку останова, чтобы посмотреть, как данные проходят через программу, но в конце я не могу следовать за ней.

Что я вижу:

Требуется число, и если число <= 1, оно печатает это число (0 или 1). </p>

Но прежде чем он это сделает, он сначала вычисляет модуль этого числа и помещает его в остаток. Затем он перемещается немного вправо от числа или делает то же самое, пока число не станет меньше или равно 1.

Но тогда он сохраняет «остаток cout» несколько раз (в зависимости от того, сколько там вычислено 0/1) Но как это возможно? Остаток - это буфер? (я думал, что он перезаписывается (потому что это int), но похоже, что биты добавляются, а затем печатаются несколько раз) ???

Может кто-нибудь объяснить мне это медленно?

Answer 1

int не перезаписывается, потому что он [int] перераспределяется как автоматическая переменная каждый раз, когда вы вызываете функцию binary() рекурсивно, поэтому, если вы вызываете его n раз рекурсивновы фактически выделяете n различных int с для remainder.

Таким образом, это «запоминается», потому что это разные локальные переменные.Распределение обычно производится по стеку вызовов

Как это работает: давайте посмотрим на стек примера: binary(5):

|number=5, remainder = 1|
-------------------------

Теперь вы повторно вызываете binary()с number = 5/2=2

|number=2, remainder = 0|
|number=5, remainder = 1|
-------------------------

и снова с number = 2/2 = 1 сейчас вы повторно вызываете binary() с number = 5/2=2 и получаете:

|number=1, remainder = 1|
|number=2, remainder = 0|
|number=5, remainder = 1|
-------------------------

Теперь условие останова истиннопотому что number <= 1 -, поэтому вы печатаете number [который равен 1] и извлекаете первый элемент из стека вызовов:

|number=2, remainder = 0|
|number=5, remainder = 1|
-------------------------

и печатаете 0, так как это остаток вверхустек вызовов.

и проделайте то же самое для следующего «элемента» в стеке вызовов:

|number=5, remainder = 1|
-------------------------

и выведите последний остаток: 1.

Answer 2

Поскольку binary является рекурсивной функцией, у вас происходит что-то подобное (каждый отступ является дополнительным уровнем рекурсии):

binary call #0
calculate remainder0
    recursive binary call #1
    calculate remainder #1
        recursive binary call #2
        calculate remainder #2
            recursive binary call #3
            print number
        print remainder #2
    print remainder #1
print remainder #0

Для печати используется исключительно остатки в обратном порядке расчета, как вы можете видеть выше.Не путайте с аргументом number - не имеет значения, копируется ли он при каждом рекурсивном вызове или нет.Вы могли бы также использовать глобальную переменную, и она работала бы (тогда она была бы «модифицирована на месте», что вы подразумеваете под «перезаписать»).

Важная часть заключается в том, чтодля каждого рекурсивного вызова исходный номер сдвигается на один бит вправо, и это все, что есть в аргументе number.

Вот рекурсивный эквивалент отсутствует:

#include <iostream>
#include <sstream>
#include <algorithm>

using namespace std;

string binary(int);

int main(void) {
    int number;

    cout << "Please enter a positive integer: ";
    cin >> number;
    if (number < 0)
        cout << "That is not a positive integer.\n";
    else {
        cout << number << " converted to binary is: ";
        cout << binary(number) << endl;
    }
    return 0;
}

string binary(int number) {
    stringstream ss;

    do {
        ss << number % 2;
        number >>= 1;
    } while (number >= 1);

    string s = ss.str();
    reverse(s.begin(), s.end());
    return s;
}

Answer 3

Любое число может быть записано как sum(ai*2^i), а также sum(bi*10^i).Я объясню для десятичных дробей, как это понятнее.Для получения цифр задано 12345,

, вы делаете

12345 % 10 = 5 (op1)
12345 / 10 = 1234.5 = 1234 in a int (op2)
1234 % 10 = 4 (restart)
1234 / 10 = 123.4 = 123 in a int

и т.д ...

в этом случае

op1 is equivalent to remainder = number%2; (modulo by the base)
op2 is equivalent to number >> 1; (division by the base. bitshifting is division by 2)

restartозначает перезапуск с результатом деления.Вот почему у нас есть рекурсивный вызов с использованием binary(number >> 1); Предположим, я вызываю эту функцию с abcdef в базе 2.

binary(abcdef)
  binary(abcde)
     binary(abcd)
        binary(abc)
           binary(ab)
               binary(a)
                  cout << number;//a
               cout << remainer;//b 
           cout << remainer;//c
        cout << remainer;//d
     cout << remainer;//e
  cout << remainer;//f