我在上次面试中遇到的一个问题是:
设计函数f,使得:f(f(n))==-n其中n是32位有符号整数;你不能用复数算术。如果你不能为整个数字范围设计这样的函数,那么就尽可能为最大范围设计它。
有什么想法吗?
我在上次面试中遇到的一个问题是:
设计函数f,使得:f(f(n))==-n其中n是32位有符号整数;你不能用复数算术。如果你不能为整个数字范围设计这样的函数,那么就尽可能为最大范围设计它。
有什么想法吗?
当前回答
我认为最大的可能范围是暗示模块化算术解决方案。在一些模基M中,有一个数,当平方等于M-1(等于-1)。例如,如果M=13,5*5=25,25 mod 13=12(=-1)总之,这里有一些M=2**32-3的python代码。
def f(x):
m=2**32-3;
halfm=m//2;
i_mod_m=1849436465
if abs( x ) >halfm:
raise "too big"
if x<0:
x+=m
x=(i_mod_m*x) % m
if (x>halfm):
x-=m
return x;
注意,有3个值不适用于2**31-1、-(2**31-1)和-(2*#31)
其他回答
#include <cmath>
int f(int n)
{
static int count = 0;
return ::cos(M_PI * count++) * n;
}
我不知道这是否完全正确,但一个简单的标志不起作用吗?在C语言中,使用静态局部变量,我成功地做到了这一点:
int main()
{
int n = -256; // 32-bit signed integer
printf("%d", f(f(n)));
}
int f(int n){
static int x = 0; // not returning negative;
switch(x){
case 0:
x = 1;
return n;
break;
case 1:
x = 0;
return -n;
break;
default:
return -999;
break;
}
}
它通过保存状态来作弊,但它有效,将操作分成两部分:-n=(~n+1)对于整数
int f(int n) {
static int a = 1;
a = !a;
if (a) {
return (~n);
} else {
return (n+1);
}
}
我的答案是正确的。。。50%的时间,所有的时间。
int f (int num) {
if (rand () / (double) RAND_MAX > 0.5)
return ~num + 1;
return num;
}
我可以想象,使用第31位作为虚(I)位将是一种支持一半总范围的方法。