# [10/12/15] Powers of Two

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

Not open for further replies.
1. 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. 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. 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. 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. Already got that ages ago xD.

• Useful x 1
14. Dank memes.

15. 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.