我在上次面试中遇到的一个问题是:
设计函数f,使得:f(f(n))==-n其中n是32位有符号整数;你不能用复数算术。如果你不能为整个数字范围设计这样的函数,那么就尽可能为最大范围设计它。
有什么想法吗?
我在上次面试中遇到的一个问题是:
设计函数f,使得:f(f(n))==-n其中n是32位有符号整数;你不能用复数算术。如果你不能为整个数字范围设计这样的函数,那么就尽可能为最大范围设计它。
有什么想法吗?
当前回答
对于javascript(或其他动态类型语言),可以让函数接受int或对象,并返回另一个。即
function f(n) {
if (n.passed) {
return -n.val;
} else {
return {val:n, passed:1};
}
}
给
js> f(f(10))
-10
js> f(f(-10))
10
或者,您可以在强类型语言中使用重载,尽管这可能会破坏规则
int f(long n) {
return n;
}
long f(int n) {
return -n;
}
其他回答
int f(int x){
if (x < 0)
return x;
return ~x+1; //two's complement
}
我想我会先不看别人的答案就试试这个:
#include <stdio.h> #include <limits.h> #include <stdlib.h> int f(int n) { if(n > 0) { if(n % 2) return -(++n); else { return (--n); } } else { if(n % 2) return -(--n); else { return (++n); } } } int main(int argc, char* argv[]) { int n; for(n = INT_MIN; n < INT_MAX; n++) { int N = f(f(n)); if(N != -n) { fprintf(stderr, "FAIL! %i != %i\n", N, -n); } } n = INT_MAX; int N = f(f(n)); if(N != -n) { fprintf(stderr, "FAIL! n = %i\n", n); } return 0; }
输出:[无]
容易的:
function f($n) {
if ($n%2 == 0) return ($n+1)*-1;
else return ($n-1);
}
下面是一个简短的Python答案:
def f(n):
m = -n if n % 2 == 0 else n
return m + sign(n)
一般情况
稍微调整一下上面的内容就可以处理我们希望k个自调用否定输入的情况——例如,如果k=3,这意味着g(g(g)n))=-n:
def g(n):
if n % k: return n + sign(n)
return -n + (k - 1) * sign(n)
这是通过将0保留在适当位置并创建长度为2*k的循环来实现的,因此,在任何循环中,n和-n之间的距离为k。具体来说,每个周期如下:
N * k + 1, N * k + 2, ... , N * k + (k - 1), - N * k - 1, ... , - N * k - (k - 1)
或者,为了更容易理解,这里是k=3的示例循环:
1, 2, 3, -1, -2, -3
4, 5, 6, -4, -5, -6
这组循环最大化了在任何以零为中心的机器类型(如有符号int32或有符号int64类型)内工作的输入范围。
兼容范围分析
映射x->f(x)实际上必须形成长度为2*k的循环,其中x=0是特殊情况下的1-长度循环,因为-0=0。因此,一般k的问题是可解的,当且仅当输入-1(补偿0)的范围是2*k的倍数,并且正负范围是相反的。
对于有符号整数表示,我们总是有一个最小的负数,在该范围内没有正的对应项,因此该问题在整个范围内变得不可解决。例如,有符号字符的范围为[-128127],因此在给定范围内f(f(-128))=128是不可能的。
该问题表示“32位有符号整数”,但没有指定它们是2个补码还是1个补码。
如果使用1补码,则所有2^32值都出现在长度为4的循环中-不需要零的特殊情况,也不需要条件。
在C中:
int32_t f(int32_t x)
{
return (((x & 0xFFFFU) << 16) | ((x & 0xFFFF0000U) >> 16)) ^ 0xFFFFU;
}
这项工作由
交换高位和低位16位块反转其中一个块
两次传递后,我们得到原始值的位逆。在一中补语表示等同于否定。
示例:
Pass | x
-----+-------------------
0 | 00000001 (+1)
1 | 0001FFFF (+131071)
2 | FFFFFFFE (-1)
3 | FFFE0000 (-131071)
4 | 00000001 (+1)
Pass | x
-----+-------------------
0 | 00000000 (+0)
1 | 0000FFFF (+65535)
2 | FFFFFFFF (-0)
3 | FFFF0000 (-65535)
4 | 00000000 (+0)