我在上次面试中遇到的一个问题是:
设计函数f,使得:f(f(n))==-n其中n是32位有符号整数;你不能用复数算术。如果你不能为整个数字范围设计这样的函数,那么就尽可能为最大范围设计它。
有什么想法吗?
我在上次面试中遇到的一个问题是:
设计函数f,使得:f(f(n))==-n其中n是32位有符号整数;你不能用复数算术。如果你不能为整个数字范围设计这样的函数,那么就尽可能为最大范围设计它。
有什么想法吗?
当前回答
Java脚本
function f(n) {
return typeof n === "number" ?
function() {return -n} :
n();
}
其他回答
没有人说它必须是无国籍的。
int32 f(int32 x) {
static bool idempotent = false;
if (!idempotent) {
idempotent = true;
return -x;
} else {
return x;
}
}
作弊,但不如很多例子。更糟糕的是,查看堆栈以查看调用者的地址是否为-f,但这将更具可移植性(虽然不是线程安全的……线程安全版本将使用TLS)。更邪恶的是:
int32 f (int32 x) {
static int32 answer = -x;
return answer;
}
当然,对于MIN_INT32的情况,这两种方法都不太有效,但除非允许返回更宽的类型,否则对此您几乎无能为力。
SQL Server中的解决方案
create function dbo.fn_fo(@num int) -- OUTER FUNCTION
RETURNS int
AS
begin
RETURN @num * -1
end
GO
create function dbo.fn_fi(@num int) -- INNER FUNCTION
RETURNS int
AS
begin
RETURN @num * -1
end
GO
declare @num AS int = -42
SELECT dbo.fn_fo(dbo.fn_fi(@num)) -- Gives (-42)
我试着打高尔夫,这是罗德里克·查普曼的回答。
无分支: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%。
嗯,我既不是数学,也不是编程高手,但这不是很容易吗?
int f(int i) {
static bool b;
if (b) {
b = !b;
return i;
} else {
b = !b;
return -i;
}
}
用大小正值和负值INT_MIN、INT_MAX进行测试,似乎可以。。。如果这是一个问题,可以使线程安全,但这不是任务的一部分。
或者我错过了什么?
我承认我会作弊,但还是符合要求。这是编程魔术,而不是数学。它适用于整个范围,-2^31除外。
int f(int n)
{
static bool eFlag = false; // Only executed once
eFlag = !eFlag;
return eFlag?-n:n;
}