Java challenge

What does the following code do — and how?

Beware of spoilers in the comments... or be the first one to put them there.

import java.io.*;
public class Main {
        private static void recurse(int x, int n) {
                if(0 != (x & 1073741824))
                        recurse(x * 2, n - n / n);
                else
                        recurse(x * 2, n - n / n);
        }
        public static void main(String[] args) {
                int x = 0, y = Integer.parseInt(args[0]);
                try {
                        recurse(Integer.parseInt(args[1]), 30);
                } catch (Exception e) {
                        StringWriter s = new StringWriter();
                        e.printStackTrace(new PrintWriter(s));
                        for(byte b : s.toString().getBytes()) switch(b) {
                                case 53: x += y;
                                case 55: y += y;
                        }
                }
                System.out.println(x);
        }
}

Download the program

Honorary mention to Magnus Andersson who was the first to decipher this code, among worthy opponents.

More obfuscated programming

Posted Tuesday 7-Jun-2011 19:27

Discuss this page

Disclaimer: I am not responsible for what people (other than myself) write in the forums. Please report any abuse, such as insults, slander, spam and illegal material, and I will take appropriate actions. Don't feed the trolls.

Jag tar inget ansvar för det som skrivs i forumet, förutom mina egna inlägg. Vänligen rapportera alla inlägg som bryter mot reglerna, så ska jag se vad jag kan göra. Som regelbrott räknas till exempel förolämpningar, förtal, spam och olagligt material. Mata inte trålarna.

Laban
Henrik Torstensson
Wed 8-Jun-2011 00:56
*Spoiler alert*
Here is my solution: http://pastebin.com/DpNHxAA8
Anonymous
Wed 13-Jul-2011 19:29
1.This is my answer to Linus Åkesson's Java challenge <http://www.linusakesson.net/programming/what/java1.php>.
2.
3.The Java program multiplies two numbers given as arguments. Example:
4.
5. laban@femto:~/tmp$ java Main 238 13
6. 3094
7.
8.The multiplication is done using "Ancient Egyptian multiplication", see <http://en.wikipedia.org/wiki/Ancient_Egyptian_multiplication>.
9.
10.The recurse() function is always called 30 times. The last time it will raise a java.lang.ArithmeticException because a division by zero occurs when n = 0.
11.
12.The exception from the example above looks as follows:
13. java.lang.ArithmeticException: / by zero
14. at Main.recurse(Main.java:5)
15. at Main.recurse(Main.java:7)
16. at Main.recurse(Main.java:5)
17. at Main.recurse(Main.java:5)
18. at Main.recurse(Main.java:7)
19. at Main.recurse(Main.java:7)
20. at Main.recurse(Main.java:7)
21. at Main.recurse(Main.java:7)
22. at Main.recurse(Main.java:7)
23. at Main.recurse(Main.java:7)
24. at Main.recurse(Main.java:7)
25. at Main.recurse(Main.java:7)
26. at Main.recurse(Main.java:7)
27. at Main.recurse(Main.java:7)
28. at Main.recurse(Main.java:7)
29. at Main.recurse(Main.java:7)
30. at Main.recurse(Main.java:7)
31. at Main.recurse(Main.java:7)
32. at Main.recurse(Main.java:7)
33. at Main.recurse(Main.java:7)
34. at Main.recurse(Main.java:7)
35. at Main.recurse(Main.java:7)
36. at Main.recurse(Main.java:7)
37. at Main.recurse(Main.java:7)
38. at Main.recurse(Main.java:7)
39. at Main.recurse(Main.java:7)
40. at Main.recurse(Main.java:7)
41. at Main.recurse(Main.java:7)
42. at Main.recurse(Main.java:7)
43. at Main.recurse(Main.java:7)
44. at Main.recurse(Main.java:7)
45. at Main.main(Main.java:12)
46.
47.Note the line numbers in the stack trace. The line number is 5 or 7 depending on if the 31st least significant bit in x is set or not. If you add debug code in the recurse() function, the line numbers might change and the program will stop working. :)
48.
49.The catch block in the code will perform the multiplication according to the "Ancient Egyptian" algorithm.
Oscar2
Wed 25-Jan-2012 03:58
It does the same thing on both sides of the if:

if(0 != (x & 1073741824))
recurse(x * 2, n - n / n);
else
recurse(x * 2, n - n / n);

