首页 文章

设计函数f（f（n））== -n [关闭]

提问于
浏览 次
837

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

设计函数f，使得：f（f（n））== - n
其中n是32位有符号整数;你不能使用复数运算 . 如果您无法为整个数字范围设计这样的功能，请尽可能设计它 .

有任何想法吗？

math integer

30 回答

  • 7

    没有人说f（x）必须是同一类型 .

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


f(2) => [2]
f(f(2)) => -2
    回复于
  • 280

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

    回复于
  • 16

    你没有说他们期望的那种语言......这是一个静态的解决方案（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()
    回复于
  • 20

    或者，您可能滥用预处理器：

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

int main()
{
  int n = -42;
  cout << "f(f(" << n << ")) = " << f(f(n)) << endl;
}
    回复于
  • 19

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

    • 我首先会问"Why would such a function be needed? What is the bigger problem this is part of?"而不是试图当场解决实际提出的问题 . 这显示了我的思考方式以及我如何解决这样的问题 . 谁知道？这甚至可能是首先在面试中提出问题的实际原因 . 如果答案是"Never you mind, assume it's needed, and show me how you would design this function."，我会继续这样做 .

    • 然后，我会编写我将使用的C＃测试用例代码（显而易见：从 int.MinValue 循环到 int.MaxValue ，对于该范围内的每个 n 调用 f(f(n)) 并检查结果是 -n ），告诉我然后使用测试驱动开发来得到这样的功能 .

    • 只有当面试官继续要求我解决所提出的问题时，我才真正开始尝试在面试过程中乱写伪代码以尝试获得某种答案 . 但是，如果面试官能够表明公司是什么样的话，我真的不认为我会跳起来接受这份工作......

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

    回复于
  • 18

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

    如果我没记错的话，你可以通过翻转第一位来否定一个带符号的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的平方根的乘法 .

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

    回复于
  • 26

    除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

    回复于
  • 61

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

    乘以-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)) = -x . f(x) 的结果也在此范围内，但当然计算需要64位整数 .

    回复于
  • 103

    The question doesn't say anything about what the input type and return value of the function f have to be （至少不是你提出来的方式）......

    ......只是当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 .

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

    回复于
  • 46

    这里有一个证明，为什么这样的函数不能存在，对于所有数字，如果它不使用额外的信息（除了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 . 总结一下：如果 f(x) = y ，那么 f(-x) = -y ， 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个数字作为奖励 . （但这只是一个愚蠢的 . ）

    回复于
  • 11

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

    • 将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

    回复于
  • 10

    这个Perl解决方案 works for integers, floats, and strings .

    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
    回复于
  • 375

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

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

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

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

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

    正如你所看到的，它只是一个补充，省去了所携带的位 .

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

    回复于
  • 48

    所有负数都是如此 .

    f(n) = abs(n)

    因为有两个负数而不是二进制补码整数的正数， f(n) = abs(n) 比 f(n) = n > 0 ? -n : 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 的应用 - 总共四个 - 否定了再次产生_251637的论点 .

    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 不是四的倍数 - 在四个长度的任何周期中都会有三个数字不存在 .

    我将使用范围从 -4 到 +3 的较小的3位有符号迭代集来解释解的剩余部分 . 我们完成零 . 我们有一个完整的周期 +1 => -2 => -1 => +2 => +1 . 现在让我们从 +3 开始构建循环 .

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

    出现的问题是 +4 不能表示为3位整数 . 我们通过否定 -3 到 +3 得到 +4 - 仍然是一个有效的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 并给我们留下两个失败的输入 . 所以不可能构造一个适用于所有值的函数，但是我们有一个适用于除一个之外的所有值的函数，这是我们可以实现的最佳值 .

    回复于
  • 439

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

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

    回复于
  • 47

    怎么样：

    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));
}
    回复于
  • 21

    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（下溢） .

    回复于
  • 13
    return x ^ ((x%2) ? 1 : -INT_MAX);
    回复于
  • 9

    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
    回复于
  • 12

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

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

    利用JavaScript异常 .

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

    f（f（0））=> 0 f（f（1））=> -1

    回复于
  • 136

    感谢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));
}
    回复于
  • 19

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

    回复于
  • 9

    本质上，函数必须将可用范围划分为大小为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)
    回复于
  • 96

    问题陈述"32-bit signed integers"但未指定它们是twos-complement还是ones-complement .

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

    在C：

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

    这是作品

    • 交换高16位块和低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)
    回复于
  • 147

    适用于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
}
    回复于
  • 16

    对于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;
}
    回复于
  • 12

    一个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;
}
    回复于
  • 10

    对于所有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循环与y => -y => y循环配对 . 所以我将 split 的两侧配对 .

    例如对于4位整数：

    0 => 7 => -8 => -7 => 0
1 => 6 => -1 => -6 => 1
2 => 5 => -2 => -5 => 2
3 => 4 => -3 => -4 => 3
    回复于
  • 16

    ：d

    boolean inner = true;

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

相关问题