设计函数f(f(n))== -n

xquis 发布于 2019-11-10 integer 最后更新 2019-11-10 12:00 195 浏览

我在最后一次采访中遇到了一个问题:

Design a function f, such that:
f(f(n)) == -n
Where n is a 32 bit signed integer; you can't use complex numbers arithmetic. If you can't design such a function for the whole range of numbers, design it for the largest range possible.
有任何想法吗?
已邀请:

ret

赞同来自:

我会改变2个最重要的位。

00.... => 01.... => 10.....
01.... => 10.... => 11.....
10.... => 11.... => 00.....
11.... => 00.... => 01.....
正如你所看到的,它只是一个补充,省去了所携带的位。 我是怎么得到答案的?我的第一个想法只是需要对称性。 4转回到我开始的地方。起初我想,这是2位格雷码。然后我认为实际上标准二进制就足够了。

xatque

赞同来自:

PHP,不使用全局变量:

function f($num) {
  static $mem;
$answer = $num-$mem;
if ($mem == 0) {
    $mem = $num*2;
  } else {
    $mem = 0;
  }
return $answer;
}
使用整数,浮点数和数字字符串! 刚刚意识到这会做一些不必要的工作,但无论如何

mex

赞同来自:

Objective-C的 这适用于除“-1”之外的所有数字。 如果你要从使用int到使用NSInt,那么你可以将-1值设置为NULL,然后将它们第二次转换为+1,但我觉得NSInt欺骗了提问者的意图。


F(N):
-(int)f:(int)n {
    if (abs(n)==1) {
        n = -1;
    } else {
        if (abs(n)%2) {//o
            if (n>0) {//+
                n--;
                n*=+1;
            } else if (n<0) {//-
                n++;
                n*=+1;
            }
        } else {//e
            if (n>0) {//+
                n++;
                n*=-1;
            } else if (n<0) {//-
                n--;
                n*=-1;
            }
        }
    }
    return n;
}
当然这可以缩短为一行,但其他人可能无法阅读...... 点击 无论如何,我将BOOLEAN逻辑存储在数字状态为奇数或偶数。

id_aut

赞同来自:

我认为通过使用图表可以最直观地解释这些问题的答案。当我们忽略零时,我们可以用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)的范围之外,因为缺少数字^ 31。

eipsum

赞同来自:

JavaScript单线程:

function f(n) { return ((f.f = !f.f) * 2 - 1) * n; }

qnobis

赞同来自:

int f(int x){
    if (x < 0)
        return x;
    return ~x+1; //two's complement
}

qet

赞同来自:

我承认我会欺骗,但仍然符合要求。这是编程魔法,而不是真正的数学。它适用于整个范围,除了-2 ^ 31。

int f(int n)
{
    static bool eFlag = false; // Only executed once
    eFlag = !eFlag;
    return eFlag?-n:n;
}

ueum

赞同来自:

实际上,这些问题更多的是关于看到面试官与规范搏斗,设计,错误处理,边界情况和解决方案的合适环境的选择等,而不是实际的解决方案。但是::) 这里的函数是围绕闭合的4周期思想编写的。如果只允许函数f仅在有符号的32位整数上着陆,那么上面的各种解决方案都将起作用,除了其他人指出的三个输入范围数。 minint将永远不会满足函数方程,因此如果是输入,我们将引发异常。 在这里,我允许我的Python函数操作并返回元组或整数。任务规范承认这一点,它只指定函数的两个应用程序应该返回一个等于原始对象的对象(如果它是int32)。 (我会询问有关规范的更多细节。) 这允许我的轨道很好和对称,并覆盖所有输入整数(minint除外)。我最初设想循环访问半整数值,但我不想纠结舍入错误。因此元组表示。这是一种在不使用复杂算术机制的情况下将复杂旋转隐藏在元组中的方法。 请注意,调用之间不需要保留任何状态,但调用者确实需要允许返回值为元组或int。

def f(x) :
  if isinstance(x, tuple) :
      # return a number.
      if x[0] != 0 :
        raise ValueError  # make sure the tuple is well formed.
      else :
        return ( -x[1] )
elif isinstance(x, int ) :
    if x == int(-2**31 ):
      # This value won't satisfy the functional relation in
      # signed 2s complement 32 bit integers.
      raise ValueError
    else :
      # send this integer to a tuple (representing ix)
      return( (0,x) )
  else :
    # not an int or a tuple
    raise TypeError
所以将f应用于37两次得到-37,反之亦然:
>>> x = 37
>>> x = f(x)
>>> x
(0, 37)
>>> x = f(x)
>>> x
-37
>>> x = f(x)
>>> x
(0, -37)
>>> x = f(x)
>>> x
37
将f两次应用于零得到零:
>>> x=0
>>> x = f(x)
>>> x
(0, 0)
>>> x = f(x)
>>> x
0
我们处理问题没有解决方案的一个案例(在int32中):
>>> x = int( -2**31 )
>>> x = f(x)
Traceback (most recent call last):
  File "<pyshell#110>", line 1, in <module>
    x = f(x)
  File "<pyshell#33>", line 13, in f
    raise ValueError
