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

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

有什么想法吗?


当前回答

这是一个C/C++解决方案,它不使用任何按位运算符,也不需要任何数学库,尽管这有点作弊。。。

double f(double n)
{
    if (n == (double)(int)n)
        return n + 0.5;
    else
        return -(n - 0.5);
}

这适用于所有32位整数,只有一个异常0x80000000(因为它的相反值不能存储在32位整数系统中)。f(f(n))==-n将始终为真,除非在这种情况下。

不过,我相信有一种更简单、更快的方法来实现它。这只是我第一个想到的。

其他回答

对于所有32位值(注意,-0是-2147483648)

int rotate(int x)
{
    static const int split = INT_MAX / 2 + 1;
    static const int negativeSplit = INT_MIN / 2 + 1;

    if (x == INT_MAX)
        return INT_MIN;
    if (x == INT_MIN)
        return x + 1;

    if (x >= split)
        return x + 1 - INT_MIN;
    if (x >= 0)
        return INT_MAX - x;
    if (x >= negativeSplit)
        return INT_MIN - x + 1;
    return split -(negativeSplit - x);
}

基本上需要将每个-x=>x=>-x循环与y=>-y=>y循环配对。所以我把裂口的两边配对。

例如,对于4位整数:

0 => 7 => -8 => -7 => 0
1 => 6 => -1 => -6 => 1
2 => 5 => -2 => -5 => 2
3 => 4 => -3 => -4 => 3

我有另一个解决方案,它可以在一半时间内工作:

def f(x):
    if random.randrange(0, 2):
        return -x
    return x

PHP,不使用全局变量:

function f($num) {
  static $mem;

  $answer = $num-$mem;

  if ($mem == 0) {
    $mem = $num*2;
  } else {
    $mem = 0;
  }

  return $answer;
}

适用于整数、浮点数和数字字符串!

只是意识到这会做一些不必要的工作,但是,不管怎样

我不知道这是否完全正确,但一个简单的标志不起作用吗?在C语言中,使用静态局部变量,我成功地做到了这一点:

int main()
{
    int n = -256; // 32-bit signed integer
    printf("%d", f(f(n)));
}

int f(int n){
    static int x = 0; // not returning negative;
    switch(x){
        case 0:
            x = 1;
            return n;
            break;

        case 1:
            x = 0;
            return -n;
            break;
        default:
            return -999;
            break;
    }
}

这适用于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的额外“位”信息的方法。