我在上次面试中遇到的一个问题是:
设计函数f,使得:f(f(n))==-n其中n是32位有符号整数;你不能用复数算术。如果你不能为整个数字范围设计这样的函数,那么就尽可能为最大范围设计它。
有什么想法吗?
我在上次面试中遇到的一个问题是:
设计函数f,使得:f(f(n))==-n其中n是32位有符号整数;你不能用复数算术。如果你不能为整个数字范围设计这样的函数,那么就尽可能为最大范围设计它。
有什么想法吗?
当前回答
f(n) { return -1 * abs(n) }
如何处理溢出问题?还是我错过了重点?
其他回答
这将在非常广泛的数字范围内发挥作用:
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,这意味着在大多数情况下这是第一次调用。如果最后一位与第二个最后一位不同,那么我假设我们在第二次调用,然后简单地重新反转最后一位。显然,对于使用最后两位的非常大的数字来说,这不起作用。但是,它再次适用于非常广泛的数字。
我可以想象,使用第31位作为虚(I)位将是一种支持一半总范围的方法。
容易的:
function f($n) {
if ($n%2 == 0) return ($n+1)*-1;
else return ($n-1);
}
根据您的平台,某些语言允许您在函数中保持状态。VB.Net,例如:
Function f(ByVal n As Integer) As Integer
Static flag As Integer = -1
flag *= -1
Return n * flag
End Function
IIRC、C++也允许这样做。我怀疑他们正在寻找不同的解决方案。
另一个想法是,由于它们没有定义函数第一次调用的结果,因此可以使用奇数/均匀度来控制是否反转符号:
int f(int n)
{
int sign = n>=0?1:-1;
if (abs(n)%2 == 0)
return ((abs(n)+1)*sign * -1;
else
return (abs(n)-1)*sign;
}
所有偶数的幅度加一,所有奇数的幅度减一。两次调用的结果大小相同,但在一次调用中,我们甚至交换了符号。在某些情况下,这不会起作用(-1,max或min int),但它的效果比迄今为止任何其他建议都要好得多。
:D
boolean inner = true;
int f(int input) {
if(inner) {
inner = false;
return input;
} else {
inner = true;
return -input;
}
}