ValueError
如果你认为该函数通过模拟乘以i的90度旋转来打破“无复数算术”规则,我们可以通过扭曲旋转来改变它。这里的元组代表半整数,而不是复数。如果跟踪数字线上的轨道,您将获得满足给定函数关系的非交叉循环。
f2: n -> (2 abs(n) +1, 2 sign( n) ) if n is int32, and not minint.
f2: (x, y) -> sign(y) * (x-1) /2  (provided y is \pm 2 and x is not more than 2maxint+1
练习:通过修改f来实现这个f2。还有其他解决方案,例如中间着陆点是半整数以外的有理数。有一个可能证明有用的分数模块。你需要一个签名功能。 这个练习确实为我提供了动态类型语言的乐趣。我在C中看不到像这样的解决方案。

psequi

赞同来自:

这是一个简短的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
这组循环最大化了将在以零为中心的任何机器类型中工作的输入范围,例如signed int32或signed int64类型。 分析兼容范围 地图x -> f(x)实际上必须形成长度为2 * k的循环,其中x = 0是特殊情况1长度循环,因为-0 = 0.因此,当且仅当输入的范围为1时,k的问题是可解的(为了补偿) 0)是2 * k的倍数,正负范围是对立的。 对于有符号整数表示,我们始终具有最小负数,在该范围内没有正对应,因此问题在整个范围内变得不可解决。例如,signed char的范围为[-128,127],因此f(f(-128)) = 128在给定范围内是不可能的。

tquod

赞同来自:

好问题! 我花了大约35秒来思考和写作:

int f(int n){
    static int originalN=0;
    if (n!=0)
        originalN=n;
    return n-originalN;
}

dodit

赞同来自:

没有人说f(x)必须是同一类型。

def f(x):
    if type(x) == list:
        return -x[0]
    return [x]
f(2) => [2]
f(f(2)) => -2

xsit

赞同来自:

#include <cmath>
int f(int n)
{
    static int count = 0;
    return ::cos(M_PI * count++) * n;
}

set

赞同来自:

在PHP中

function f($n) {
    if(is_int($n)) {
        return (string)$n;
    }
    else {
        return (int)$n * (-1);
    }
}
我相信你可以理解这种方法对其他语言的精神。我明确地将其转换回int,以使那些不使用弱类型语言的人更清楚。你必须为某些语言重载函数。 关于这个解决方案的巧妙之处在于无论你是以字符串还是整数开头,并且在返回f(n)时都没有明显改变任何东西。 在我看来,采访者问:“这位候选人是否知道如何标记数据以便稍后进行操作”,并且“这位候选人是否知道如何标记数据,同时最少改变数据呢?”您可以使用双打,字符串或任何其他您想要投射的数据类型来执行此操作。

nodit

赞同来自:

创建许多解决方案的一种方法是注意,如果我们将整数划分为两个集合S和R s.t -S = S,-R = R,并且函数g s.t g(R)= S 然后我们可以创建f如下: 如果x在R中则f(x)= g(x) 如果x在S中则f(x)= -invg(x) 其中invg(g(x))= x因此invg是g的反函数。 上面提到的第一个解决方案是分区R =偶数,R =奇数,g(x)= x + 1。 我们可以取任意两个无穷集T,P s.t T + U =整数集并取S = T +( - T),R = U +( - U)。 然后-S = S和-R = R的定义我们可以将g作为从S到R的任何1-1对应关系,它必须存在,因为两个集合都是无限且可数的,将起作用。 因此,这将为我们提供许多解决方案,但并非所有当然都可以编程,因为它们不会被有限地定义。 一个例子可以是: R =可被3整除的数字,S =不能被3整除的数字。 然后我们取g(6r)= 3r + 1,g(6r + 3)= 3r + 2。

znemo

赞同来自:

一个C函数:

int f(int n) /* Treats numbers in the range 0XC0000000 to 0X3FFFFFFF as valid to
                generate f(f(x)) equal to -x. If n is within this range, it will
                project n outside the range. If n is outside the range, it will
                return the opposite of the number whose image is n. */
{
    return n ? n > 0 ? n <= 0X3FFFFFFF ? 0X3FFFFFFF + n : 0X3FFFFFFF - n :\
           n >= 0XC0000000 ? 0XC0000000 + n : 0XC0000000 - n : 0;
}

Ideone Link for Testing and Download

et_et

赞同来自:

根据微软/谷歌采访者在采访中经常提出的问题,我认为提问者意味着一种创新的,轻量级的,简单的解决方案,它将使用按位操作,而不是那些复杂的高级答案。 受到@eipipuz答案的启发,我编写了这个C++函数(但没有运行它):

int32_t f(int32_t n){
    int32_t temp = n & 00111111111111111111111111111111;
    x = n >> 30;
    x++;
    x = x << 30;
    return x | temp;
}
它将n的最左边两位存储在x中,将x加1,然后再将其替换为n的最左边两位。 如果我们继续用另一个f(n)作为参数n运行f(n),最左边的两位将像这样旋转:
00 --> 01 --> 10 --> 11 --> 00 ...
请注意,最右边的30位不会改变。 8位整数的示例: 例1:
  • > f(00001111)= 01001111
  • > f(01001111)= 10001111 [这是原始值的负数,00001111]
例2:
  • > f(11101010)= 00101010
  • > f(00101010)= 01101010 [这是原始值的负数,11101010]

get

赞同来自:

