37
\$\begingroup\$

So you are given a POSITIVE 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.

This is A030101 in the OEIS.

\$\endgroup\$
6
  • 3
    \$\begingroup\$ Does "reverse the bits" mean reverse its binary digits? Sometimes it can also mean invert every bit. \$\endgroup\$ Jan 4, 2017 at 18:03
  • \$\begingroup\$ Yes. Sorry for being unclear. \$\endgroup\$
    – Joseph
    Jan 4, 2017 at 18:04
  • \$\begingroup\$ This and this are veeeeery similar. \$\endgroup\$
    – Geobits
    Jan 4, 2017 at 18:10
  • \$\begingroup\$ OEIS A030101. \$\endgroup\$
    – orlp
    Jan 4, 2017 at 18:12
  • 1
    \$\begingroup\$ "base 10" Any particular reason why? \$\endgroup\$ Jun 21, 2017 at 1:00

49 Answers 49

22
\$\begingroup\$

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.

\$\endgroup\$
9
  • 2
    \$\begingroup\$ Beat you by 9 seconds. \$\endgroup\$
    – mbomb007
    Jan 4, 2017 at 18:09
  • 4
    \$\begingroup\$ @mbomb007 meta.codegolf.stackexchange.com/a/10812/14215 \$\endgroup\$
    – Geobits
    Jan 4, 2017 at 18:12
  • 6
    \$\begingroup\$ @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. \$\endgroup\$
    – FlipTack
    Jan 4, 2017 at 18:15
  • 3
    \$\begingroup\$ 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. \$\endgroup\$
    – mbomb007
    Jan 4, 2017 at 18:17
  • 1
    \$\begingroup\$ @steenbergh Who cares? Same code, same score. \$\endgroup\$
    – mbomb007
    Feb 2, 2017 at 19:35
17
\$\begingroup\$

Python, 29 bytes

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

Try it online

\$\endgroup\$
1
  • 1
    \$\begingroup\$ This is what I would have done. ;) \$\endgroup\$
    – Joseph
    Jan 4, 2017 at 18:28
13
\$\begingroup\$

JavaScript (ES6), 30 28 bytes

Saved 2 bytes thanks to @Arnauld

f=(n,q)=>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 a 32 byte solution that does the same thing:

f=(n,q='0b')=>n?f(n>>1,q+n%2):+q
\$\endgroup\$
3
  • \$\begingroup\$ f=(n,q)=>n?f(n>>1,q*2|n%2):q almost works. But sadly not for n=0. \$\endgroup\$
    – Arnauld
    Jan 4, 2017 at 22:07
  • \$\begingroup\$ @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. \$\endgroup\$
    – FlipTack
    Jan 4, 2017 at 23:05
  • \$\begingroup\$ This is a late follow-up, but the input is now known to be always positive. \$\endgroup\$
    – Arnauld
    Jan 13, 2017 at 1:45
10
\$\begingroup\$

Java 8, 53 47 46 45 bytes

  • -4 bytes thanks to Titus
  • -1 byte thanks to Kevin Cruijssen

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+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
};
\$\endgroup\$
4
  • 1
    \$\begingroup\$ 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? \$\endgroup\$
    – Titus
    Jan 4, 2017 at 22:28
  • 2
    \$\begingroup\$ @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. \$\endgroup\$
    – FlipTack
    Jan 4, 2017 at 22:40
  • \$\begingroup\$ 45 bytes (Changed t=t*2+ to t+=t+.) \$\endgroup\$ Oct 25, 2017 at 12:45
  • \$\begingroup\$ @KevinCruijssen nice one! \$\endgroup\$
    – FlipTack
    Oct 25, 2017 at 12:49
9
\$\begingroup\$

J, 6 bytes

|.&.#:

|. reverse

&. under

#: base 2

\$\endgroup\$
8
\$\begingroup\$

Jelly, 3 bytes

BUḄ

Try it online!

B   # convert to binary
 U  # reverse
  Ḅ # convert to decimal
