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

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

有什么想法吗?


当前回答

这也是一个解决方案(但我们稍微改变了一下规则):

def f(n):
    if isinstance(n,int):
        return str(n)
    else:
        return -int(n)

其他回答

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(下溢)。

很简单,只需让f返回看起来等于任何整数的值,并且可以从整数转换。

public class Agreeable
{
    public static bool operator==(Agreeable c, int n)
        { return true; }

    public static bool operator!=(Agreeable c, int n)
        { return false; }

    public static implicit operator Agreeable(int n)
        { return new Agreeable(); }
}

class Program
{
    public static Agreeable f(Agreeable c)
        { return c; }

    static void Main(string[] args)
    {
        Debug.Assert(f(f(0)) == 0);
        Debug.Assert(f(f(5)) == -5);
        Debug.Assert(f(f(-5)) == 5);
        Debug.Assert(f(f(int.MaxValue)) == -int.MaxValue);
    }
}

JavaScript单行:

function f(n) { return ((f.f = !f.f) * 2 - 1) * n; }

另一种方法是将状态保持在一位,并在负数的情况下翻转它,注意二进制表示。。。限制为2^29

整数ffn(整数n){

    n = n ^ (1 << 30); //flip the bit
    if (n>0)// if negative then there's a two's complement
    {
        if (n & (1<<30))
        {
            return n;
        }
        else
        {
            return -n;
        }
    }
    else
    {
        if (n & (1<<30))
        {
            return -n;
        }
        else
        {
            return n;
        }
    }


}

C++中的另一个作弊解决方案是运算符重载。

struct func {
    int n;
    func operator()(int k) { n = -k; return *this; }
    int operator()(const func &inst) { return inst.n; }
} f;