Brain teaser: A more complicated way to negate integers

25 Jun
2013-06-25

Today, we will look at a brain teaser:

Design a function f() that operates on whole numbers, such that f(x) = y and f(y) = -x. Or, more succintly, f(f(x)) = -x.

I will help you analyze the problem, and contribute my suggestion for a solution, along with an explanation of why it works.

Spoiler warning! You WILL learn an answer to this question. If you want a challenge, attempt to solve the problem before reading the rest of the post 🙂

Think of it this way: f(x) produces some output, y, which must then contain enough information for f() to calculate -x in every case.

When I saw this, it wasn’t long before I realized a crucial property:

f(f(f(f(x))))) = x

This is obvious, since if f'(x) = f(f(x)), then f'(x) = -x, and thus f'(f'(x)) == f'(-x) == -(-x) == x.

This means that after 4 operations, the output is the starting value. Obvious, but also important.

If we can find 2 numeric measurable quanteties that each contain exactly 1 bit of information, we can use this to cycle through the 4 stages, since it takes exactly 2 bits to count to 4. Let’s call these 2 bits S and E, for reasons that will be clear later.

Or, in pseudo-python:

def S(x):
    ...

def E(x):
    ...

def is_stage1(x):
    return not S(x) and not E(x)

def is_stage2(x):
    return     S(x) and not E(x)

def is_stage3(x):
    return not S(x) and     E(x)

def is_stage4(x):
    return     S(x) and     E(x)

def f(x):
    if is_stage1(x):
        return map_1_to_2(x)
    elif is_stage2(x):
        return map_2_to_3(x)
    elif is_stage3(x):
        return map_3_to_4(x)
    else:
        return map_4_to_1(x)

That’s great. Now we just need to define S(x), E(x) and the map functions. However, the code is a bit cluttered, so let’s compact it a bit:

def f(x):
    if S(x):
        if E(x):
            return map_4_to_1(x)
        else:
            return map_2_to_3(x)
    else:
        if E(x):
            return map_3_to_4(x)
        else:
            return map_1_to_2(x)

We also need to satisfy the property, that any number mapped through one of the map functions, will change the output of either E(x), S(x) or both, such that a number mapped through all 4 stages will hit the conditions outlined in “is_stage1” through “is_stage4”.

Now we need to think of 2 measurable 1-bit quantities on whole numbers. One is pretty easy: the sign bit. The number is either positive or negative (0 counts as positive here). We’ll call the sign bit test S(x). The other one can be anything we like, but an easy one is whether the number is odd or even. We’ll call this E(x). Now the original naming should be appearant.

So, now we have:

def f(x):
    if x >= 0:
        if x % 2 == 0:
            return map_4_to_1(x)
        else:
            return map_2_to_3(x)
    else:
        if x % 2 == 0:
            return map_3_to_4(x)
        else:
            return map_1_to_2(x)

Almost there. Now we just need map functions, such that we will cause the corresponding truth values to be inverted, and the 4-step symmetry to be maintained.

Specifically, since we need to go: Original integer -> Something -> Negative original, we have the following patterns:

Even -> Something -> Negative Even
Odd -> Something -> Negative Odd
Negative Even -> Something -> Even
Negative Odd -> Something -> Odd

It’s clear that we must use the even-bit as the middle counter, and the sign bit as the outer counter. In this way, we get

Even -> Negative Odd -> Negative Even
Odd -> Even -> Negative Odd
Negative Even -> Odd -> Even
Negative Odd -> Negative Even -> Odd

The 4-step cycle then looks like this:

Even -> Negative Odd -> Negative Even -> Odd -> Even

After 4 steps, we are back where we started. In actual python, this is:

def f(x):
    if x >= 0:
        if x % 2 == 0:
            return -x - 1
        else:
            return x - 1
    else:
        if x % 2 == 0:
            return -x + 1
        else:
            return x + 1

And if you want to see it in action, try this extra code. It demonstrates what happens around the limits of an 8-bit integer, which is interesting, since throwing 2-complements notation into the mix makes the problem even harder. My answer does NOT take this into account, for simplicity. Bonus problem: Can you explain why the reality of 2-complement notation makes this problem harder around the edge cases? Can it be fixed? If so, how?

import ctypes

def u8(s):
    return ctypes.c_uint8(s).value

def s8(s):
    return ctypes.c_int8(s).value

def demo(x):
    a = f(x)
    b = f(a)
    c = f(b)
    d = f(c)
    print "0x%02x: %2d -> %2d -> %2d -> %2d -> %2d" % (
        x, s8(x), s8(a), s8(b), s8(c), s8(d)
        )

for x in range(0, 10):
    demo(x)

print "---"

for x in range(120, 140):
    demo(x)

print "---"

for x in range(250, 260):
    demo(x)
VN:F [1.9.22_1171]
Rating: 8.8/10 (9 votes cast)
Brain teaser: A more complicated way to negate integers, 8.8 out of 10 based on 9 ratings
6 replies
  1. MartinK says:

    *cough* Complex Numbers *cough*

    cpx num = 2;

    f(num) => 2i
    f(num) => -2
    f(num) => -2i
    f(num) => 2

    VA:F [1.9.22_1171]
    Rating: 0.0/5 (0 votes cast)
    Reply
    • Christian says:

      Absolutely!!

      I should have specified that it’s a programming challenge, so you have to operate within the limits of binary integers.

      Still, there’s a hilariously large number of mapping functions possible. Complex Numbers is definitely one of them, yes. And of course you could implement that in a number of ways.

      In fact, care to contribute some pseudo-code? 🙂

      VN:F [1.9.22_1171]
      Rating: 0.0/5 (0 votes cast)
      Reply
  2. MartinK says:

    well… if the system understand complex numbers then:

    public cpx f ( cpx num )
    {
       return num * i   // i being the complex part .. i*i = -1
    }
    public int RealPartOfCpx( cpx num )
    {
       return real ( num )
    }
    
    alternatively:
    public class ComplexPolar
    {
       int real
       int degree
    }
    
    public f ( ComplexPolar num )
    {
      num.degree += 90;
      if( num.degree == 360) num.degree = 0;
      return num
    }
    
    public ComplexPolarToReal( ComplexPolar num )
    {
        if ( num.degree == 0 || num.degree == 90)
           return abs ( num.real )
       else
           return num.real * -1
    }
    
    VA:F [1.9.22_1171]
    Rating: 0.0/5 (0 votes cast)
    Reply
  3. Christian says:

    You return the Real value at 0 and 90 degrees, and the negative value of the Real value at any other angle. That seems wrong.

    Also, the “f” function in the alternate-version is now basically a counter, which also goes against the spirit of the question.

    A proper no-tricks solution should operate only on an integer, with no other state being involved.

    It’s true that packing a complex number into 2 integers can sort of do that, but you could also just say that the top 2 bits are reserved for counting how many times the number has been through f(). That’s basically a bit of a cheat, I think 😉

    VN:F [1.9.22_1171]
    Rating: 0.0/5 (0 votes cast)
    Reply
  4. MartinK says:

    Your task smells like some embedded system that are very limited…

    VA:F [1.9.22_1171]
    Rating: 0.0/5 (0 votes cast)
    Reply
    • Christian says:

      It’s a brain teaser. It’s not meant to be directly applicable to a situation. It’s just good exercise 🙂

      VN:F [1.9.22_1171]
      Rating: 0.0/5 (0 votes cast)
      Reply

Leave a Reply

Want to join the discussion?
Feel free to contribute!

Leave a Reply

Your email address will not be published. Required fields are marked *

© Copyright - Christian Iversen's blog
UA-41598088-1