\$\endgroup\$
4
  • 7
    \$\begingroup\$ That's pretty short, BUB \$\endgroup\$
    – Cyoce
    Jan 4, 2017 at 22:42
  • \$\begingroup\$ Hmm... Is that really 3 bytes? \$\endgroup\$
    – aioobe
    Jan 6, 2017 at 19:41
  • 1
    \$\begingroup\$ @aioobe Yep. Jelly uses it's own code page where each of these characters is 1 byte. \$\endgroup\$
    – Riley
    Jan 6, 2017 at 19:43
  • \$\begingroup\$ Cool, thanks! <pad> \$\endgroup\$
    – aioobe
    Jan 6, 2017 at 21:32
8
\$\begingroup\$

Mathematica, 19 bytes

#~IntegerReverse~2&
\$\endgroup\$
7
\$\begingroup\$

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);
}
\$\endgroup\$
5
  • \$\begingroup\$ 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" \$\endgroup\$
    – simon
    Jan 5, 2017 at 8:19
  • 1
    \$\begingroup\$ @gurka The function should be reusable. \$\endgroup\$
    – Karl Napf
    Jan 5, 2017 at 8:26
  • 1
    \$\begingroup\$ I think that for loops are always at least as short as while loops, and often shorter. \$\endgroup\$
    – anatolyg
    Jan 5, 2017 at 20:00
  • \$\begingroup\$ @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). \$\endgroup\$
    – simon
    Jan 5, 2017 at 22:01
  • \$\begingroup\$ Yes; also, turn = into += to make it shorter and more obfuscated \$\endgroup\$
    – anatolyg
    Jan 5, 2017 at 22:49
7
\$\begingroup\$

Labyrinth, 23 bytes

?_";:_2
  :   %
 @/2_"!

Well, this is awkward... this returns the reverse BINARY number... Thanks @Martin Ender for pointing out both my bug and my ID 10T error. So this doesn't work, I'll have to find another solution.

\$\endgroup\$
3
  • 1
    \$\begingroup\$ 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 \$\endgroup\$ Jan 5, 2017 at 23:48
  • 1
    \$\begingroup\$ Did you accidentally omit a leading space from the second row? As it stands, the program would just bounce back and forth on the first line because the _ are on the junctions. \$\endgroup\$ Oct 25, 2017 at 13:09
  • \$\begingroup\$ Unfortunately, I just noticed that this isn't valid regardless, because the challenge asks for the base-10 representation of the reversed number, not its binary representation. \$\endgroup\$ Oct 25, 2017 at 13:12
5
\$\begingroup\$

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
\$\endgroup\$
3
  • \$\begingroup\$ @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 \$\endgroup\$
    – Cyoce
    Jan 4, 2017 at 22:46
  • \$\begingroup\$ Can you remove the parentheses in .to_i(2)? \$\endgroup\$
    – Cyoce
    Jan 5, 2017 at 15:48
  • \$\begingroup\$ @Cyoce sure enough, thanks. \$\endgroup\$ Jan 5, 2017 at 15:54
4
\$\begingroup\$

05AB1E, 3 bytes

bRC

Try it online!

\$\endgroup\$
4
\$\begingroup\$

Java (OpenJDK), 63 bytes

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

Try it online!

Thanks to poke for -12 bytes and to Cyoce for -8 bytes!

\$\endgroup\$
13
  • \$\begingroup\$ 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) \$\endgroup\$
    – FlipTack
    Jan 4, 2017 at 18:24
  • \$\begingroup\$ @FlipTack Oops. It was originally a function before I remembered the repl existed \$\endgroup\$
    – Pavel
    Jan 4, 2017 at 18:25
  • 1
    \$\begingroup\$ Also, in the future, use print instead of println for golfing :) \$\endgroup\$
    – FlipTack
    Jan 4, 2017 at 18:26
  • 1
    \$\begingroup\$ StringBuffer saves a byte over StringBuilder \$\endgroup\$
    – Poke
    Jan 4, 2017 at 19:33
  • 1
    \$\begingroup\$ Could you do +"" instead of .toString()? \$\endgroup\$
    – Cyoce
    Jan 8, 2017 at 2:35