void f(int x)
{
     Console.WriteLine(string.Format("f(f({0})) == -{0}",x));
}
对不起伙计们......太诱人了;)

ut_sed

赞同来自:

int f(int n)
{
  static long counter=0;
  counter++;
  if(counter%2==0)
    return -n;
  else
    return n;
}

ket

赞同来自:

C++中的另一种作弊解决方案,运算符重载。

struct func {
    int n;
    func operator()(int k) { n = -k; return *this; }
    int operator()(const func &inst) { return inst.n; }
} f;

bipsam

赞同来自:

所述问题不要求该函数必须仅接受32位整数,只有n,如给定的,是32位整数。 红宝石:

def f( n )
  return 0 unless n != 0 
  ( n == n.to_i ) ? 1.0 / n : -(n**-1).to_i
end

mest

赞同来自:

使用全局...但是这样?

bool done = false
f(int n)
{
  int out = n;
  if(!done)
  {  
      out = n * -1;
      done = true;
   }
   return out;
}

uaut

赞同来自:

Wolfram Language中的解决方案:

f[f[n_]] := -n
应用:
In[2]:= f[f[10]]                                                                                                                                                                                                                                                                              
Out[2]= -10
In[3]:= f[10]                                                                                                                                                                                                                                                                                 
Out[3]= f[10]
因为问题没有说明f(n)的价值,f [n]仍然没有评估。

nerror

赞同来自:

这里有一个证明,为什么这样的函数不能存在,对于所有数字,如果它不使用额外的信息(除了32位的int): 我们必须有f(0)= 0.(证明:假设f(0)= x。那么f(x)= f(f(0))= - 0 = 0.现在,-x = f(f(x ))= f(0)= x,表示x = 0。) 此外,对于任何xy,假设f(x) = y。我们想要f(y) = -x。和f(f(y)) = -y => f(-x) = -y。总结一下:如果是f(x) = y,那么f(-x) = -yf(y) = -x,以及f(-y) = x。 因此,我们需要将除0之外的所有整数除以4的集合,但是我们有一个奇数个这样的整数;不仅如此,如果我们删除没有正对应的整数,我们仍然有2(mod4)数。 如果我们删除剩下的2个最大数字(通过abs值),我们可以得到函数:

int sign(int n)
{
    if(n>0)
        return 1;
    else 
        return -1;
}
int f(int n)
{
    if(n==0) return 0;
    switch(abs(n)%2)
    {
        case 1:
             return sign(n)*(abs(n)+1);
        case 0:
             return -sign(n)*(abs(n)-1);
    }
}   
当然另一种选择是不遵守0,并获得我们删除的2个数字作为奖励。 (但这只是一个愚蠢的。)

but

赞同来自:

类似于函数重载解决方案,在python中:

def f(number):
 if type(number) != type([]):
  return [].append(number)
 else:
  return -1*number[0]
替代方案:static datamembers

hipsum

赞同来自:

这个想法已被用于其他答案中,但我将其纳入了一行Python:

def f(n):
    return str(n) if type(n) == int else -int(n)

eet

赞同来自:

f(x)=点(x)在2D笛卡尔坐标系中绕原点逆时针旋转90度。仅假设一个数字x的输入为(x,0),并且提供具有y = 0的输出作为单个数字x。

object f: (object) x {
    if (x.length == 1)
        x = (x, 0)
    swap = x[0]
    x[1] = x[0]
    x[0] = -swap
    if (x[1] == 0)
        x = x[0]
    return x

eut

赞同来自:

好吧,我既不是数学也不是编程问题,但这不是很容易吗?

int f(int i) {
    static bool b;
    if (b) {
        b = !b;
        return i;
    } else {
        b = !b;
        return -i;
    }
}
它使用大小的正负值INT_MIN,INT_MAX进行测试,它似乎有效......如果这是一个问题,可以使线程安全,但它不是任务的一部分。 或许我错过了什么?

gcum

赞同来自:

const unsigned long Magic = 0x8000000;
unsigned long f(unsigned long n)
{    
    if(n > Magic )
    {
        return Magic - n;
    }
return n + Magic;
} 
0~2 ^ 31

nodio

赞同来自:

C++解决方案;

long long f(int n){return static_cast <long long> (n);}
int f(long long n){return -static_cast <int> (n);}
int n = 777;
assert(f(f(n)) == -n);

ut_sit

赞同来自:

感谢C++中的重载:

double f(int var)
{
 return double(var);
}
int f(double var)
{
 return -int(var);
}
int main(){
int n(42);
std::cout<<f(f(n));
}

lsunt

赞同来自:

我还没有看到其他答案,我认为已经彻底讨论了按位技术。 我以为我会在C++中想出一些邪恶的东西,希望这不是一个骗局:

struct ImplicitlyConvertibleToInt
{
    operator int () const { return 0; }
};
int f(const ImplicitlyConvertibleToInt &) { return 0; }
ImplicitlyConvertibleToInt f(int & n)
{
    n = 0; // The problem specification didn't say n was const
    return ImplicitlyConvertibleToInt();
}
整个ImplicitlyConvertibleToInt类型和重载是必要的,因为temporaries不能绑定到非const引用。 当然,现在看一下它是否未定义f(n)是否在-n之前执行。 对这种程度的邪恶来说,或许更好的解决方案就是:
struct ComparesTrueToInt
{
    ComparesTrueToInt(int) { } // implicit construction from int
};
bool operator == (ComparesTrueToInt, int) const { return true; }
ComparesTrueToInt f(ComparesTrueToInt ct) { return ComparesTrueToInt(); }

et_et

赞同来自:

简单的Python解决方案可以通过以下事实实现:f(x)应该输出的内容没有限制,只有f(f(x)):

def f(x):
    return (isinstance(x, tuple) and -x[0]) or (x,)

xest

赞同来自:

似乎很容易。

<script type="text/javascript">
function f(n){
    if (typeof n === "string") {
        return parseInt(n, 10)
    }
    return (-n).toString(10);
}
alert(f(f(1)));
</script>

oiusto

赞同来自:

这将适用于非常广泛的数字:

    static int f(int n)
    {
        int lastBit = int.MaxValue;
        lastBit++;
        int secondLastBit = lastBit >> 1;
        int tuple = lastBit | secondLastBit;
        if ((n & tuple) == tuple)
            return n + lastBit;
        if ((n & tuple) == 0)
            return n + lastBit;
        return -(n + lastBit);
    }
我最初的方法是使用最后一位作为检查位来知道我们在第一次或第二次调用中的位置。基本上,我会在第一次通话后将此位置为1,以表示第一次已经通过的第二次通话。但是,这种方法被第一次通话中最后一位已经到达1的负数击败。 同样的理论适用于大多数负数的倒数第二位。但是,通常发生的是大多数时候,最后和最后一位是相同的。要么它们都是1表示负数,要么它们都是0表示正数。 所以我最后的方法是检查它们是1还是0都是0,这意味着在大多数情况下这是第一次调用。如果最后一位与倒数第二位不同,那么我假设我们处于第二次调用,并且只是重新反转最后一位。显然,这对使用这两个最后位的非常大的数字不起作用。但是,它再次适用于非常广泛的数字。

tet

赞同来自:

使用问题中给出的信息,您可以

  1. 从2补码转换为符号位表示
  2. 如果设置了最后一位,则翻转符号位和最后一位;否则,翻转最后一位
  3. 转换回2-complement。
所以你基本上是奇数 - >偶数 - >奇数或偶数 - >奇数 - >偶数,并且仅为偶数改变符号。这个不起作用的唯一数字是-2 ^ 31 码:
function f(x) {
  var neg = x < 0;
  x = Math.abs(x) ^ 1;
  if (x & 1) {
    neg = !neg;
  }
  return neg ? -x : x;
}

uut

赞同来自:

return x ^ ((x%2) ? 1 : -INT_MAX);

gsint

赞同来自:

我认为可能的最大范围是暗示模块化算术解决方案。在一些模块化基础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)

bsint

赞同来自:

int f(const int n)  {
    static int last_n;
if (n == 0)
        return 0;
    else if (n == last_n)
        return -n;
    else
    {
        last_n = n;
        return n;
    }
}
哈金,但是正确的。

taut

赞同来自:

怎么样

int f(int n)
{
    return -abs(n);
}

cet

赞同来自:

LUA:

function f(n)
    if type(n) == "number" then
        return (-number) .. ""
    else
        return number + 0
    end
end

uaut

赞同来自:

C#为2 ^ 32 - 1个数字,所有int32数字除外(Int32.MinValue)

    Func<int, int> f = n =>
        n < 0
           ? (n & (1 << 30)) == (1 << 30) ? (n ^ (1 << 30)) : - (n | (1 << 30))
           : (n & (1 << 30)) == (1 << 30) ? -(n ^ (1 << 30)) : (n | (1 << 30));
Console.WriteLine(f(f(Int32.MinValue + 1))); // -2147483648 + 1
    for (int i = -3; i <= 3  ; i++)
        Console.WriteLine(f(f(i)));
    Console.WriteLine(f(f(Int32.MaxValue))); // 2147483647
打印:
2147483647
3
2
1
0
-1
-2
-3
-2147483647

yautem

赞同来自:

C#重载:

string f(int i) {
  return i.ToString();
}
int f(string s) {
  return Int32.Parse(s) * -1;
}
要么
object f(object o) {
  if (o.ToString.StartsWith("s"))
    return Int32.Parse(s.Substring(1)) * -1;
  return "s" + i.ToString();
}

xnobis

赞同来自:

f#中的简单解决方案(不使用“技巧”)

let rec f n =
    if n = 0 then 0
    elif n > 0 then
        if (f (n - 1) <> n) then n + 1
        else -(n - 1)
    else
        if (f (-(n - 1)) = n) then n - 1
        else -(n + 1) 

gvel

赞同来自:

这个怎么样?

int nasty(int input)
{
    return input + INT_MAX/2;
}

iid

赞同来自:

我实际上并没有尝试解决问题本身,但确实有几条评论,因为问题表明这个问题是(工作?)采访的一部分:

  • 我首先会问“为什么需要这样的功能?这个问题的重大问题是什么?”而不是试图当场解决实际提出的问题。这显示了我的思考方式以及我如何解决这样的问题。谁知道?这甚至可能是首先在面试中提出问题的实际原因。如果答案是“从不介意,假设需要它,并告诉我你将如何设计这个功能。”然后我会继续这样做。
  • 然后,我会写C#测试用例代码我会使用(明显的事实:循环从int.MinValueint.MaxValue,以及用于在该范围内呼叫f(f(n))每个n并检查结果是-n),告诉我将然后使用测试驱动发展以实现这样的功能。
  • 只有当面试官继续要求我解决所提出的问题时,我才真正开始尝试在面试过程中涂写伪代码以尝试获得某种答案。但是,如果面试官能够表明公司是什么样的话,我真的不认为我会跳起来工作......
