我理解下面快照中的代码是如何工作的，但我很好奇，我怎么知道它的时间和空间复杂度呢？
我知道这取决于b变成0所需的时间。有什么数学方法可以找到这个吗？
我知道这不会导致数百万次的递归。但还是很好奇会发生多少次递归？
问题：
不使用任何算术运算添加2个数字-
最佳答案
因为进位是a&b左移，所以它的位-0（最低有效位或LSB）为零此外，进位在每个位置p都有0，而b在位置p-1有0。这意味着在第一个递归调用中，b将有一个0位-0，在第二个递归调用中，b将有一个0位-0和1位（2个lsb为0），依此类推。在第n次递归调用中，b将有n个lsb为0，因此当n是a中最重要的非零位的位置时，进位将为0，递归将在下一次调用中结束。
因此，时间复杂度是O（n），其中n是A中的位的数目（更准确地说，A中最重要的非零位的位置，在最坏的情况下是A中的比特数）。空间复杂度也是O（n），因为有N个递归调用，但是由于这是尾递归，所以它可以被优化掉，因此优化的空间复杂度将是O（1）。