我在上次面试中遇到的一个问题是:
设计函数f,使得:f(f(n))==-n其中n是32位有符号整数;你不能用复数算术。如果你不能为整个数字范围设计这样的函数,那么就尽可能为最大范围设计它。
有什么想法吗?
我在上次面试中遇到的一个问题是:
设计函数f,使得:f(f(n))==-n其中n是32位有符号整数;你不能用复数算术。如果你不能为整个数字范围设计这样的函数,那么就尽可能为最大范围设计它。
有什么想法吗?
当前回答
我承认我会作弊,但还是符合要求。这是编程魔术,而不是数学。它适用于整个范围,-2^31除外。
int f(int n)
{
static bool eFlag = false; // Only executed once
eFlag = !eFlag;
return eFlag?-n:n;
}
其他回答
另一种方法是将状态保持在一位,并在负数的情况下翻转它,注意二进制表示。。。限制为2^29
整数ffn(整数n){
n = n ^ (1 << 30); //flip the bit
if (n>0)// if negative then there's a two's complement
{
if (n & (1<<30))
{
return n;
}
else
{
return -n;
}
}
else
{
if (n & (1<<30))
{
return -n;
}
else
{
return n;
}
}
}
我认为这些问题的答案最好用图表直观地解释。当我们忽略零时,我们可以将整数分成4个数的小集合:
1 → 2 3 → 4 5 → 6
↑ ↓ ↑ ↓ ↑ ↓ ...
-2 ← -1 -4 ← -3 -6 ← -5
这很容易翻译成代码。注意,偶数改变符号,奇数增加或减少1。在C#中,它看起来像这样:
public static int f(int x)
{
if(x == 0)
return 0;
if(x > 0)
return (x % 2 == 0) ? -x+1 : x+1;
// we know x is negative at this point
return (x % 2 == 0) ? -x-1 : x-1;
}
当然,您可以通过使用巧妙的技巧来缩短此方法,但我认为这段代码最好地解释了它本身。
然后是范围。32位整数的范围从-2^31到2^31-1。数字2^31-1、-2^31-1和-2^31超出了f(x)的范围,因为缺少数字2^31。
Tcl:
proc f {input} {
if { [string is integer $input] } {
return [list expr [list 0 - $input]]
} else {
return [eval $input]
}
}
% f [f 1]
-1
按照其他一些答案的思路。。。如果它是一个整数,则返回一个返回该数字负数的命令。如果不是数字,请对其求值并返回结果。
x86 asm(AT&T风格):
; input %edi
; output %eax
; clobbered regs: %ecx, %edx
f:
testl %edi, %edi
je .zero
movl %edi, %eax
movl $1, %ecx
movl %edi, %edx
andl $1, %eax
addl %eax, %eax
subl %eax, %ecx
xorl %eax, %eax
testl %edi, %edi
setg %al
shrl $31, %edx
subl %edx, %eax
imull %ecx, %eax
subl %eax, %edi
movl %edi, %eax
imull %ecx, %eax
.zero:
xorl %eax, %eax
ret
代码已检查,所有可能的32位整数都已通过,错误为-2147483647(下溢)。
Clojure解决方案:
(defmacro f [n] (if (list? n) `(- ~n) n))
也适用于任何大小的正整数和负整数、双整数和比率!