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

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

有什么想法吗?


当前回答

int func(int a)  
{   
    static int p = 0;  
    int ret = a;  

    if ( p ) ret *= -1;  
    p ^= 1;  

    return ret;  
}  

其他回答

f#中的简单解决方案(不使用“技巧”)

let rec f n =
    if n = 0 then 0
    elif n > 0 then
        if (f (n - 1) <> n) then n + 1
        else -(n - 1)
    else
        if (f (-(n - 1)) = n) then n - 1
        else -(n + 1) 

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

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的情况,这两种方法都不太有效,但除非允许返回更宽的类型,否则对此您几乎无能为力。

Scala中使用隐式转换的一个奇怪且唯一稍微聪明的解决方案:

sealed trait IntWrapper {
  val n: Int
}

case class First(n: Int) extends IntWrapper
case class Second(n: Int) extends IntWrapper
case class Last(n: Int) extends IntWrapper

implicit def int2wrapper(n: Int) = First(n)
implicit def wrapper2int(w: IntWrapper) = w.n

def f(n: IntWrapper) = n match {
  case First(x) => Second(x)
  case Second(x) => Last(-x)
}

我认为这不是一个很好的主意。

我相信这符合所有要求。没有什么规定参数必须是32位有符号整数,只有你传入的值“n”是。

long long f(long long n)
{
    int high_int = n >> 32;
    int low_int  = n & 0xFFFFFFFF;

    if (high_int == 0) {
        return 0x100000000LL + low_int;
    } else {
        return -low_int;
    }
}

以下情况如何:

int f (int n)
{
    static bool pass = false;
    pass = !pass;
    return pass? n : -n;
}