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

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

有什么想法吗?


当前回答

这适用于1073741823至1073741822范围:

int F(int n)
{
    if(n < 0)
    {
        if(n > -1073741824)
            n = -1073741824 + n;
        else n = -(n + 1073741824);
    }
    else
    {
        if(n < 1073741823)
            n = 1073741823 + n;
        else n = -(n - 1073741823);
    }
    return n;
}

它的工作原理是获取32位有符号整数的可用范围并将其一分为二。函数的第一次迭代将n自身置于该范围之外。第二次迭代检查它是否在该范围之外-如果是,则将其放回该范围内,但使其为负值。

这实际上是一种保留关于值n的额外“位”信息的方法。

其他回答

对于javascript(或其他动态类型语言),可以让函数接受int或对象,并返回另一个。即

function f(n) {
    if (n.passed) {
        return -n.val;
    } else {
        return {val:n, passed:1};
    }
}

js> f(f(10))  
-10
js> f(f(-10))
10

或者,您可以在强类型语言中使用重载,尽管这可能会破坏规则

int f(long n) {
    return n;
}

long f(int n) {
    return -n;
}

我认为最大的可能范围是暗示模块化算术解决方案。在一些模基M中,有一个数,当平方等于M-1(等于-1)。例如,如果M=13,5*5=25,25 mod 13=12(=-1)总之,这里有一些M=2**32-3的python代码。

def f(x):
    m=2**32-3;
    halfm=m//2;
    i_mod_m=1849436465
    if abs( x ) >halfm:
        raise "too big"
    if x<0:
        x+=m
    x=(i_mod_m*x) % m
    if (x>halfm):
        x-=m
    return x;

注意,有3个值不适用于2**31-1、-(2**31-1)和-(2*#31)

int j = 0;

void int f(int n)
{    
    j++;

    if(j==2)
    {
       j = 0;
       return -n;
    }

    return n;
}

:D

适用于n=[0..2^31-1]

int f(int n) {
  if (n & (1 << 31)) // highest bit set?
    return -(n & ~(1 << 31)); // return negative of original n
  else
    return n | (1 << 31); // return n with highest bit set
}

这将在非常广泛的数字范围内发挥作用:

    static int f(int n)
    {
        int lastBit = int.MaxValue;
        lastBit++;
        int secondLastBit = lastBit >> 1;
        int tuple = lastBit | secondLastBit;
        if ((n & tuple) == tuple)
            return n + lastBit;
        if ((n & tuple) == 0)
            return n + lastBit;
        return -(n + lastBit);
    }

我最初的方法是使用最后一位作为检查位,以了解我们在第一次或第二次调用中的位置。基本上,我会在第一次调用后将此位设置为1,以向第二次调用发出第一次调用已经通过的信号。但是,这种方法被负数所击败,负数的最后一位在第一次调用期间已经到达1。

同样的理论适用于大多数负数的倒数第二位。但是,通常发生的情况是,大多数情况下,最后一位和第二位是相同的。它们要么都是负数的1,要么都是正数的0。

所以我的最后一个方法是检查它们是否都是1或都是0,这意味着在大多数情况下这是第一次调用。如果最后一位与第二个最后一位不同,那么我假设我们在第二次调用,然后简单地重新反转最后一位。显然,对于使用最后两位的非常大的数字来说,这不起作用。但是,它再次适用于非常广泛的数字。