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

Question

我上次采访时遇到的一个问题:

设计一个函数f,这样:

f(f(n)) == -n

哪里n是32位有符号整数 ; 你不能使用复数运算.

如果您无法为整个数字范围设计此类功能,请将其设计为可能的最大范围.

有任何想法吗？

Answer 1

你没有说他们期望的那种语言......这是一个静态的解决方案(Haskell).它基本上搞乱了2个最重要的位:

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()

Answer 2

怎么样:

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自动将整数提升为任意长度的长度.在其他语言中,最大的正整数将溢出,因此它将适用于除了那个之外的所有整数.

为了使之成为真正的数字工作,你需要更换ñ在(-1)^ñ用{ ceiling(n) if n>0; floor(n) if n<0 }.

在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));
}

Answer 3

这里有一个证明,为什么这样的函数不能存在,对于所有数字,如果它不使用额外的信息(除了32位的int):

我们必须有f(0)= 0.(证明:假设f(0)= x.那么f(x)= f(f(0))= - 0 = 0.现在,-x = f(f(x ))= f(0)= x,这意味着x = 0.)

此外,对于任何x和y,假设f(x) = y.我们f(y) = -x当时想要.并且f(f(y)) = -y => f(-x) = -y.总结一下:if f(x) = y,then f(-x) = -y,and f(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个号码作为奖励.(但这只是一个愚蠢的.)

Answer 4

感谢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));
}

Answer 5

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

#define f(n) (f##n)
#define ff(n) -n

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

Answer 6

所有负数都是如此.

    f(n) = abs(n)

因为对于二进制补码整数,有一个负数而不是正数,f(n) = abs(n)所以对于另一个案例而言f(n) = n > 0 ? -n : n,这个数字与解决方案相同f(n) = -abs(n).得到你一个......:D

UPDATE

不,它对于一个案例更有效,因为我刚刚被litb的评论所认可...... abs(Int.Min)将会溢出......

我也考虑过使用mod 2信息,但总结说,它早期不起作用.如果做得好,它将适用于所有数字,除非Int.Min因为它会溢出.

UPDATE

我玩了一段时间,寻找一个很好的位操作技巧,但我找不到一个漂亮的单行,而mod 2解决方案适合一个.

    f(n) = 2n(abs(n) % 2) - n + sgn(n)

在C#中,这将成为以下内容:

public static Int32 f(Int32 n)
{
    return 2 * n * (Math.Abs(n) % 2) - n + Math.Sign(n);
}

得到它的工作对于所有的值,必须更换Math.Abs()与(n > 0) ? +n : -n和包括在计算unchecked块.然后你甚至Int.Min可以像未经检查的否定一样映射到自己.

UPDATE

受另一个答案的启发,我将解释该函数如何工作以及如何构造这样的函数.

让我们从一开始就开始吧.该函数f重复应用于给定值,n产生一系列值.

    n => f(n) => f(f(n)) => f(f(f(n))) => f(f(f(f(n)))) => ...

问题要求f(f(n)) = -n,即两个连续的应用f否定论证.两个进一步的应用f- 总共四个 - 否定了再次屈服的论点n.

    n => f(n) => -n => f(f(f(n))) => n => f(n) => ...

现在有一个明显的长度为四的循环.代入x = f(n)并注意到所获得的等式f(f(f(n))) = f(f(x)) = -x成立,得到以下结果.

    n => x => -n => -x => n => ...

所以我们得到一个长度为4的循环,有两个数字,两个数字都被否定了.如果您将循环想象为矩形,则否定的值位于相对的角上.

构建这样一个循环的许多解决方案之一是从n开始的以下.

 n                 => negate and subtract one
-n - 1 = -(n + 1)  => add one
-n                 => negate and add one
 n + 1             => subtract one
 n

这样一个循环的具体例子是+1 => -2 => -1 => +2 => +1.我们差不多完成了.注意到构造的循环包含一个奇数正数,它甚至是后继数,并且两个数字都是否定的,我们可以很容易地将整数分成许多这样的循环(2^32是四的倍数)并找到满足条件的函数.

但我们有零问题.循环必须包含,0 => x => 0因为零被否定于自身.并且因为循环已经0 => x说明了0 => x => 0 => x.这只是一个长度为2的循环,x在两个应用程序之后变为自身,而不是-x.幸运的是,有一个案例解决了这个问题.如果X等于零,我们得到一个长度为1的循环,只包含零,我们解决了这个问题,得出的结论是零是一个固定点f.

完成了吗？几乎.我们有2^32数字,零是一个固定点,留下2^32 - 1数字,我们必须将这个数字划分为四个数字的周期.坏2^32 - 1的不是四的倍数 - 在长度为四的任何循环中都会有三个数字.

