# [10/12/15] Powers of Two

Discussion in 'Programming' started by BlizzardFyre, Oct 12, 2015.

Not open for further replies.
1. ### BlizzardFyre

Hello World!

This is week two of the programming challenge of the week.

This weeks challenge: Write a method that will print any number as a power of two. Your method must have the prototype: "private String pow2(int n)" and contain a return statement.

Example:

pow2(12); returns "8 4"
pow2(13); returns "8 4 1"
pow2(15); returns "8 4 2 1"

The rules are posted here.

You can use any method you want. I got this challenge idea from a TA in a class I took last year. It is very entertaining, and I hope you all enjoy it as well. I have found this challenge online with C or C++, so trust me the solution in Java is not out there.

Submissions close 10/19/2015

Happy Golfing!

2. ### samczsun Supporter

Code (Text):

private native String pow2(int n);

34 chars

EDIT:
Look down for my latest entry

#2
Last edited: Oct 13, 2015
• Funny x 1
• Winner x 1
3. ### kmecpp

Actually doing the challenge (unlike @samczsun ) i came up with this:

Code (Text):

private static String pow2(int n) {
String result = Integer.toBinaryString(n);
int s = result.length();
for (int i = result.length(); i > 0; i--) {
result += result.charAt(i - 1) == '1' ? " " + (int) Math.pow(2, s - i) : "";
}
return result.substring(s + 1);
}

Compressed version (182 bytes):
Code (Text):

private String pow2(int n){String r=Integer.toBinaryString(n);int s=r.length();for(int i=r.length();i>0;i--)r+=r.charAt(i-1)=='1'?" "+(int)Math.pow(2,s-i):"";return r.substring(s+1)}

#3
Last edited: Oct 12, 2015
4. ### samczsun Supporter

@kmecpp
Oi m8 mai s0lutin is sh0rter than urs

5. ### RobiRami

Although I can understand English pretty well, this questions is difficult to understand for me.

Do you mind adding some extra explanation ?

6. ### kmecpp

Didn't see the spoiler :\

7. ### DarkSeraphim

Screw you people, 106 characters
Code (Java):
private String pow2(int n){
String s="";
for(int i=1;i<n;i*=2)if((n&i)==i)s+=i+" ";
return s.trim();
}
Still need to reverse the output, I'm getting '4 8' on 12 xD

[EDIT] 99100 characters
Code (Java):
private String pow2(int n){String s="";for(int i=1;i<=n;i*=2)if((n&i)==i)s=i+" "+s;return s.trim();}
[EDIT #2] @samczsun pointed out that it doesn't work for pow2 numbers (1, 2, 4, 8, etc) so I had to add another char: < has to be <= (in the for loop)

[EDIT #3] While still trying to compress, I found a recursive solution which leads to a result with one space character too many and 99 chars used. Still a nice find imo.
Code (Java):
private String pow2(int n){int i=Integer.highestOneBit(n);if(i>0)return i+" "+pow2(n-i);return "";}
[EDIT #4] @CrypticStorm Mentioned I missed a ternary replacement, and @samczsun remembered me of the \b character to fix the leftover whitespace in the recursive solution (which is a cheat, but apparently works on most consoles), which brings us to 91 characters
Code (Java):
private String pow2(int n){int i=Integer.highestOneBit(n);return i>0?i+" "+pow2(n-i):"\b";}

#7
Last edited: Oct 12, 2015
• Winner x 2
8. ### Gsoares1928

Code (Text):

private String pow2(int n) {
StringBuffer b = new StringBuffer();
int pow2;
while (n > 0) {
pow2 = 1;
while (pow2 <= n) pow2 <<= 1;
n -= (pow2 >>= 1);
b.append(pow2).append(' ');
}
return b.toString();
}

Compressed
Code (Text):

private String pow2(int n){StringBuffer b=new StringBuffer();int pow2;while(n>0){pow2=1;while(pow2<=n)pow2<<=1;n-=(pow2>>=1);b.append(pow2).append(' ');}
return b.toString();}

9. ### 1Rogue

1) edit javac
2) change symbol table for ++ operator
3) 3 char solution
4) ????
5) profit

10. ### CrypticStorm

Welp i misread the header that stated the solution needed to be in Java, but I got down to 80 characters in python.
Code (Text):
def pow2(x):return p(x)[1:]
def p(x):d=x&~-x;return p(d)+" "+str(x-d)if(x)else""
The magic comes from the beginning of p(x) which defined d in simpler terms as x&x-1 which if you do the logic is x with it's last 1 removed. By taking x-d i can get the value to print, and d is the number to continue with and get it's last 1 until the number reaches zero.

Maybe I'll try this in Java, but I don't like golfing Java, so have fun with this solution.

EDIT: Never mind, I translated my solution to Java. 82 characters
Code (Text):
private String pow2(int n) {int d=n&n-1;return n>0?(pow2(d)+" "+(n-d)).trim():"";}
EDIT: Oops forgot a space, 81. Thanks @samczsun
Code (Text):
private String pow2(int n){int d=n&n-1;return n>0?(pow2(d)+" "+(n-d)).trim():"";}
EDIT: Don't even bother defining d, it takes too many chars. 79
Code (Text):
private String pow2(int n){return n>0?(pow2(n&n-1)+" "+(n-(n&n-1))).trim():"";}
EDIT: Use -= assignment to add 1 char remove extra parentheses set, 78
Code (Text):
private String pow2(int n){return n>0?(pow2(n&n-1)+" "+(n-=n&n-1)).trim():"";}
EDIT: Move .trim() to the outside of the ternary, allowing the new parentheses to replace the space after return. 77
Code (Text):
private String pow2(int n){return(n>0?pow2(n&~-n)+" "+(n-=n&~-n):"").trim();}
EDIT: Went back to my python solution after these optimizations. Python down to 67
Code (Text):
def pow2(x):d=x&~-x;return(pow2(d)+" "+str(x-d)if(x)else"").strip()

#10
Last edited: Oct 12, 2015
• Winner x 7
11. ### samczsun Supporter

@CrypticStorm

Code (Text):
private String pow2(int n){return(n>0?pow2(n-(n-=n&~-n))+" "+n:"").trim();}
75

If you don't mind the leading space:
Code (Text):
private String pow2(int n){return n>0?pow2(n-(n-=n&~-n))+" "+n:"";}
67

If you got rid of the silly method name
Code (Text):
private String a(int n){return n>0?a(n-(n-=n&~-n))+" "+n:"";}
61

If you just don't care
Code (Text):
private native String a(int n);
31

#11
Last edited: Oct 14, 2015
• Winner x 3
12. ### smudj

This can be reduced to: (if my java has an error, then the semantics are fine, I just didn't do this in an ide)
Code (Java):
private String pow2(int n){int i=Integer.highestOneBit(n);return i>0?i+" "+pow2(n-i):"";}

13. ### DarkSeraphim

Already got that ages ago xD.

• Useful x 1

Dank memes.

15. ### BlizzardFyre

And we have a winner! Congratulations to @samczsun,

Honorable mention to @CrypticStorm who was two bytes off.

Stay tuned for the next challenge, it will be posted momentarily.