哦,这个答案假设面试是针对C#编程相关的职位。如果面试是针对数学相关的职位,那当然是一个愚蠢的答案。 ;-)

ased

赞同来自:

用coffeescript打高尔夫球:

f = (n)-> -n[0] or [n]

matque

赞同来自:

少于50个字符(C#)
int f(int n) { return (n <= 0) ? n : f(-n); }

或者更容易阅读:
static int f(int n) { 
  if (n <= 0)
    return n;
  else 
    return f(-n);
}

测试
static void Main(string[] args) {
    for (int n = int.MinValue; n < int.MaxValue; n+=1) {
        Console.Out.WriteLine("Value: " + n + " Result: " + f(f(n)));
    }
}
它有效(假设我理解正确的问题)

gipsam

赞同来自:

在C中,

int 
f(int n) {
     static int r = 0;
     if (r == 1) {r--; return -1 * n; };
     r++;
     return n;
}
这将有助于了解这是什么语言。 我错过了什么吗?许多“解决方案”似乎过于复杂,坦率地说,并非如此 工作(因为我读到了问题)。

lnon

赞同来自:

C++

struct Value
{
  int value;
  Value(int v) : value(v) {}
  operator int () { return -value; }
};
Value f(Value input)
{
  return input;
}

wanimi

赞同来自:

内容太长未翻译

ad_est

赞同来自:

:d

boolean inner = true;
int f(int input) {
   if(inner) {
      inner = false;
      return input;
   } else {
      inner = true;
      return -input;
   }
}

taut

赞同来自:

f(n) { return IsWholeNumber(n)? 1/n : -1/n }

set

赞同来自:

根据您的平台,某些语言允许您在功能中保持状态。 VB.Net,例如:

Function f(ByVal n As Integer) As Integer
    Static flag As Integer = -1
    flag *= -1
Return n * flag
End Function
IIRC,C++也允许这样做。我怀疑他们正在寻找不同的解决方案。 另一个想法是,由于他们没有定义第一次调用函数的结果,你可以使用奇数/偶数来控制是否反转符号:
int f(int n)
{
   int sign = n>=0?1:-1;
   if (abs(n)%2 == 0)
      return ((abs(n)+1)*sign * -1;
   else
      return (abs(n)-1)*sign;
}
在所有偶数的幅度上加1,从所有奇数的幅度中减去1。两个调用的结果具有相同的幅度,但是一个调用甚至我们交换符号。在某些情况下,这将不起作用(-1,max或min int),但它比目前为止提出的任何其他方法都要好得多。

womnis

赞同来自:

这个怎么样:

do
    local function makeFunc()
        local var
        return function(x)
            if x == true then
                return -var
            else
                var = x
                return true
            end
        end
end
    f = makeFunc()
end
print(f(f(20000)))

et_qui

赞同来自:

这个Perl解决方案适用于整数,浮点数和字符串。

sub f {
    my $n = shift;
    return ref($n) ? -$$n : \$n;
}
尝试一些测试数据。
print $_, ' ', f(f($_)), "\n" for -2, 0, 1, 1.1, -3.3, 'foo' '-bar';
输出:
-2 2
0 0
1 -1
1.1 -1.1
-3.3 3.3
foo -foo
-bar +bar

ynulla

赞同来自:

int f( int n ){
    return n==0?0:(n&1?n:-n)+(n<0?-1:1);
}

id_aut

赞同来自:

我可以想象使用第31位作为虚数(i)位将是一种支持总范围的一半的方法。

eet

赞同来自:

一个C++版本,可能会稍微弯曲规则,但适用于所有数字类型(浮点数,整数,双精度)甚至是重载一元减号的类类型:

template <class T>
struct f_result
{
  T value;
};
template <class T>
f_result <T> f (T n)
{
  f_result <T> result = {n};
  return result;
}
template <class T>
T f (f_result <T> n)
{
  return -n.value;
}
void main (void)
{
  int n = 45;
  cout << "f(f(" << n << ")) = " << f(f(n)) << endl;
  float p = 3.14f;
  cout << "f(f(" << p << ")) = " << f(f(p)) << endl;
}

jenim

赞同来自:

利用JavaScript异常。

function f(n) {
    try {
        return n();
    }
    catch(e) { 
        return function() { return -n; };
    }
}
f(f(0)) => 0 f(f(1)) => -1

kquis

赞同来自:

适用于n = [0 .. 2 ^ 31-1]

int f(int n) {
  if (n & (1 << 31)) // highest bit set?
    return -(n & ~(1 << 31)); // return negative of original n
  else
    return n | (1 << 31); // return n with highest bit set
}

nomnis

赞同来自:

简单,只需使f返回看似等于任何整数的东西,并且可以从整数转换。

public class Agreeable
{
    public static bool operator==(Agreeable c, int n)
        { return true; }
public static bool operator!=(Agreeable c, int n)
        { return false; }
public static implicit operator Agreeable(int n)
        { return new Agreeable(); }
}
class Program
{
    public static Agreeable f(Agreeable c)
        { return c; }
static void Main(string[] args)
    {
        Debug.Assert(f(f(0)) == 0);
        Debug.Assert(f(f(5)) == -5);
        Debug.Assert(f(f(-5)) == 5);
        Debug.Assert(f(f(int.MaxValue)) == -int.MaxValue);
    }
}

het

赞同来自:

在Python中

f=lambda n:n[0]if type(n)is list else[-n]

snihil

赞同来自:

SQL Server中的解决方案

create function dbo.fn_fo(@num int) -- OUTER FUNCTION
RETURNS int
AS
begin
RETURN @num * -1
end
GO
create function dbo.fn_fi(@num int) -- INNER FUNCTION
RETURNS int
AS
begin
RETURN @num * -1
end
GO
declare @num AS int = -42
SELECT dbo.fn_fo(dbo.fn_fi(@num)) -- Gives (-42)

killo

赞同来自:

我有另一个解决方案,有一半的时间工作:

def f(x):
    if random.randrange(0, 2):
        return -x
    return x

punde

赞同来自:

这是一个不使用任何按位运算符的C / C++解决方案,并且不需要任何数学库,尽管它有点作弊......

double f(double n)
{
    if (n == (double)(int)n)
        return n + 0.5;
    else
        return -(n - 0.5);
}
这适用于所有32位整数,只有0x80000000例外(因为它的相反方法不能存储在32位整数系统中)。除了那种情况外,f(f(n)) == -n将始终为true。 不过,我确信有更简单,更快捷的方法来实现它。这只是我想到的第一件事。

zearum

赞同来自:

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(下溢)。

adicta

赞同来自:

怎么样:

f(n) = sign(n) - (-1)n * n
在Python中:
def f(n): 
    if n == 0: return 0
    if n >= 0:
        if n % 2 == 1: 
            return n + 1
        else: 
            return -1 * (n - 1)
    else:
        if n % 2 == 1:
            return n - 1
        else:
            return -1 * (n + 1)
Python自动将整数提升为任意长度的长度。在其他语言中,最大的正整数将溢出,因此它将适用于除了那个之外的所有整数。
要使其适用于实数,您需要使用{ ceiling(n) if n>0; floor(n) if n<0 }替换(-1) n 中的n。 在C#中(适用于任何double,除了溢出情况):
static double F(double n)
{
    if (n == 0) return 0;
if (n < 0)
        return ((long)Math.Ceiling(n) % 2 == 0) ? (n + 1) : (-1 * (n - 1));
    else
        return ((long)Math.Floor(n) % 2 == 0) ? (n - 1) : (-1 * (n + 1));
}

baut

赞同来自:

我给出了正确的答案... 50%的时间,所有的时间。

int f (int num) {
    if (rand () / (double) RAND_MAX > 0.5)
         return ~num + 1;
    return num;
}

pporro

赞同来自:

这适用于-1073741823到1073741822的范围:

int F(int n)
{
    if(n < 0)
    {
        if(n > -1073741824)
            n = -1073741824 + n;
        else n = -(n + 1073741824);
    }
    else
    {
        if(n < 1073741823)
            n = 1073741823 + n;
        else n = -(n - 1073741823);
    }
    return n;
}
它的工作原理是获取32位signed int的可用范围并将其除以2。函数的第一次迭代将n 置于该范围之外。第二次迭代检查它是否在此范围之外 - 如果是,则将其放回范围内但使其为负值。 它实际上是一种保持关于值n的额外“信息”的方法。

xeos

赞同来自:

或者,您可能滥用预处理器:

#define f(n) (f##n)
#define ff(n) -n
int main()
{
  int n = -42;
  cout << "f(f(" << n << ")) = " << f(f(n)) << endl;
}

iaut

赞同来自:

int f(int n) {
    return ((n>0)? -1 : 1) * abs(n);
}

xipsam

赞同来自:

虽然问题是n必须是32位int,但它没有说参数或返回类型必须是32位int。这应该在java中编译 - 在c中你可以摆脱!= 0

private final long MAGIC_BIT=1<<38;
long f(long n) {
    return n & MAGIC_BIT != 0 ? -(n & !MAGIC_BIT) : n | MAGIC_BIT;
}
编辑: 这实际上是一个非常好的面试问题。最好的是难以或无法回答的问题,因为它迫使人们思考它,你可以观察和寻找:
  • 他们只是放弃了吗?
  • 他们说这是愚蠢的吗?
  • 他们尝试独特的方法吗?
  • 他们在处理问题时是否与您沟通?
  • 他们是否要求进一步完善要求?
等等 除非你有一个非常好的答案,否则永远不要回答行为问题。总是愉快,并试图让提问者参与进来。不要沮丧,不要早点放弃!如果你真的没有到达任何地方,尝试一些完全非法的东西,可以工作,你将得到几乎完全的功劳。

podio

赞同来自:

number f( number n)
{
  static count(0);
  if(count > 0) return -n;
  return n;
}
f(n) = n
f(f(n)) = f(n) = -n

yalias

赞同来自:

本质上,函数必须将可用范围划分为大小为4的循环,其中-n位于n循环的另一端。但是,0必须是大小为1的循环的一部分,否则0->x->0->x != -x。因为0是单独的,所以我们的范围中必须有3个其他值(其大小是4的倍数),而不是具有4个元素的正确循环。 我选择这些额外的奇怪值为MIN_INTMAX_INTMIN_INT+1。此外,MIN_INT+1将正确映射到MAX_INT,但卡在那里而不是映射回来。我认为这是最好的折衷方案,因为它具有只有极端值不能正常工作的优良特性。此外,这意味着它适用于所有BigInts。

int f(int n):
    if n == 0 or n == MIN_INT or n == MAX_INT: return n
    return ((Math.abs(n) mod 2) * 2 - 1) * n + Math.sign(n)

xsed

赞同来自:

不记得你的上一个状态是否足够好?

int f (int n)
{
    //if count 
    static int count = 0;
if (count == 0)
        { 
            count = 1;
            return n;
        }
if (n == 0)
        return 0;
    else if (n > 0)
    {
        count = 0;
        return abs(n)*(-1);
    } 
    else
    {
        count = 0;
        return abs(n);
    }
}
int main()
{
    int n = 42;
    std::cout << f(f(n))
}

eomnis

赞同来自:

问题没有说明f函数的输入类型和返回值必须是什么(至少不是你提出的方式)...... ...只是当n是32位整数然后是f(f(n)) = -n 那么,怎么样的

Int64 f(Int64 n)
{
    return(n > Int32.MaxValue ? 
        -(n - 4L * Int32.MaxValue):
        n + 4L * Int32.MaxValue);
}
如果n是32位整数,则语句f(f(n)) == -n将为真。 显然,这种方法可以扩展到更广泛的数字......

mnatus

赞同来自:

MIN_INT上没有失败:

int f(n) { return n < 0 ? -abs(n + 1) : -(abs(n) + 1); }

tut

赞同来自:

以为我会先试试这个,而不先看别人的答案:

#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;
}
输出:[无]

nin

赞同来自:

也许我错过了什么? 这不是一件简单的事情:

    function f(n)
    {
        if(n ==0 || n < 0){return n;}
        return n * -1;
    }
编辑: 所以我很想念这个问题,哼哼,所以:
    function f(n)
    {
        if(!c(n,"z")&&!c(n,"n")){if(n==0){return "z"+n;}return "n"+n;}
        if( c(n,"z")){return 0;}return parseInt(n.replace("n",""))*-1;
    }
    function c(x,y){return x.indexOf(y) !==-1;}
丑陋但有效。

qquod

赞同来自:

Python 2.6:

f = lambda n: (n % 2 * n or -n) + (n > 0) - (n < 0)
我意识到这对讨论没什么好处,但我无法抗拒。

ut_sit

赞同来自:

我尝试过Rodrick Chapman打高尔夫球的this answer。 没有分支:74个字符

int f(int i){return(-((i&1)<<1)|1)*i-(-((i>>>31)<<1)|1)*(((i|-i)>>31)&1);}
有分支,Java风格:58个字符
int f(int i){return i==0?0:(((i&1)==0?i:-i)+(i>0?-1:1));}
有分支,C风格:52个字符
int f(int i){return i?(((i&1)?-i:i)+(i>0?-1:1)):0;}

在快速但有效的基准测试之后,分支版本在我的机器上的速度提高了33%。 (正数和负数的随机数据集,足够的重复并阻止编译器优化代码,并进行预热。)鉴于未分支版本中的操作数和可能的良好分支预测,这并不令人惊讶该函数被调用两次:f(f(i))。当我将基准测试更改为:f(i)时,分支版本的速度仅提高了28%。我认为这证明了分支预测在第一种情况下实际上做得很好。更多证明:使用f(f(f(f(i))))进行测试时,分支版本的速度提高了42%。

kex

赞同来自:

Scala中使用隐式转换的一个奇怪的,只是稍微聪明的解决方案:

sealed trait IntWrapper {
  val n: Int
}
case class First(n: Int) extends IntWrapper
case class Second(n: Int) extends IntWrapper
case class Last(n: Int) extends IntWrapper
implicit def int2wrapper(n: Int) = First(n)
implicit def wrapper2int(w: IntWrapper) = w.n
def f(n: IntWrapper) = n match {
  case First(x) => Second(x)
  case Second(x) => Last(-x)
}
我不认为这是一个非常正确的想法。

tvelit

赞同来自:

  1. 将n转换为符号和幅度表示;
  2. 添加1/4的范围;
  3. 转换回来。
    #define STYPE int
    STYPE sign_bit = (unsigned STYPE) 1 << ( sizeof ( STYPE ) * 8  - 1 );
    STYPE f ( STYPE f )
    {
        unsigned STYPE smf = f > 0 ? f : -f | sign_bit;
        smf += sign_bit >> 1;
        return smf & sign_bit ? -( smf & ~sign_bit ) : smf;
    }

jalias

赞同来自:

有些相似但只是想我会写下我的第一个想法(在C++中)

#include <vector>
vector<int>* f(int n)
{
  returnVector = new vector<int>();
  returnVector->push_back(n);
  return returnVector;
}
int f(vector<int>* n) { return -(n->at(0)); }
只是使用重载使f(f(n))实际调用两个不同的函数

aut_id

赞同来自:

另一种利用短路的Javascript解决方案。

​function f(n) {return n.inv || {inv:-n}}
f(f(1)) => -1
f(f(-1)) => 1

overo

赞同来自:

没有人说它必须是无国籍的。

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的情况,这些都不能很好地工作,但是除非你被允许返回更宽的类型,否则你可以做的很少。

dquia

赞同来自:

这是一个灵感来自要求或声称复杂数字不能用于解决此问题的解决方案。 乘以-1的平方根是一个想法,似乎只是失败,因为-1没有整数的平方根。但是,玩像mathematica这样的程序可以得到例如等式

(18494364652+1) mod (232-3) = 0.
这几乎与-1的平方根一样好。函数的结果需要是有符号整数。因此,我将使用修改的模运算mods(x,n),它将整数y congruent返回到最接近0的x modulo n。只有极少数编程语言有模数运算,但它很容易定义。例如。在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)
这满足了[-2 31 -2, 2 31 -2]范围内所有整数的f(f(x)) = -xf(x)的结果也在此范围内,但当然计算需要64位整数。

