我在上次面试中遇到的一个问题是:
设计函数f,使得:f(f(n))==-n其中n是32位有符号整数;你不能用复数算术。如果你不能为整个数字范围设计这样的函数,那么就尽可能为最大范围设计它。
有什么想法吗?
我在上次面试中遇到的一个问题是:
设计函数f,使得:f(f(n))==-n其中n是32位有符号整数;你不能用复数算术。如果你不能为整个数字范围设计这样的函数,那么就尽可能为最大范围设计它。
有什么想法吗?
当前回答
C函数:
int f(int n) /* Treats numbers in the range 0XC0000000 to 0X3FFFFFFF as valid to
generate f(f(x)) equal to -x. If n is within this range, it will
project n outside the range. If n is outside the range, it will
return the opposite of the number whose image is n. */
{
return n ? n > 0 ? n <= 0X3FFFFFFF ? 0X3FFFFFFF + n : 0X3FFFFFFF - n :\
n >= 0XC0000000 ? 0XC0000000 + n : 0XC0000000 - n : 0;
}
Ideone测试和下载链接
其他回答
f(n) { return -1 * abs(n) }
如何处理溢出问题?还是我错过了重点?
使用问题中给出的信息,您可以
从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;
}
这里有一个我从未见过的变体。因为这是ruby,所以32位整数的东西就不见了(当然可以添加检查)。
def f(n)
case n
when Integer
proc { n * -1 }
when Proc
n.call
else
raise "Invalid input #{n.class} #{n.inspect}"
end
end
(-10..10).each { |num|
puts "#{num}: #{f(f(num))}"
}
我承认我会作弊,但还是符合要求。这是编程魔术,而不是数学。它适用于整个范围,-2^31除外。
int f(int n)
{
static bool eFlag = false; // Only executed once
eFlag = !eFlag;
return eFlag?-n:n;
}
本质上,函数必须将可用范围划分为大小为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)