我将解释使用较小的一套3个有符号itegers从溶液中的剩余部分-4来+3.我们完成零.我们有一个完整的周期+1 => -2 => -1 => +2 => +1.现在让我们从开始构建循环+3.

    +3 => -4 => -3 => +4 => +3

出现的问题+4是不能表示为3位整数.我们将获得+4由否定-3到+3什么仍然是一个有效的3位整数- -但后来加入一个+3(二进制011)产生100的二进制文件.解释为无符号整数,+4但我们必须将其解释为有符号整数-4.所以实际上-4对于这个例子或者Int.MinValue在一般情况下是整数算术否定的第二个固定点 - 0 并且Int.MinValue被映射到它们.所以这个周期实际上如下.

    +3 =>    -4 => -3 => -4 => -3

它是一个长度为2 +3的循环,另外进入循环通道-4.因此-4,在两个函数应用程序之后正确映射到自身,在两个函数应用程序之后+3正确映射到-3,但-3在两个函数应用程序之后错误地映射到自身.

所以我们构造了一个适用于所有整数但只有一个整数的函数.我们可以做得更好吗？不,我们不可以.为什么？我们必须构造长度为4的循环,并且能够覆盖整个范围,最多四个值.剩余值是两个固定点0和Int.MinValue必须被映射到自身和两个任意的整数x,并-x必须由两个功能的应用程序被映射到彼此.

要映射x到-x反之亦然,它们必须形成四个周期,并且它们必须位于该周期的相对角.因此0,Int.MinValue也必须在对面的角落.这将正确映射x并-x交换两个固定点,0并Int.MinValue在两个函数应用程序之后,并给我们留下两个失败的输入.所以不可能构造一个适用于所有值的函数,但是我们有一个适用于除一个之外的所有值的函数,这是我们能够实现的最佳值.

Answer 7

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

• 将n乘以i,得到n*i,即逆时针旋转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.

Answer 8

除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));
    }

Answer 9

问题并没有说明函数的输入类型和返回值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将为true.

显然,这种方法可以扩展到更广泛的数字......

Answer 10

对于javascript(或其他动态类型语言),您可以让函数接受int或object并返回另一个.即

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;
}

Answer 11

根据您的平台,某些语言允许您在功能中保持状态.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),但它比目前为止提出的任何其他方法都要好得多.

Answer 12

利用JavaScript异常.

function f(n) {
    try {
        return n();
    }
    catch(e) { 
        return function() { return -n; };
    }
}

f(f(0)) => 0

f(f(1)) => -1

Answer 13

对于所有32位值(警告-0为-2147483648)

int rotate(int x)
{
    static const int split = INT_MAX / 2 + 1;
    static const int negativeSplit = INT_MIN / 2 + 1;

    if (x == INT_MAX)
        return INT_MIN;
    if (x == INT_MIN)
        return x + 1;

    if (x >= split)
        return x + 1 - INT_MIN;
    if (x >= 0)
        return INT_MAX - x;
    if (x >= negativeSplit)
        return INT_MIN - x + 1;
    return split -(negativeSplit - x);
}

你基本上需要将每个-x => x => -x循环与ay => -y => y循环配对.所以我把它的两侧配对了split.

例如,对于4位整数:

0 => 7 => -8 => -7 => 0
1 => 6 => -1 => -6 => 1
2 => 5 => -2 => -5 => 2
3 => 4 => -3 => -4 => 3

Answer 14

一个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;
}

Answer 15

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

Answer 16

使用全局...但是这样呢？

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

Answer 17

此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

Answer 18

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

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


f(2) => [2]
f(f(2)) => -2

Answer 19

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

• 我首先会问"为什么需要这样的功能？这是一个更重要的问题是什么？" 而不是试图当场解决实际提出的问题.这显示了我的思考方式以及我如何解决这样的问题.谁知道？这甚至可能是首先在面试中提出问题的实际原因.如果答案是"从不介意,假设需要它,并告诉我你将如何设计这个功能." 然后我会继续这样做.
• 然后,我会写C#测试用例代码,我会用(明显:循环从int.MinValue到int.MaxValue,并为每个n在该范围内的通话f(f(n))和检查结果-n),告诉然后我会使用测试驱动开发来获得这样的功能.
• 只有当面试官继续要求我解决所提出的问题时,我才真正开始尝试在面试过程中写下伪代码,试图找到某种答案.但是,如果面试官能够表明公司是什么样的话,我真的不认为我会跳起来接受这份工作......

哦,这个答案假设面试是针对C#编程相关的职位.如果面试是针对数学相关的职位,那当然是一个愚蠢的答案.;-)

Answer 20

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

00.... => 01.... => 10.....

01.... => 10.... => 11.....

10.... => 11.... => 00.....

11.... => 00.... => 01.....

正如你所看到的,它只是一个补充,遗漏了携带的位.