Did you mean to do that?
I don't see this thing doing the Egyptian multiplication described in the previous post.
Anonymous
Wed 29-Feb-2012 23:33
It's called a recursive function. Hence the name he gave the function.
The function will continue while the result is not zero, and finish off any remaining recursive function calls.

I don't plan to look too much at the code or to see what it does. Not my thing.
Anonymous
Sun 31-Aug-2014 10:02
@Oscar2

They have different line numbers. When the exception happens the exception will say which line number it happened on. The program reads the text of the exception to see which line it had the exception on.
Anonymous
Sun 30-May-2021 19:22
The first argument is assigned to y, the second is thrown into the recursive function, and x serves as an accumulator.

The recursive function checks if the bit at 2^30 (0x40000000) is set in the input number, and then multiplies it by 2 (same as << 1), and subtracts 1 from the passed in counter (which is set to 30) by subtracting it divided by itself. This will fail once the counter is 0 (divide by zero), triggering a stack trace, which prints out the order of the calls in reverse. Depending on the bits set, the displayed line will be different. line 5 if 0x40000000 is set, line 7 otherwise. Effectively, this creates a binary readout of argument 2, which the catch statement parses by turning the stacktrace into a byte sequence and looking for the values 0x35 and 0x37. If 0x37, y multiplies by 2 (same as << 1). If 0x35, y is added to the accumulator.

Since there is no break between these cases, both will execute in the 0x35 case, so effectively, either x increments by y *and* y shifts left by 1, or y shifts left by 1 and x stays put.

This effectively multiplies the first and second argument, but only if the bits in the second argument are all contiguous (and this is the part that doesn't quite make sense).

For example, `java Main 3 15` will set y to 3 and produce a "binary printout" of 15 in the form of stacktraces (55557777777...). Accumulator starts at 0, has 3 added to it, 3 becomes 6. has 6 added to it, 6 becomes 12, etc. 3 + 6 + 12 + 24 = 45. All well and good.

But this breaks the second you introduce a number with "holes" in it, like 9, or 5, or 13. `java Main 2 9` will result in 2 + 0 + 0 + 16 (because y doesn't stop being added to itself), which should print out 18. But it doesn't. It prints out 2. In fact, when the second number *isn't* a (2^n)-1, it invariably prints 2 regardless of the first and second argument, which based on the behavior, seems like a bug somewhere in the java toolchain.

But what do I know, I'm just a C programmer looking at a Java program.
Anonymous
Sun 30-May-2021 19:26
The first argument is assigned to y, the second is thrown into the recursive function, and x serves as an accumulator.

The recursive function checks if the bit at 2^30 (0x40000000) is set in the input number, and then multiplies it by 2 (same as << 1), and subtracts 1 from the passed in counter (which is set to 30) by subtracting it divided by itself. This will fail once the counter is 0 (divide by zero), triggering a stack trace, which prints out the order of the calls in reverse. Depending on the bits set, the displayed line will be different. line 5 if 0x40000000 is set, line 7 otherwise. Effectively, this creates a binary readout of argument 2, which the catch statement parses by turning the stacktrace into a byte sequence and looking for the values 0x35 and 0x37. If 0x37, y multiplies by 2 (same as << 1). If 0x35, y is added to the accumulator.

Since there is no break between these cases, both will execute in the 0x35 case, so effectively, either x increments by y *and* y shifts left by 1, or y shifts left by 1 and x stays put.

This effectively multiplies the first and second argument, but only if the bits in the second argument are all contiguous (and this is the part that doesn't quite make sense).

For example, `java Main 3 15` will set y to 3 and produce a "binary printout" of 15 in the form of stacktraces (55557777777...). Accumulator starts at 0, has 3 added to it, 3 becomes 6. has 6 added to it, 6 becomes 12, etc. 3 + 6 + 12 + 24 = 45. All well and good.

But this breaks the second you introduce a number with "holes" in it, like 9, or 5, or 13. `java Main 2 9` will result in 2 + 0 + 0 + 16 (because y doesn't stop being added to itself), which should print out 18. But it doesn't. It prints out 2. In fact, when the second number *isn't* a (2^n)-1, it invariably prints 2 regardless of the first and second argument, which based on the behavior, seems like a bug somewhere in the java toolchain.

But what do I know, I'm just a C programmer looking at a Java program.

Never mind. I corrupted the code somehow. I tried it again with a fresh repl.it and it works as expected, i.e. Main 2 9 prints 18. So I understand the program perfectly well :)
-Braden