Java - 位操作的大O？

Question

这段代码的大O是什么？我知道所有的行都是O(1),除了递归部分.我不确定递归的大O是什么,我感觉它仍然是O(1),因为我们没有比O(1)差的行,但通常递归是O(n).

码:

public int getSum(int a, int b) {

        if (b == 0){
            return a;
        }

        if (a == 0){
            return b;
        }

        int add = a ^ b;
        int carry = (a&b) << 1;

        return getSum(add, carry);
    }

编辑:顺便说一下,这不是作业,而是为面试做好准备.

Answer 1

这个函数实际上是O(n)最坏的情况。正如上面评论中所讨论的，大 O 表示法引用了函数的渐近上限。在最坏的情况下，该函数的上限是每个输入数字都是一个max int。这意味着函数被调用的次数等于整数的位数。如果您的整数有32 bits，则该函数运行32 次，每次执行一系列常量操作。这使得函数O(n)，其中n是整数的大小。