3
\$\begingroup\$

Perl 6, 19 bytes

{:2(.base(2).flip)}
\$\endgroup\$
3
  • \$\begingroup\$ Where is the input? \$\endgroup\$
    – Titus
    Jan 4, 2017 at 21:54
  • \$\begingroup\$ This is a function that takes a single parameter $_. It isn't mentioned by name, but the base method is called on it. \$\endgroup\$
    – Sean
    Jan 4, 2017 at 22:40
  • 2
    \$\begingroup\$ @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. \$\endgroup\$
    – hobbs
    Jan 6, 2017 at 7:55
3
\$\begingroup\$

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.

\$\endgroup\$
3
\$\begingroup\$

Bash/Unix utilities, 24 23 bytes

dc -e2i`dc -e2o?p|rev`p

Try it online!

\$\endgroup\$
2
  • \$\begingroup\$ A courageous take on Bash! 😉 \$\endgroup\$
    – Joseph
    Jan 7, 2017 at 20:01
  • \$\begingroup\$ @juniorRubyist -- Thank you! \$\endgroup\$ Jan 7, 2017 at 21:55
3
\$\begingroup\$

PHP, 33 bytes

<?=bindec(strrev(decbin($argn)));

convert to base2, reverse string, convert to decimal. Save to file and run as pipe with -F.

no builtins:

iterative, 41 bytes

for(;$n=&$argn;$n>>=1)$r+=$r+$n%2;echo$r;

While input has set bits, pop a bit from input and push it to output. Run as pipe with -nR.

recursive, 52 bytes

function r($n,$r=0){return$n?r($n>>1,$r*2+$n%2):$r;}
\$\endgroup\$
1
  • \$\begingroup\$ @JörgHülsermann The 44 bytes have $r+=$r. But I actually don´t remember why I put that in front. \$\endgroup\$
    – Titus
    May 15, 2017 at 7:28
3
\$\begingroup\$

Japt, 5 3 bytes

-2 bytes thanks to Shaggy

¢ÔÍ

Try it online!

\$\endgroup\$
2
  • 1
    \$\begingroup\$ Nice, exactly what I had. The ) could be a space too :-) \$\endgroup\$ Jan 4, 2017 at 18:17
  • \$\begingroup\$ This can now be ¢ÔÍ or ¤ÔÍ. \$\endgroup\$
    – Shaggy
    Dec 19, 2019 at 12:34
2
\$\begingroup\$

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
\$\endgroup\$
2
\$\begingroup\$

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
\$\endgroup\$
2
\$\begingroup\$

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
  )
\$\endgroup\$
2
\$\begingroup\$

APL (Dyalog Unicode), 10 bytes

2⊥∘⊖2∘⊥⍣¯1

Try it!

Thanks to @Adám for 2 bytes.

How it works:

This is a tacit function. To use it, it has to be assigned a name (like f←) and then called over an input; for the test cases: f 1, f 2, etc.

2⊥∘⊖2∘⊥⍣¯1  # Main function; tacit.
       ⍣¯1  # invert
    2∘⊥     # convert from base 2 (which is inverted to 'convert to base 2')
  ∘⊖        # flip, then
2⊥          # convert from base 2 
\$\endgroup\$
1
\$\begingroup\$

Mathematica, 38 bytes

#+##&~Fold~Reverse[#~IntegerDigits~2]&
\$\endgroup\$
1
\$\begingroup\$

Groovy, 46 bytes

{0.parseInt(0.toBinaryString(it).reverse(),2)}
\$\endgroup\$
4
  • \$\begingroup\$ Does this take any input? \$\endgroup\$
    – Titus
    Jan 4, 2017 at 21:55
  • 1
    \$\begingroup\$ @Titus it refers to the argument given to a block IIRC \$\endgroup\$
    – Cyoce
    Jan 4, 2017 at 22:47
  • \$\begingroup\$ I love how this is the same length as my Java answer - Java and groovy, unite! \$\endgroup\$
    – FlipTack
    Jan 4, 2017 at 23:06
  • 1
    \$\begingroup\$ @FlipTack I'm gonna go cry now. \$\endgroup\$ Jan 5, 2017 at 14:23
