面试中代码片段的困惑

Question

我在一次面试中被问到下面这段代码的作用。

class Case {

    static int count1(int n) {
        if (n == 0) {
            return 0;
        }
        int m = n / 2;
        if (2 * m != n) {
            return 1 + count1(m);
        }
        return count1(m);
    }

    static int count0(int n) {
        if (n == 0) {
            return 1;
        }
        if (n == 1) {
            return 0;
        }
        int m = n % 2;
        return count0((n - m) / 2) + 1 - m;
    }

    static boolean equivalent(int n, int m) {
        return ((count1(n) == count1(m)) && (count0(n) == count0(m)));
    }
}

首先，我得提一下，这个工作是数据分析实习，要求的编程语言只有Python，而我是一名物理专业的学生，所以对我来说，“//”和“/”的区别很大。

我们先来看一下函数 count1。我当时真的觉得这是个陷阱问题，因为 int(2*m != n) 可能会导致值错误（我错了，因为我已经被多次提醒过在物理中“//”和“/”的区别，我完全忘记了在其他语言中“7”可以用来进行整数除法，并返回向下取整的结果。所以我傻傻地以为这是个陷阱问题，立刻指出这可能会出现错误信息，并且 if(2*m !=n) 可能是多余的。

现在让我真正困惑的是 count0，第二个函数。我简单地指出这个程序没有解决任何问题，没有规律可言。面试官说它应该返回0或1，但如果要返回0或1，那应该是 count0((n-m/2+1-m)，也就是说每个项都应该在括号里面，对吧？

这次面试是在昨晚进行的。我应该写信给面试官，告诉他虽然我没能回答第一个函数的作用是我的错，但你的第二个函数可能有逻辑错误吗？当然要用更礼貌的方式。

附言：ChatGPT告诉我这段代码是Java，所以我加上了“java”标签。

正如我在上面所解释的。

我意识到我可能搞错了第一个函数，不过这是用Python测试的结果：

# Implementing count0 function as described in the pseudocode
def count0(n):
    if n == 0:
        return 1
    if n == 1:
        return 0
    m = n % 2
    return count0((n - m) // 2) + 1 - m

# We will calculate the values of count0 for n = 0 to 20
results_count0 = {n: count0(n) for n in range(21)}

results_count0

结果：

{0: 1, 1: 0, 2: 1, 3: 0, 4: 2, 5: 1, 6: 1, 7: 0, 8: 3, 9: 2, 10: 2, 11: 1, 12: 2, 13: 1, 14: 1, 15: 0, 16: 4, 17: 3, 18: 3, 19: 2, 20: 3}

Answer 1

如果源代码是正确的（也就是说，和你问题中的文字有关，而不是纸上的照片）：

Case.count1(n) 这个方法用来计算数字 n 在二进制补码表示中有多少个1。这和 Integer.bitCount(n) 是一样的。

Case.count0(n) 这个方法用来计算数字 n 在二进制补码表示中有多少个重要的零位。这里的“重要”是指只计算那些在最高位1的右边的零位。你也可以用 Integer.bitCount((Integer.highestOneBit(n)<<1)-1-n) 来计算这个。

面试官说这个方法应该返回0或1

不过，count0 的结果并不只有这些，输入为0时，结果是1，这个情况需要单独处理，因为输入0没有任何1位，但仍然有一个重要的0位，那就是最低位。

Case.equivalent(m, n) 这个方法用来检查两个整数 m 和 n 的1位和0位的数量是否相同，所以 Case.equivalent(1, 2) 会返回 true。

关于 / 和 // 的区别：在Java中，/ 可以用作整数和浮点数的除法运算符，而 // 是用来标记行注释的，所以它根本不是一个运算符。

Answer 2

对于喜欢代码的人来说（代码就是真理！），这里有一个更好的版本。

这是Java 14及以上版本的代码，如果你本地没有工具，可以在一些免费的在线Java控制台上试试。

另外，对于那些对细节感兴趣的人，可以查看整数序列在线百科全书：

• count0() 生成序列 A023416：n的二进制表示中0的数量。
• count1() 生成序列 A000120：1的计数序列：n的二进制表示中1的数量（或者说n的二进制权重）

package org.example;

public class Sequence {

    static int count1(int n) {
        if (n == 0) {
            return 0;
        }
        int m = n / 2;
        if (2 * m != n) {
            return 1 + count1(m);
        }
        return count1(m);
    }

    static int count1_better(int n) {
        if (n == 0) {
            return 0;
        }
        else {
            int leastSignificantBit = n%2;
            int shiftedRight = n/2; // or use n>>1, whatever
            return leastSignificantBit + count1_better(shiftedRight);
        }
    }

    static int count0(int n) {
        if (n == 0) {
            return 1;
        }
        if (n == 1) {
            return 0;
        }
        int m = n % 2;
        return count0((n - m) / 2) + 1 - m;
    }

    static int count0_better(int n) {
        return switch (n) {
            case 0 -> 1;
            case 1 -> 0;
            default -> {
                int leastSignificantBit = n%2;
                int leastSignificantBitInverted = (1 - leastSignificantBit);
                // the original (n - m) / 2 is really for fractionals
                int shiftedRight = n/2; // or use n>>1, whatever
                yield leastSignificantBitInverted + count0_better(shiftedRight);
            }
        };
    }

    public static void main(String[] argv) throws Exception {
        final int limit = 10000;
        for (int i=0;i<limit;i++) {
            System.out.printf("%10s: zeros: %3d, ones: %3d\n",
                Integer.toBinaryString(i),
                count0_better(i),
                count1_better(i)
            );
            if (count1(i) != count1_better(i)) {
                throw new Exception("count1() and count1_better() differ at " + i);
            }
            if (count0(i) != count0_better(i)) {
                throw new Exception("count0() and count0_better() differ at " + i);
            }
        }
    }

}

所以：

         0: zeros:   1, ones:   0
         1: zeros:   0, ones:   1
        10: zeros:   1, ones:   1
        11: zeros:   0, ones:   2
       100: zeros:   2, ones:   1
       101: zeros:   1, ones:   2
       110: zeros:   1, ones:   2
       111: zeros:   0, ones:   3
      1000: zeros:   3, ones:   1
      1001: zeros:   2, ones:   2
...

Answer 3

如果你看看一些例子，就能发现其中的规律：

输入数字	输入数字的二进制表示	count0()的结果	count1()的结果
0	0	1	0
1	1	0	1
2	10	1	1
3	11	0	2
4	100	2	1
7	111	0	3
8	1000	3	1
10	1010	2	2