wnihil

赞同来自:

使用复数,您可以有效地将否定数字的任务分为两个步骤:

  • 将n乘以i,得到n * i,即n逆时针旋转90°
  • 再次乘以i,你得到-n
最棒的是你不需要任何特殊的处理代码。只是乘以我做的工作。 但是你不允许使用复数。因此,您必须使用部分数据范围以某种方式创建自己的虚轴。由于您需要与初始值完全相同的虚数(中间)值,因此只剩下一半的数据范围。 假设有符号的8位数据,我试图在下图中将其可视化。您必须将此缩放为32位整数。初始n的允许范围是-64到+63。 这是函数对正n的作用:
  • 如果n在0..63(初始​​范围)内,则函数调用加64,将n映射到范围64..127(中间范围)
  • 如果n在64..127(中间范围),则该函数从64减去n,将n映射到范围0 ..- 63
对于负n,该函数使用中间范围-65 ..- 128。 alt text

tiure

赞同来自:

int j = 0;
void int f(int n)
{    
    j++;
if(j==2)
    {
       j = 0;
       return -n;
    }
return n;
}
:d

zin

赞同来自:

int f(int n)
{
   static int x = 0;
   result = -x;
   x = n;
   return result;
}
这是一个带有否定的入口FIFO。当然,它不适用于最大负数。

