将十进制转换为二进制的函数，由三行组成，需要解释。

Question

我希望您能准确解释以下函数。

void ToBin(int n){
  if (n>1)
     ToBin( n/2 );
  printf( "%d", n%2 );
}

例如：
如果我输入 7，将其转换为二进制数 111，该函数会如何运作（行为）。

请给出逐步解释以便我能够理解。

---

编辑：
同一函数但打印结果更清晰。

void ToBin( int n ){
   printf("%d/2= %d -> %d\n", n, n/2 ,n%2);
   if (n>1)
      ToBin( n/2 );
}

- Lion King

---

请谷歌如何将数字转换为布尔值，并尝试将这些步骤与您的ToBin方法进行比较......通过自己的理解，您将会更好地理解。您是否对ToBin中的ToBin调用（递归）感到困惑？ - Nitin Agrawal

@Nitin Agrawal：我知道标准数学的方法，但我不知道如何用编程来实现。 - Lion King

这就是为什么在我的评论中我问你是否对ToBin内部的调用感到困惑......尝试阅读有关递归函数的内容，而且还有很多答案可以帮助你更详细地理解你的原始问题...愉快的编程... :-) - Nitin Agrawal

Answer 1

特别是在n = 7的情况下：

首先，n = 7，因此n > 1。因此，再次对n / 2 = 3调用ToBin。

现在，n = 3，因此n > 1。因此，再次对n / 2 = 1调用ToBin。

现在，n = 1，因此n不大于1。因此，打印1％2 = 1，并将控件跳回到上一个框架。

这里，n = 3，且打印3％2 = 1，控制再次跳回到上一帧。

这里，n = 7，且打印7％2 = 1，由于函数已离开且没有更多的ToBin框架，因此控制返回最初调用ToBin的函数。

一般来说，该函数的工作原理如下：

一个数字的二进制表达式等于该数字的一半向下取整的二进制表达式，附加原始数字的最低位。

因此，该函数重复获取输入数值的一半向下取整的二进制表达式，直到该值为单个位。然后，打印该位，作为数字的最高有效位，并随后依次按重要性降序打印每个位。

- qaphla

---

在这一行中，“现在，n = 1，因此n不大于1。因此，打印1％2 = 1，并且控制跳回到上一个框架。”是什么导致它再次跳回到函数的开头。 - Lion King

它不会跳回函数的开头。一旦内部调用ToBin完成，执行就会简单地继续在较早的ToBin调用中进行。也就是说，在内部ToBin（其中n = 1）完成后，下一行运行的是printf（其中n = 3），因为可以将内部ToBin视为在n = 3时被调用的所有行都在运行，而这本身又在n = 7时被调用的行上运行。 - qaphla

抱歉，但我想知道为什么在这个条件中我们使用 if (n>1)，为什么是特别的 1？ - Lion King

如果该条件不成立，则（假设原始输入是正整数--请注意，此函数不适用于负数）n = 0或n = 1，因此只需打印n即可，因为0和1都可以用与其十进制表示相同的1位字符串表示二进制。 - qaphla

Answer 2

这是一个递归函数调用。n%2基本上只是剪掉整数的最后一位（二进制表示）。（2是因为二进制是基于2的，所以有两个可能的基础数字）。n/2通过整数除法删除最低有效位，并将其传递给下一个递归级别。

因此，每个递归级别都会修剪它所传递的整数的最低有效位，直到在某个级别上该整数不等于1。如果它等于1，则if失败，不再进行递归调用。现在递归回滚。首先执行最后一次递归调用的printf，它将打印由调用者传递的整数的最低有效位。因此，在级别k，将基本上打印第k 位数字。因为在k级别上，经过递归函数调用链上的前k-1个最低有效位已被移除，而在级别k处的调用已使用已删除了k-1个最低有效位的整数。因此，在每个级别上，printf将打印它所传递的整数的最低有效位，直到递归回滚到顶部。

这是一个n = 10的图形表示。然后n的二进制是1010。尝试使用不同的值自己绘制这样的图表，以获得更好的理解。

          ToBin (10 = 1010)          print 10%2 = 0
             |                           ^
             call ToBin (10/2)           |
             |                           |
             V                           |
          ToBin (5 = 101)            print 5%2 = 1
             |                           ^
             call ToBin (5/2)            |
             |                           |
             V                           |
          Tobin (2 = 10)             print 2%2 = 0
             |                           ^
             call ToBin (2/2)            |
             |                           |
             V                           |
          ToBin (1 = 1)              print 1%2 = 1
             |                           ^
             if condition fails,         |
             |  roll back.               |
             |                           |
             |                           |
             +------>------>------>------+

- phoxis

Answer 3

order    call    print
  1    ToBin(7)    1
          ↓        ↑
  2    ToBin(3)    1
          ↓        ↑
  3    ToBin(1) →  1

那是递归。

也许你应该找到它的递归方程。

- SubmarineX

Answer 4

为了找到一个数的二进制表示，我们需要寻找位b0…bn，使得:

n = bn * 2^n + b_(n - 1) * 2^(n - 1) + ... + b1 * 2^1 + b0 * 2^0

现在我们专注于寻找b0, b1, ..., bn。请注意，

