So you are given a base 10 (decimal) number. Your job is to reverse the binary digits and return that base 10 number.

Examples:

1 => 1 (1 => 1)
2 => 1 (10 => 01)
3 => 3 (11 => 11)
4 => 1 (100 => 001)
5 => 5 (101 => 101)
6 => 3 (110 => 011)
7 => 7 (111 => 111)
8 => 1 (1000 => 0001)
9 => 9 (1001 => 1001)
10 => 5 (1010 => 0101)

This is a challenge, so the solution that uses the least bytes wins.

share|improve this question
1  
Does "reverse the bits" mean reverse its binary digits? Sometimes it can also mean invert every bit. – ETHproductions 2 days ago
    
Yes. Sorry for being unclear. – juniorRubyist 2 days ago
    
This and this are veeeeery similar. – Geobits 2 days ago
    
OEIS A030101. – orlp 2 days ago
11  
Will the input always be positive? – Dennis 2 days ago

32 Answers 32

Python, 29 bytes

lambda n:int(bin(n)[:1:-1],2)

Try it online

share|improve this answer
1  
This is what I would have done. ;) – juniorRubyist 2 days ago

Python, 29 bytes

lambda n:int(bin(n)[:1:-1],2)

Try it online!

This is an anonymous, unnamed function which returns the result.


First, bin(n) converts the argument to a binary string. We would ordinarily reverse this with the slice notation [::-1]. This reads the string with a step of -1, i.e. backwards. However, binary strings in Python are prefixed with an 0b, and therefore we give the slicing's second argument as 1, telling Python to read backwards terminating at index 1, thus not reading indexes 1 and 0.

Now that we have the backwards binary string, we pass it to int(...) with the second argument as 2. This reads the string as a base 2 integer, which is then implicity returned by the lambda expression.

share|improve this answer
2  
Beat you by 9 seconds. – mbomb007 2 days ago
    
@mbomb007 I beat you a few seconds too I guess, but I made a small mistake so I deleted mine xP – busukxuan 2 days ago
3  
5  
@mbomb007 so my answer is invalid because you clicked the post button 9 seconds before hand? Just because we reach the same golf at the same time doesn't mean we have to delete any answers. If anything, blame the 0-effort question. – FlipTack 2 days ago
2  
Not invalid, but definitely pointless. If I had been slower, I'd simply delete mine and post a comment on the faster one that I came up with it too. – mbomb007 2 days ago

JavaScript (ES6), 30 bytes

f=(n,q=0)=>n?f(n>>1,q*2+n%2):q

This basically calculates the reverse one bit at a time: We start with q = 0; while n is positive, we multiply q by 2, sever the last bit off of n with n>>1, and add it to q with +n%2. When n reaches 0, the number has been successfully reversed, and we return q.

Thanks to JS's long built-in names, solving this challenge the easy way takes 44 bytes:

n=>+[...n.toString(2),'0b'].reverse().join``

Using recursion and a string, you can get an alternate 32 byte solution:

f=(n,q='0b')=>n?f(n>>1,q+n%2):+q
share|improve this answer
    
f=(n,q)=>n?f(n>>1,q*2|n%2):q almost works. But sadly not for n=0. – Arnauld 2 days ago
    
@Arnauld OP has not yet replied as to whether the input will always be positive, but if so, then 0 doesn't have to be handled. – FlipTack 2 days ago

Java 8, 53 47 46 bytes

-4 bytes thanks to Titus

This is a lambda expression which has the same principle as ETH's answer (although recursion would have been too verbose in Java, so we loop instead):

x->{int t=0;for(;x>0;x/=2)t=t*2+x%2;return t;}

Try it online!

This can be assigned with IntFunction<Integer> f = ..., and then called with f.apply(num). Expanded, ungolfed and commented, it looks like this:

x -> { 
    int t = 0;           // Initialize result holder   
    while (x > 0) {      // While there are bits left in input:
        t <<= 1;         //   Add a 0 bit at the end of result
        t += x%2;        //   Set it to the last bit of x
        x >>= 1;         //   Hack off the last bit of x
    }              
    return t;            // Return the final result
};
share|improve this answer
    
Save 3 bytes with t*2 instead of (t<<1), one more with moving that calculation from loop head to loop body. Can You use x instead of x>0 for the condition? – Titus 2 days ago
1  
@Titus not without an explicit cast to a boolean, but thanks for the other tips! Also just realised that x>>=1 can be replaced with x/=2 as it will automatically be integer division. – FlipTack 2 days ago

Mathematica, 19 bytes

#~IntegerReverse~2&
share|improve this answer

J, 6 bytes

|.&.#:

|. reverse

&. under

#: base 2

share|improve this answer

Jelly, 3 bytes

BUḄ

Try it online!

B   # convert to binary
 U  # reverse
  Ḅ # convert to decimal
share|improve this answer
5  
That's pretty short, BUB – Cyoce 2 days ago
    
Hmm... Is that really 3 bytes? – aioobe 21 hours ago
    
@aioobe Yep. Jelly uses it's own code page where each of these characters is 1 byte. – Riley 21 hours ago
    
Cool, thanks! <pad> – aioobe 19 hours ago

Ruby, 29 28 bytes

->n{("%b"%n).reverse.to_i 2}

"%b" % n formats the input n as a binary string, reverse, then convert back to a number

Usage/Test cases:

m=->n{("%b"%n).reverse.to_i 2}
m[1] #=> 1
m[2] #=> 1
m[3] #=> 3
m[4] #=> 1
m[5] #=> 5
m[6] #=> 3
m[7] #=> 7
m[8] #=> 1
m[9] #=> 9
m[10] #=> 5
share|improve this answer
    
@Titus I think you misunderstand the answer. 2 is the base he is converting to, and n is the input. ->args{return value} is the ruby lambda syntax – Cyoce 2 days ago
    
Can you remove the parentheses in .to_i(2)? – Cyoce 2 days ago
    
@Cyoce sure enough, thanks. – Alexis Andersen 2 days ago

C, 48 44 43 42 bytes

-1 byte thanks to gurka and -1 byte thanks to anatolyg:

r;f(n){for(r=n&1;n/=2;r+=r+n%2);return r;}

Previous 44 bytes solution:

r;f(n){r=n&1;while(n/=2)r=2*r+n%2;return r;}

Previous 48 bytes solution:

r;f(n){r=0;while(n)r=2*(r+n%2),n/=2;return r/2;}

Ungolfed and usage:

r;
f(n){
 for(
  r=n&1;
  n/=2;
  r+=r+n%2
 );
 return r;}
}


main() {
#define P(x) printf("%d %d\n",x,f(x))
P(1);
P(2);
P(3);
P(4);
P(5);
P(6);
P(7);
P(8);
P(9);
P(10);
}
share|improve this answer
    
Isn't r already initialized to zero here r;f(n){r=0;, e.g. the r=0; is unnecessary? Also minor typo: "Previous 48 bytes solution" – gurka 2 days ago
1  
@gurka The function should be reusable. – Karl Napf 2 days ago
1  
I think that for loops are always at least as short as while loops, and often shorter. – anatolyg yesterday
    
@anatolyg something like: r;f(n){for(r=n&1;n/=2;r=2*r+n%2);return r;}? 1 byte shorter, but I'm unsure if it's valid C (C99). – gurka yesterday
    
Yes; also, turn = into += to make it shorter and more obfuscated – anatolyg yesterday

05AB1E, 3 bytes

bRC

Try it online!

share|improve this answer

Bash/Unix utilities, 24 bytes

dc<<<2i`dc<<<2o$1p|rev`p

Try it online!

share|improve this answer

Java 8, 84 79 73 72 bytes

a->a.valueOf(new StringBuffer(a.toString(a,2)).reverse().toString(),2);

Lambda expression. Converts to binary representation, reverses, parses the string in base 2.