zsed

赞同来自:

f(n) { return -1 * abs(n) }
我该如何处理溢出问题呢?或者我错过了这一点?

zrerum

赞同来自:

也许作弊? (蟒蛇)

def f(n):    
    if isinstance(n, list):
        return -n[0]
    else:
        return [n,0]    
n = 4
print f(f(n))
--output--
-4

riure

赞同来自:

使用循环置换方法来做到这一点。 -b a b -a a b -a -b 在琐碎的情况下 f(0)返回0 对不起,我的电话粗略回答,28日后我将发布完整版(现在正在考试......) 简单地说,认为f(n)是一个循环置换,问题是如何构造它。 define fk = f(f(f(f(... f(n)))))(k fs) 情况k = 2 0.trivial情况 f(0)返回0 1.制作团体,情况k = 2,团体: {0} {1,2} {3,4} ... {n,n + 1 | (n + 1)%2 = 0} ,注意:我只使用Z +,因为施工不需要使用负数。 2.构造排列: 如果n%2 = 0,那么a = n-1 b = n 如果n%2 = 1,那么a = n b = n + 1 这将产生相同的排列,因为n和f(n)在同一组中。 注意排列为P 返回P(n) 对于k = 2t,只做上面相同的事情,只是MOD k。 对于k = 2t-1,虽然方法有效但是没有意义啊,是吗? (f(n)= -n是好的)