1
\$\begingroup\$

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
\$\endgroup\$
1
\$\begingroup\$

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.

\$\endgroup\$
1
\$\begingroup\$

C#, 98 bytes

using System.Linq;using b=System.Convert;a=>b.ToInt64(string.Concat(b.ToString(a,2).Reverse()),2);
\$\endgroup\$
1
\$\begingroup\$

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.

\$\endgroup\$
1
\$\begingroup\$

Pushy, 19 bytes

No builtin base conversion!

$&2%v2/;FL:vK2*;OS#

Try it online!

Pushy has two stacks, and this answer makes use of this extensively.

There are two parts two this program. First, $&2%v2/;F, converts the number to its reverse binary representation:

            \ Implicit: Input is an integer on main stack.
$      ;    \ While i != 0:
 &2%v       \   Put i % 2 on auxiliary stack
     2/     \   i = i // 2 (integer division)
        F   \ Swap stacks (so result is on main stack)

Given the example 10, the stacks would appear as following on each iteration:

1: [10]
2: []

1: [5]
2: [0]

1: [2]
2: [0, 1]

1: [1]
2: [0, 1, 0]

1: [0]
2: [0, 1, 0, 1]

We can see that after the final iteration, 0, 1, 0, 1 has been created on the second stack - the reverse binary digits of 10, 0b1010.

The second part of the code, L:vK2*;OS#, is taken from my previous answer which converts binary to decimal. Using the method decsribed and explained in that answer, it converts the binary digits on the stack into a base 10 integer, and prints the result.

\$\endgroup\$
1
\$\begingroup\$

Labyrinth, 22 bytes

_2/?+:{!
}    "
++:{%#

Try it online!

Explanation

The idea is to disassemble the input bit-by-bit while assembling the output from the other end. Luckily, it's easiest to deconstruct a number from the right, and build one up from the left, so this automatically reverses the bits. We'll generally be keeping what's left of the input on top the main stack, and what we've already computed of the result on top of the auxiliary stack.

_2/  When the program starts out, this doesn't really do anything, because it
     just divides an implicit zero by 2.
?+   Read an integer N from STDIN and add it to the implicit zero on top of 
     the stack.

     The main loop starts here:

:    Duplicate what's left of N. This is also used as the conditional to end
     the loop. Once this reaches zero, the IP moves straight ahead, exiting
     the loop. Otherwise, the IP turns south which continues the loop.
#    Push the stack depth, 2.
%    Take N modulo 2, i.e. get its least significant bit.
{    Fetch the intermediate result R from the auxiliary stack.
:+   Double it (shifting its existing bits left by one position).
+    Add the bit we just extracted from N to R.
}    Put R back on the auxiliary stack.
_2/  Divide N by 2, dropping its least significant bit.
?+   We're at EOF, so ? just pushes zero and the + gets rid of that zero.

     Then the main loop starts over.
     When we exit the loop (once N is zero), this bit is run:

{    Retrieve R from the auxiliary stack.
!    Print it.
     The IP hits a dead end and turns around.
{:+? Various shenanigans which simply leave a zero on top of the stack.
/    Terminates the program due to the attempted division by zero.
\$\endgroup\$
1
\$\begingroup\$

Vyxal, 3 bytes

bṘB

Try it Online!

Converts to a binary string, reverses it, then puts it back in base 10.

\$\endgroup\$
2
  • 1
    \$\begingroup\$ So then when will you be back? \$\endgroup\$
    – lyxal
    Oct 8, 2022 at 22:39
  • \$\begingroup\$ Btw the link doesn't have any input in it. \$\endgroup\$
    – naffetS
    Oct 9, 2022 at 3:29

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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