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

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

有什么想法吗?


当前回答

这个Perl解决方案适用于整数、浮点数和字符串。

sub f {
    my $n = shift;
    return ref($n) ? -$$n : \$n;
}

尝试一些测试数据。

print $_, ' ', f(f($_)), "\n" for -2, 0, 1, 1.1, -3.3, 'foo' '-bar';

输出:

-2 2
0 0
1 -1
1.1 -1.1
-3.3 3.3
foo -foo
-bar +bar

其他回答

下面是一个简短的Python答案:

def f(n):
  m = -n if n % 2 == 0 else n
  return m + sign(n)

一般情况

稍微调整一下上面的内容就可以处理我们希望k个自调用否定输入的情况——例如,如果k=3,这意味着g(g(g)n))=-n:

def g(n):
  if n % k: return n + sign(n)
  return -n + (k - 1) * sign(n)

这是通过将0保留在适当位置并创建长度为2*k的循环来实现的,因此,在任何循环中,n和-n之间的距离为k。具体来说,每个周期如下:

N * k + 1, N * k + 2, ... , N * k + (k - 1), - N * k - 1, ... , - N * k - (k - 1)

或者,为了更容易理解,这里是k=3的示例循环:

1, 2, 3, -1, -2, -3
4, 5, 6, -4, -5, -6

这组循环最大化了在任何以零为中心的机器类型(如有符号int32或有符号int64类型)内工作的输入范围。

兼容范围分析

映射x->f(x)实际上必须形成长度为2*k的循环,其中x=0是特殊情况下的1-长度循环,因为-0=0。因此,一般k的问题是可解的,当且仅当输入-1(补偿0)的范围是2*k的倍数,并且正负范围是相反的。

对于有符号整数表示,我们总是有一个最小的负数,在该范围内没有正的对应项,因此该问题在整个范围内变得不可解决。例如,有符号字符的范围为[-128127],因此在给定范围内f(f(-128))=128是不可能的。

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

    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,这意味着在大多数情况下这是第一次调用。如果最后一位与第二个最后一位不同,那么我假设我们在第二次调用,然后简单地重新反转最后一位。显然,对于使用最后两位的非常大的数字来说,这不起作用。但是,它再次适用于非常广泛的数字。

上述问题不要求函数只能接受32位整数,只要求给定的n是32位整数。

红宝石:

def f( n )
  return 0 unless n != 0 
  ( n == n.to_i ) ? 1.0 / n : -(n**-1).to_i
end

这很简单!

每个数字以4为周期映射到另一个数字,其中所需条件成立。

例子:

规则如下:

0→ 0±2³¹ → ±2³¹古怪的→ 甚至,甚至→ -奇数:对于所有k,0<k<2³⁰: (2k-1)→ (2k)→ (-2k+1)→ (-2k)→ (2k-1)

唯一不匹配的值是±(2³¹-1),因为只有两个。必须有两个不能匹配,因为在二进制补码系统中只有四个数字的倍数,其中0和±2³¹已被保留。

在一的补码系统中,存在+0和-0。我们开始了:

对于所有k,0<k<2³⁰: (+2k)→ (+2k+1)→ (-2k)→ (-2k-1)→ (+2k)

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

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