(bn * 2^n + b_(n - 1) * 2^(n - 1) + ... + b1 * 2^1 + b0 * 2^0) % 2 = b0

因为 b0 * 2^0 % 2 = b0，而当 j >= 1 时，bj * 2^j % 2 = 0，因为当 j >= 1 时，2^j % 2 = 0。所以，

       n = bn * 2^n + b_(n - 1) * 2^(n - 1) + ... + b1 * 2^1 + b0 * 2^0 
=> n % 2 = (bn * 2^n + b_(n - 1) * 2^(n - 1) + ... + b1 * 2^1 + b0 * 2^0) % 2 = b0

我们发现 b0 = n % 2。这是关键事实之一。

现在，让我们除以2：

n / 2 = (bn * 2^n + b_(n - 1) * 2^(n - 1) + ... + b1 * 2^1 + b0 * 2^0)
      = bn * 2^(n - 1) + b_(n - 1) * 2^(n - 2) + ... + b1 * 2^1

现在，我们先停下来。仔细观察一下 n / 2 的二进制表示。注意到它与 n 的二进制表示完全相同，只是最后一位被去掉了。也就是说：

    n = bn b_(n-1) ... b1 b0
n / 2 =   b_n b_(n-1) ... b1

这是关键事实2.

因此，让我们总结一下我们所学到的内容。

1. n的二进制表示是n/2的二进制表示加上n的二进制表示的最后一位数字。 这来自于关键事实2。

2. n的二进制表示的最后一位数字可以通过计算n%2来得到。 这来自于关键事实1。

所有这些都是正确的，除了一个情况：当n=0时。在这种情况下，n的二进制表示是0。如果我们尝试使用除以2的规则，我们将永远不会停止除以2。因此，我们需要一条规则来捕捉n=0的情况。

因此，为了计算n的二进制表示，首先计算n/2的二进制表示，然后附加n%2的结果，但一定要处理n=0的情况。让我们把它写成代码:

// print binary representation of n
void ToBin(int n) {
    if(n > 1) { // this is to handle zero!
        ToBin(n / 2); // this will print the binary representation of n
    }
    print(n % 2); // this will print the the last digit
}

- jason

Answer 5

你输入了7，所以

call 1) 7>1 true ,call ToBin(7/2)=ToBin(3.5) , pending print(7%2)=1
call 2) 3>1 true ,call ToBin(3/2)=ToBin(1.5) , pending print(3%2)=1
call 3) 1>1 false ,dont call ToBin(1/2), print(1%2)=1

,

print 1
pop function activation record for call 3)
pending print 1
pop function activation record for call 2)
pending print 1
pop function activation record for call 1)
So your output is 111

- user2408578

Answer 6

递归可能会使其比本来更难理解。首先，请注意，如果我们重新排列语句：

void ToBin(int n){
  printf( "%d", n%2 );
  if (n>1)
     ToBin( n/2 );
}

现在它将以相反的顺序打印数字。当然，这不是你想要的，但现在递归调用在末尾，更容易转换为迭代形式：

void ToBin(int n) {
  do {
    printf( "%d", n%2 );
    n = n/2;
  } while(n > 1);
}

从这段代码中，您可以看到：

• 打印数字模二的余数。
• 将数字除以二。
• 如果数字大于1，则重复。

考虑到给定一个十进制数，我们可以除以10。余数和被除数分别是最低有效位和数字向左移动一位。对于二进制也是如此：不过，我们除以二而不是除以10。

因此，该算法基本上是这样的：

• 打印最低有效位。
• 将数字向左移动一位。
• 如果数字大于1，则重复。

如果您将其以递归形式编写，然后交换递归和打印，则可以按从最高有效位到最低有效位的顺序打印数字。完成。

- icktoofay

Answer 7

ToBin(7)
n=7 if(7>1)
    ToBin(7/2=3) call ToBin(3)
    {
     ToBin(3)
     n=3 if(3>1)
     ToBin(3/2=1) call ToBin(1)
     {
       ToBin(1)
       n=1 if(1>1)
         false
       print n%2=> 1%2= 1
      }     
    print n%2=> 3%2= 1
    }
print n%2=> 7%2= 1

- EnterKEY

Answer 8

这是关于编程的内容，以下是按照2进制来进行余数（%操作）递归打印的方式

ToBin() 函数会调用自身，直到输入参数 n 大于1为止。

 2 | 7
 ------     remainder   /|\
 2 | 3  ---> 1           |    down to top
 ------                  |
   | 1  ---> 1           |
     -------------------->

- P0W

Answer 9

如果 n 是 7，则每个层级的递归调用为：

 1.ToBin(7)--> 2. ToBin(3) --> 3. ToBin(1)

现在返回值已经发生，第一种情况下为1，因为7%2等于1，

第二种情况下也是1，因为3%2等于1，第三种情况下同样为1，因为1%2等于1。

因此，111是输出结果。

注意：每个递归调用都有自己的n，在其堆栈中，因此第一次调用中的n为7，第二次为3，第三次为1。

- Raju

Answer 10

ToBin函数使用递归（调用自身）和this algorithm：

将十进制整数转换为二进制等效形式，需要将该数字除以二，余数即为最低有效位。再次将（整数）结果除以二，其余数是下一个最低有效位。此过程重复，直到商变为零。

- Yu Hao