我在上次面试中遇到的一个问题是:
设计函数f,使得:f(f(n))==-n其中n是32位有符号整数;你不能用复数算术。如果你不能为整个数字范围设计这样的函数,那么就尽可能为最大范围设计它。
有什么想法吗?
我在上次面试中遇到的一个问题是:
设计函数f,使得:f(f(n))==-n其中n是32位有符号整数;你不能用复数算术。如果你不能为整个数字范围设计这样的函数,那么就尽可能为最大范围设计它。
有什么想法吗?
当前回答
使用问题中给出的信息,您可以
从2-完成转换为符号位表示如果设置了最后一位,则翻转符号位和最后一位;否则,只翻转最后一位转换回2-完成。
所以你基本上是奇数->偶数->奇数或偶数->奇数->偶数,只对偶数更改符号。唯一不适用的数字是-2^31
代码:
function f(x) {
var neg = x < 0;
x = Math.abs(x) ^ 1;
if (x & 1) {
neg = !neg;
}
return neg ? -x : x;
}
其他回答
这个问题并没有说明函数f的输入类型和返回值必须是什么(至少不是你给出的方式)。。。
…只是当n是32位整数时,f(f(n))=-n
那么,怎么样
Int64 f(Int64 n)
{
return(n > Int32.MaxValue ?
-(n - 4L * Int32.MaxValue):
n + 4L * Int32.MaxValue);
}
如果n是32位整数,则语句f(f(n))==-n将为真。
显然,这种方法可以扩展到更大范围的数字。。。
目标-C
这适用于除“-1”以外的所有数字。
如果要从使用int转换为使用NSInt,那么可以将-1值设置为NULL,然后第二次将它们转换为+1,但我觉得NSInt欺骗了询问者的意图。
f(n):
-(int)f:(int)n {
if (abs(n)==1) {
n = -1;
} else {
if (abs(n)%2) {//o
if (n>0) {//+
n--;
n*=+1;
} else if (n<0) {//-
n++;
n*=+1;
}
} else {//e
if (n>0) {//+
n++;
n*=-1;
} else if (n<0) {//-
n--;
n*=-1;
}
}
}
return n;
}
当然,这一切都可以缩短为一行,但其他人可能无法阅读。。。
无论如何,我将BOOLEAN逻辑存储为奇数或偶数的状态。
我有另一个解决方案,它可以在一半时间内工作:
def f(x):
if random.randrange(0, 2):
return -x
return x
本质上,函数必须将可用范围划分为大小为4的循环,其中-n位于n循环的另一端。但是,0必须是大小为1的循环的一部分,否则0->x->0->x!=-x.因为0是单独的,所以在我们的范围内必须有3个其他值(其大小是4的倍数)不在具有4个元素的正确循环中。
我选择这些额外的奇怪值为MIN_INT、MAX_INT和MIN_INT+1。此外,MIN_INT+1将正确映射到MAX_INT,但会被卡在那里而不能映射回来。我认为这是最好的妥协,因为它有一个很好的特性,即只有极端值不能正常工作。此外,这意味着它将适用于所有BigInt。
int f(int n):
if n == 0 or n == MIN_INT or n == MAX_INT: return n
return ((Math.abs(n) mod 2) * 2 - 1) * n + Math.sign(n)
return x ^ ((x%2) ? 1 : -INT_MAX);