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

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

有什么想法吗?


当前回答

对于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;
}

其他回答

int f(int x){
    if (x < 0)
        return x;
    return ~x+1; //two's complement
}

我想我会先不看别人的答案就试试这个:

#include <stdio.h>
#include <limits.h>
#include <stdlib.h>

int f(int n) {
    if(n > 0) {  
        if(n % 2)
            return -(++n);
        else {
            return (--n);

        }
    }
    else {
        if(n % 2)
            return -(--n);
        else {
            return (++n);

        }
    }
}

int main(int argc, char* argv[]) {
    int n;
    for(n = INT_MIN; n < INT_MAX; n++) {
        int N = f(f(n));

        if(N != -n) {
            fprintf(stderr, "FAIL! %i != %i\n", N, -n);
        }
    }
    n = INT_MAX;
    int N = f(f(n));
    if(N != -n) {
        fprintf(stderr, "FAIL! n = %i\n", n);
    }
    return 0;
}

输出:[无]

容易的:

function f($n) {
   if ($n%2 == 0) return ($n+1)*-1;
   else return ($n-1);
}

下面是一个简短的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是不可能的。

该问题表示“32位有符号整数”,但没有指定它们是2个补码还是1个补码。

如果使用1补码,则所有2^32值都出现在长度为4的循环中-不需要零的特殊情况,也不需要条件。

在C中:

int32_t f(int32_t x)
{
  return (((x & 0xFFFFU) << 16) | ((x & 0xFFFF0000U) >> 16)) ^ 0xFFFFU;
}

这项工作由

交换高位和低位16位块反转其中一个块

两次传递后,我们得到原始值的位逆。在一中补语表示等同于否定。

示例:

Pass |        x
-----+-------------------
   0 | 00000001      (+1)
   1 | 0001FFFF (+131071)
   2 | FFFFFFFE      (-1)
   3 | FFFE0000 (-131071)
   4 | 00000001      (+1)

Pass |        x
-----+-------------------
   0 | 00000000      (+0)
   1 | 0000FFFF  (+65535)
   2 | FFFFFFFF      (-0)
   3 | FFFF0000  (-65535)
   4 | 00000000      (+0)