我在上次面试中遇到的一个问题是:
设计函数f,使得:f(f(n))==-n其中n是32位有符号整数;你不能用复数算术。如果你不能为整个数字范围设计这样的函数,那么就尽可能为最大范围设计它。
有什么想法吗?
我在上次面试中遇到的一个问题是:
设计函数f,使得:f(f(n))==-n其中n是32位有符号整数;你不能用复数算术。如果你不能为整个数字范围设计这样的函数,那么就尽可能为最大范围设计它。
有什么想法吗?
当前回答
你没说他们期望什么样的语言。。。这是一个静态解决方案(Haskell)。这基本上是在搞乱两个最重要的比特:
f :: Int -> Int
f x | (testBit x 30 /= testBit x 31) = negate $ complementBit x 30
| otherwise = complementBit x 30
在动态语言(Python)中要容易得多。只需检查参数是否为数字X,并返回返回-X的lambda:
def f(x):
if isinstance(x,int):
return (lambda: -x)
else:
return x()
其他回答
该问题表示“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)
这个想法已经在其他答案中使用过,但我把它融入了Python的一行:
def f(n):
return str(n) if type(n) == int else -int(n)
这里有一个解决方案,其灵感来自于不能使用复数来解决这个问题的要求或声明。
乘以-1的平方根是一个想法,但似乎失败了,因为-1没有整数的平方根。但是,使用mathematica这样的程序可以得出如下公式
(18494364652+1)模(232-3)=0。
这几乎和平方根为-1一样好。函数的结果必须是有符号整数。因此,我将使用一个修改的模运算mods(x,n),它返回与x模n最接近0的整数y。只有极少数编程语言能够成功地进行模运算,但它很容易被定义。例如,在python中,它是:
def mods(x, n):
y = x % n
if y > n/2: y-= n
return y
使用上面的公式,问题现在可以解决为
def f(x):
return mods(x*1849436465, 2**32-3)
对于[-231-2231-2]范围内的所有整数,这满足f(f(x))=-x。f(x)的结果也在这个范围内,但当然计算需要64位整数。
我可以想象,使用第31位作为虚(I)位将是一种支持一半总范围的方法。
int f( int n ){
return n==0?0:(n&1?n:-n)+(n<0?-1:1);
}