somnis

赞同来自:

F#
let f n =
    match n with
    | n when n % 2 = 0 -> -n + System.Math.Sign n
    | _ -> n - System.Math.Sign -n
其中n就是System.Int32.MinValue < n < System.Int32.MaxValue

trerum

赞同来自:

它是通过保存状态而作弊但它可以工作,将操作分成两部分:-n =(~n + 1)表示整数

int f(int n) {
    static int a = 1;
    a = !a;
    if (a) {
        return (~n);
    } else {
        return (n+1);
    }
}

eut

赞同来自:

这是Python中的一个。适用于n的所有负值:

f = abs

eomnis

赞同来自:

另一种方法是将状态保持在一位,并在负数的情况下小心地翻转二进制表示... 限制是2 ^ 29 int ffn(int 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;
        }
    }
}

cut

赞同来自:

除int.MaxValue和int.MinValue外的工作

    public static int f(int x)
    {
if (x == 0) return 0;
if ((x % 2) != 0)
            return x * -1 + (-1 *x) / (Math.Abs(x));
        else
            return x - x / (Math.Abs(x));
    }
pictorial

nerror

赞同来自:

这是rossfabricant答案的C实现。请注意,由于我始终坚持使用32位整数,因此f(f(2147483647))== 2147483647,而不是-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语句中使用的文字。

liste

赞同来自:

简单:

function f($n) {
   if ($n%2 == 0) return ($n+1)*-1;
   else return ($n-1);
}