-5 bytes thanks to Poke!

-6 more bytes thanks to Poke!

-1, Poke has done more golfing on this than me by now.

share|improve this answer
    
Even though REPL submissions are allowed, they still follow the rule that you can't assume input is in predefined variables (like a in this context) – FlipTack 2 days ago
    
@FlipTack Oops. It was originally a function before I remembered the repl existed – Pavel 2 days ago
    
Well I suppose you can just do a-> at the start to make it a lambda expression and cut out the println. That might make it shorter. – FlipTack 2 days ago
1  
Also, in the future, use print instead of println for golfing :) – FlipTack 2 days ago
    
As far as I can tell, this prints the reverse binary string, rather than evaluating it as a new integer. – FlipTack 2 days ago

Haskell, 36 bytes

0!b=b
a!b=div a 2!(b+b+mod a 2)
(!0)

Same algorithm (and length!) as ETHproductions’ JavaScript answer.

share|improve this answer

Labyrinth, 89 bytes

2}?_";:_2%}_2/"";{:_2-;;_";!#;@
    "        " "     ;   "  "
    "1_""""""" "1_""""   """"

I'm sure there's a way to reduce loop bytes, but this took long enough to make.

share|improve this answer
    
Welcome to PPCG, and nice first post! Just completing a challenge in a language like Labyrinth can be very difficult. Around here, we usually prefix the first line of an answer with one or two hashes, to make it show as a header: # Labyrinth, 89 bytes – ETHproductions yesterday
    
Thanks! Now I know. – C Anderson yesterday

Pyth, 6 bytes

i_.BQ2

Test suite available here.

Explanation

i_.BQ2
    Q     eval(input())
  .B      convert to binary
 _        reverse
i    2    convert from base 2 to base 10
share|improve this answer

Perl 6, 19 bytes

{:2(.base(2).flip)}
share|improve this answer
    
Where is the input? – Titus 2 days ago
    
This is a function that takes a single parameter $_. It isn't mentioned by name, but the base method is called on it. – Sean 2 days ago
1  
@Titus in Perl 6 a Block is a type of Code, which is to say it's a callable object. The above is an expression that you can take and assign to a variable like a function or lambda in another language, or call directly — {:2(.base(2).flip)}(10) at the REPL will print 5. So it meets the standard code-golf criteria for a function. – hobbs yesterday

Japt, 5 bytes

¢w n2

Try it Online!

share|improve this answer
1  
Nice, exactly what I had. The ) could be a space too :-) – ETHproductions 2 days ago

MATL, 4 bytes

BPXB

Try it online!

Explanation

B     % Input a number implicitly. Convert to binary array
P     % Reverse array
XB    % Convert from binary array to number. Display implicitly
share|improve this answer

Mathematica, 38 bytes

#+##&~Fold~Reverse[#~IntegerDigits~2]&
share|improve this answer

Groovy, 46 bytes

{0.parseInt(0.toBinaryString(it).reverse(),2)}
share|improve this answer
    
Does this take any input? – Titus 2 days ago
1  
@Titus it refers to the argument given to a block IIRC – Cyoce 2 days ago
    
I love how this is the same length as my Java answer - Java and groovy, unite! – FlipTack 2 days ago
1  
@FlipTack I'm gonna go cry now. – carusocomputing 2 days ago

CJam, 8 bytes

ri2bW%2b

Try it online!

Explanation

ri          e# Read integer
  2b        e# Convert to binary array
    W%      e# Reverse array
      2b    e# Convert from binary array to number. Implicitly display
share|improve this answer

Batch, 62 bytes

@set/an=%1/2,r=%2+%1%%2
@if %n% gtr 0 %0 %n% %r%*2
@echo %r%

Explanation: On the first pass, %1 contains the input parameter while %2 is empty. We therefore evaluate n as half of %1 and r as +%1 modulo 2 (the % operator has to be doubled to quote it). If n is not zero, we then call ourselves tail recursively passing in n and an expression that gets evaluated on the next pass effectively doubling r each time.

