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

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

有什么想法吗?


当前回答

由于C++中的重载:

double f(int var)
{
 return double(var);
} 

int f(double var)
{
 return -int(var);
}

int main(){
int n(42);
std::cout<<f(f(n));
}

其他回答

C#表示2^32-1个数字的范围,所有整数32(int32.MinValue除外)

    Func<int, int> f = n =>
        n < 0
           ? (n & (1 << 30)) == (1 << 30) ? (n ^ (1 << 30)) : - (n | (1 << 30))
           : (n & (1 << 30)) == (1 << 30) ? -(n ^ (1 << 30)) : (n | (1 << 30));

    Console.WriteLine(f(f(Int32.MinValue + 1))); // -2147483648 + 1
    for (int i = -3; i <= 3  ; i++)
        Console.WriteLine(f(f(i)));
    Console.WriteLine(f(f(Int32.MaxValue))); // 2147483647

打印:

2147483647
3
2
1
0
-1
-2
-3
-2147483647

从来没有人说过f(x)必须是同一类型。

def f(x):
    if type(x) == list:
        return -x[0]
    return [x]


f(2) => [2]
f(f(2)) => -2

这个想法已经在其他答案中使用过,但我把它融入了Python的一行:

def f(n):
    return str(n) if type(n) == int else -int(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的情况,这两种方法都不太有效,但除非允许返回更宽的类型,否则对此您几乎无能为力。

x86 asm(AT&T风格):

; input %edi
; output %eax
; clobbered regs: %ecx, %edx
f:
    testl   %edi, %edi
    je  .zero

    movl    %edi, %eax
    movl    $1, %ecx
    movl    %edi, %edx
    andl    $1, %eax
    addl    %eax, %eax
    subl    %eax, %ecx
    xorl    %eax, %eax
    testl   %edi, %edi
    setg    %al
    shrl    $31, %edx
    subl    %edx, %eax
    imull   %ecx, %eax
    subl    %eax, %edi
    movl    %edi, %eax
    imull   %ecx, %eax
.zero:
    xorl    %eax, %eax
    ret

代码已检查,所有可能的32位整数都已通过,错误为-2147483647(下溢)。