我是怎么得到答案的？我的第一个想法只是需要对称性.4转回到我开始的地方.起初我想,那是2位格雷码.然后我认为实际上标准二进制就足够了.

Answer 21

这是一个灵感来自要求或声称复杂数字不能用于解决此问题的解决方案.

乘以-1的平方根是一个想法,它似乎只是失败,因为-1在整数上没有平方根.但是,玩像mathematica这样的程序就可以得到例子

(1849436465 ² +1)mod(2 ³² -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)

这满足f(f(x)) = -x范围内的所有整数.结果也在这个范围内,但当然计算需要64位整数.[-231-2, 231-2]f(x)

Answer 22

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

Answer 23

本质上,函数必须将可用范围划分为大小为4的周期,其中-n位于n周期的另一端.但是,0必须是大小为1的循环的一部分,否则0->x->0->x != -x.因为0是单独的,所以我们的范围中必须有3个其他值(其大小是4的倍数),而不是在具有4个元素的适当循环中.

我选择了这些额外的怪异值是MIN_INT,MAX_INT和MIN_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)

Answer 24

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

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

Answer 25

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

Answer 26

适用于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
}

Answer 27

该问题表示"32位有符号整数",但未指定它们是二进制补码还是单补码.

如果使用one-complement,则所有2 ^ 32值都以长度为4的周期出现 - 您不需要特殊情况为零,并且您也不需要条件.

在C:

int32_t f(int32_t x)
{
  return (((x & 0xFFFFU) << 16) | ((x & 0xFFFF0000U) >> 16)) ^ 0xFFFFU;
}

这是作品

1. 交换高和低16位块
2. 反转其中一个块

两次传递后,我们得到原始值的按位反转.其中补码表示等同于否定.

例子:

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)

Answer 28

:d

boolean inner = true;

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

Answer 29

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

Answer 30

作为一名数学家,我想就这个有趣的问题分享我的观点.我想我有最有效的解决方案.

如果我没记错的话,你可以通过翻转第一位来否定一个带符号的32位整数.例如,如果n = 1001 1101 1110 1011 1110 0000 1110 1010,则-n = 0001 1101 1110 1011 1110 0000 1110 1010.

那么我们如何定义一个函数f,该函数f采用带符号的32位整数并返回另一个带符号的32位整数,其中f取两次的属性与翻转第一位相同？

让我在不提及像整数这样的算术概念的情况下重新解释这个问题.

我们如何定义一个函数f,它接受一个零序列和一个长度为32的序列并返回一个零序列和一个相同长度的序列,其中f取两次的属性与翻转第一位相同？

观察:如果您能回答上述问题的32位情况,那么您也可以回答64位情况,100位情况等.您只需将f应用于前32位.

现在,如果你能回答2位案件的问题,瞧!

是的,事实证明改变前2位就足够了.

这是伪代码

1. take n, which is a signed 32-bit integer.
2. swap the first bit and the second bit.
3. flip the first bit.
4. return the result.

备注:步骤2和步骤3一起可以夏令时为(a,b) - >( - b,a).看起来很熟悉？这应该提醒你平面的90度旋转和-1的平方根的乘法.

如果我只是单独提出伪代码而没有很长的前奏,它看起来像是一只兔子,我想解释我是如何得到解决方案的.

Answer 31

在PHP中

function f($n) {
    if(is_int($n)) {
        return (string)$n;
    }
    else {
        return (int)$n * (-1);
    }
}

我相信你能理解这种方法对其他语言的精神.我明确地将其转换回int,以使那些不使用弱类型语言的人更清楚.你必须为某些语言重载函数.

关于这个解决方案的巧妙之处在于,无论是以字符串还是整数开头,它都有效,并且在返回f(n)时不会明显改变任何东西.

在我看来,采访者问,"这位候选人是否知道如何标记数据以便稍后进行操作",并且"这位候选人是否知道如何标记数据,同时最少改变数据？" 您可以使用双打,字符串或任何其他您想要投射的数据类型来执行此操作.

Answer 32

这很简单!

每个数字以4的周期映射到另一个数字,其中所需条件成立.

例:

规则是:

• 0→0

• ±2³¹→±2³¹

• 奇数→偶数,偶数→-odd:

  forall k,0 <k <2³⁰:(2k-1)→(2k)→( - 2k + 1)→( - 2k)→(2k-1)

唯一不匹配的值是±(2³¹-1),因为只有两个.必须有两个不能匹配,因为在二进制补码系统中只有四个数字的倍数,其中0和±2³¹已被保留.

在一个补码系统中,存在+0和-0.我们去:

forall k,0 <k <2³⁰:(+ 2k)→(+ 2k + 1)→( - 2k)→( - 2k-1)→(+ 2k)

Answer 33

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

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

Answer 34

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

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