share|improve this answer

C#, 98 bytes

using System.Linq;using b=System.Convert;a=>b.ToInt64(string.Concat(b.ToString(a,2).Reverse()),2);
share|improve this answer

PHP, 44 bytes

for(;$n=&$argv[1];$n>>=1)$r+=$r+$n%2;echo$r;

iterative: while input has set bits, pop a bit from input and push it to output. Run with -nr.

reursive, 52 bytes

function r($n,$r=0){return$n?r($n>>1,$r*2+$n%2):$r;}

PHP, 36 bytes

<?=bindec(strrev(decbin($argv[1])));

using builtins: convert to base2, reverse string, convert to decimal
(same as Robert Lerner´s answer, but using a parameter)

share|improve this answer

R, 55 bytes

sum(2^((length(y<-rev(miscFuncs::bin(scan()))):1)-1)*y)

Reads input from stdin and consequently uses the bin function from the miscFuncs package to convert from decimal to a binary vector.

share|improve this answer

k, 18 bytes

{2/:|X@&|\X:0b\:x}

Example:

k){2/:|X@&|\X:0b\:x}6
3
share|improve this answer

Perl 5 (5.12+), 34 bytes

say oct"0b".reverse sprintf"%b",<>

(Input on stdin, output on stdout, requires -E or -M5.012 at no cost).

Straightforward but not all that short. Too bad "reverse" and "sprintf" are such weighty keywords.

oct is an odd legacy name; oct "123" gives the decimal equivalent of octal 123 as you'd expect, but oct "0x123" interprets its input as hex and oct "0b101" interprets it as binary.

share|improve this answer

Java 7, 94 bytes

Golfed:

int x(int n){return Integer.parseInt(new StringBuffer(Integer.toString(n,2)).reverse()+"",2);}

Ungolfed:

int x(int n)
{
    return Integer.parseInt(new StringBuffer(Integer.toString(n, 2)).reverse() + "", 2);
}
share|improve this answer
    
You can use Long.parseLong and Long.toString to save a few bytes. – corvus_192 yesterday

Scala, 40 bytes

i=>BigInt(BigInt(i)toString 2 reverse,2)

Usage:

val f:(Int=>Any)=i=>BigInt(BigInt(i)toString 2 reverse,2)
f(10) //returns 5

Explanation:

i =>          // create an anonymous function with a parameter i
  BigInt(       //return a BigInt contructed from
    BigInt(i)     //i converted to a BigInt
    toString 2    //converted to a binary string
    reverse       //revered
    ,           
    2             //interpreted as a binary string
  )
share|improve this answer

c/c++ 136 bytes

uint8_t f(uint8_t n){int s=8*sizeof(n)-ceil(log2(n));n=(n&240)>>4|(n&15)<<4;n=(n&204)>>2|(n&51)<<2;n=(n&172)>>1|(n&85)<<1;return(n>>s);}

It's not going to win, but I wanted to take a different approach in c/c++ 120 bytes in the function

#include <math.h>
#include <stdio.h>
#include <stdint.h>

uint8_t f(uint8_t n){
    int s=8*sizeof(n)-ceil(log2(n));
    n=(n&240)>>4|(n&15)<<4;
    n=(n&204)>>2|(n&51)<<2;
    n=(n&172)>>1|(n&85)<<1;
    return (n>>s);
}

int main(){
    printf("%u\n",f(6));
    return 0;
}

To elaborate on what I am doing, I used the log function to determine the number of bits utilized by the input. Than a series of three bit shifts left/right, inside/outside, even/odd which flips the entire integer. Finally a bit shift to shift the number back to the right. Using decimals for bit shifts instead of hex is a pain but it saved a few bytes.

share|improve this answer
    
You do need to include the function declaration, so this is actually 163 bytes. Although, if you remove the extraneous whitespace, you could shorten it to 136. – DJMcMayhem 19 hours ago

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.