我在上次面试中遇到的一个问题是：
设计函数f，使得：f（f（n））==-n其中n是32位有符号整数；你不能用复数算术。如果你不能为整个数字范围设计这样的函数，那么就尽可能为最大范围设计它。
有什么想法吗？
当前回答
下面是一个简短的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是不可能的。
其他回答
这是rossfabricant答案的C实现。注意，由于我始终使用32位整数，f（f（2147483647））==2147483648，而不是-2147483647。
int32_t f( int32_t n )
{
if( n == 0 ) return 0;
switch( n & 0x80000001 ) {
case 0x00000000:
return -1 * ( n - 1 );
case 0x00000001:
return n + 1;
case 0x80000000:
return -1 * ( n + 1 );
default:
return n - 1;
}
}
如果您将问题定义为允许f（）接受并返回int64_t，则会涉及2147483647。当然，switch语句中使用的文字必须更改。
该问题表示“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)
没有人说它必须是无国籍的。
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的情况，这两种方法都不太有效，但除非允许返回更宽的类型，否则对此您几乎无能为力。
int f(int n) {
return ((n>0)? -1 : 1) * abs(n);
}
下面是一个简短的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是不可能的。
