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

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

有什么想法吗?


当前回答

MIN_INT不会失败:

int f(n) { return n < 0 ? -abs(n + 1) : -(abs(n) + 1); }

其他回答

:D

boolean inner = true;

int f(int input) {
   if(inner) {
      inner = false;
      return input;
   } else {
      inner = true;
      return -input;
   }
}

我试着打高尔夫,这是罗德里克·查普曼的回答。

无分支:74个字符

int f(int i){return(-((i&1)<<1)|1)*i-(-((i>>>31)<<1)|1)*(((i|-i)>>31)&1);}

带有分支,Java风格:58个字符

int f(int i){return i==0?0:(((i&1)==0?i:-i)+(i>0?-1:1));}

带分支,C样式:52个字符

int f(int i){return i?(((i&1)?-i:i)+(i>0?-1:1)):0;}

经过快速但有效的基准测试后,分支版本在我的机器上的速度提高了33%。(正数和负数的随机数据集,足够的重复,并防止编译器在预热时优化代码。)考虑到非分支版本中的操作数量以及可能的良好分支预测,这并不奇怪,因为函数被调用了两次:f(f(i))。当我将基准更改为度量:f(I)时,分支版本只快28%。我认为这证明了分支预测在第一种情况下确实有一些好处。更多证明:当使用f(f(f)(f(i)))进行测试时,分支版本的速度会快42%。

Clojure解决方案:

(defmacro f [n]
  (if (list? n) `(- ~n) n))

也适用于任何大小的正整数和负整数、双整数和比率!

我还没有看其他答案,我假设已经彻底讨论了按位技术。

我想我会在C++中想出一些邪恶的东西,希望不会上当受骗:

struct ImplicitlyConvertibleToInt
{
    operator int () const { return 0; }
};

int f(const ImplicitlyConvertibleToInt &) { return 0; }

ImplicitlyConvertibleToInt f(int & n)
{
    n = 0; // The problem specification didn't say n was const
    return ImplicitlyConvertibleToInt();
}

整个ImplicitlyConvertableToInt类型和重载是必需的,因为临时变量不能绑定到非常量引用。

当然,现在来看它,f(n)是否在-n之前执行是不确定的。

对于这种程度的邪恶,也许一个更好的解决方案是:

struct ComparesTrueToInt
{
    ComparesTrueToInt(int) { } // implicit construction from int
};
bool operator == (ComparesTrueToInt, int) const { return true; }

ComparesTrueToInt f(ComparesTrueToInt ct) { return ComparesTrueToInt(); }

在PHP中

function f($n) {
    if(is_int($n)) {
        return (string)$n;
    }
    else {
        return (int)$n * (-1);
    }
}

我相信你能理解其他语言的这种方法的精神。为了让不使用弱类型语言的人更清楚,我明确地将其转换回int。对于某些语言,您必须重载该函数。

这个解决方案的妙处在于,无论您是从字符串还是整数开始,它都是有效的,并且在返回f(n)时不会明显改变任何内容。

在我看来,面试官在问,“这位应聘者是否知道如何标记数据以供以后操作”,以及“这位应聘人员是否知道如何在最少更改数据的情况下标记数据?”你可以使用双精度、字符串或任何其他你想使用的数据类型来实现这一点。