我在上次面试中遇到的一个问题是:

设计函数f,使得:f(f(n))==-n其中n是32位有符号整数;你不能用复数算术。如果你不能为整个数字范围设计这样的函数,那么就尽可能为最大范围设计它。

有什么想法吗?


当前回答

使用复数,您可以有效地将否定数字的任务分为两个步骤:

将n乘以i,得到n*i,n逆时针旋转90°再乘以i,得到-n

最棒的是,您不需要任何特殊的处理代码。只要乘以i就可以了。

但不允许使用复数。因此,您必须使用部分数据范围创建自己的虚拟轴。由于需要的虚(中间)值与初始值一样多,因此只剩下一半的数据范围。

我试图在下图中显示这一点,假设有符号的8位数据。您必须将其缩放为32位整数。初始n的允许范围为-64到+63。下面是函数对正n的作用:

如果n在0..63(初始范围)内,函数调用将添加64,将n映射到范围64..127(中间范围)如果n在64..127(中间范围)内,则函数从64中减去n,将n映射到范围0..-63

对于负n,函数使用中间范围-65..-128。

其他回答

我可以想象,使用第31位作为虚(I)位将是一种支持一半总范围的方法。

我的答案是正确的。。。50%的时间,所有的时间。

int f (int num) {
    if (rand () / (double) RAND_MAX > 0.5)
         return ~num + 1;
    return num;
}

在C中,

int 
f(int n) {
     static int r = 0;
     if (r == 1) {r--; return -1 * n; };
     r++;
     return n;
}

知道这是为了什么语言会有帮助。我错过了什么吗?许多“解决方案”似乎过于复杂,坦率地说,并非如此工作(当我读到问题时)。

没有人说它必须是无国籍的。

int32 f(int32 x) {
    static bool idempotent = false;
    if (!idempotent) {
        idempotent = true;
        return -x;
    } else {
        return x;
    }
}

作弊,但不如很多例子。更糟糕的是,查看堆栈以查看调用者的地址是否为-f,但这将更具可移植性(虽然不是线程安全的……线程安全版本将使用TLS)。更邪恶的是:

int32 f (int32 x) {
    static int32 answer = -x;
    return answer;
}

当然,对于MIN_INT32的情况,这两种方法都不太有效,但除非允许返回更宽的类型,否则对此您几乎无能为力。

MIN_INT不会失败:

int f(n) { return n < 0 ? -abs(n + 1) : -(abs(n) + 1); }