What is the reverse (binary) bit number?

Question

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 code-golf challenge, so the solution that uses the least bytes wins.

This is A030101 in the OEIS.

Answer 1

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.

Answer 2

Python, 29 bytes

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

Try it online

Answer 3

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

Answer 4

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
};

Answer 5

J, 6 bytes

|.&.#:

|. reverse

&. under

#: base 2

Answer 6

Jelly, 3 bytes

BUḄ

Try it online!

B   # convert to binary
 U  # reverse
  Ḅ # convert to decimal

Answer 7

Mathematica, 19 bytes

#~IntegerReverse~2&

Answer 8

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);
}

Answer 9

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.

Answer 10

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

Answer 11

05AB1E, 3 bytes

bRC

Try it online!

Answer 12

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!

Answer 13

Japt, 5 3 bytes

-2 bytes thanks to Shaggy

¢ÔÍ

Try it online!

Answer 14

Perl 6, 19 bytes

{:2(.base(2).flip)}

Answer 15

Bash/Unix utilities, 24 23 bytes

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

Try it online!

Answer 16

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.

Answer 17

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;}

Answer 18

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

Answer 19

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

Answer 20

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
  )

Answer 21

Mathematica, 38 bytes

#+##&~Fold~Reverse[#~IntegerDigits~2]&

Answer 22

Groovy, 46 bytes

{0.parseInt(0.toBinaryString(it).reverse(),2)}

Answer 23

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

Answer 24

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.

Answer 25

C#, 98 bytes

using System.Linq;using b=System.Convert;a=>b.ToInt64(string.Concat(b.ToString(a,2).Reverse()),2);

Answer 26

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.

Answer 27

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.

Answer 28

k, 18 bytes

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

Example:

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

Answer 29

Perl 5 (5.12+), 32 bytes

say oct reverse sprintf"%bb0",<>

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

Answer 30

Java 7, 94 89 bytes

Golfed:

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

Ungolfed:

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

^{5 bytes saved thanks to @corvus_192}

Answer 31

C#, 167 bytes

 for(int i = 1; i <= 10; i++)
 {
 var bytes= Convert.ToString(i, 2);
 var value= Convert.ToInt32(byteValue.Reverse()); 
 console.WriteLine(value);
}

Explanation:

Here I will iterate n values and each time iterated integer value is convert to byte value then reverse that byte value and that byte value is converted to integer value.

Answer 32

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.

Answer 33

Pari/GP , 28 byte

The value to be "reversed" is expected in variable a; i.e. do a=37 first. Then execute the cmd. Because Pari/GP is interpreting you do not need to add an extra print(b) because referencing a variable or a result just prints it to the console:

  b=a%2;while(a\=2,b+=b+a%2);b

Example:

  a=37
  b=a%2;while(a\=2,b+=b+a%2);b
  \\ printed result is: 41                  

Try it online!

Answer 34

SmileBASIC, 41 bytes

INPUT N
WHILE N:T=T+T+N MOD 2N=N>>1WEND?T

Basically a port of the C/Java versions.

Answer 35

8th, 41 29 bytes

2 base drop >s rev >n decimal

Usage

ok> 37 2 base drop >s rev >n decimal .
41

Test case

: f 2 base drop >s s:rev >n decimal ; 
( dup . " => " . f . cr ) 1 10 loop

1 => 1
2 => 1
3 => 3
4 => 1
5 => 5
6 => 3
7 => 7
8 => 1
9 => 9
10 => 5

Answer 36

Scala 47 bytes

Handles BigInt

((i:BigInt)=>BigInt(i.toString(2).reverse,2))([Number to Reverse])

if only we could:

(i=>BigInt(i.toString(2).reverse,2))([Number to Reverse])

or

(BigInt(_.toString(2).reverse,2))([Number to Reverse])

Example (REPL):

scala> ((i:Int)=>BigInt(i.toString(2).reverse,2))(100)
res1: scala.math.BigInt = 19

Example (in Situ):

object main extends App {
    val arg = Option(args).getOrElse(Array[String]("100"))
    (BigInt(arg(0)) to BigInt(arg(1))).map((n)=>
    (println(n + "-->" + BigInt(n.toString(2).reverse, 2))))
}

run:

run 20 30

result:

[debug] Waiting for thread run-main-23 to terminate.
20-->5
21-->21
22-->13
23-->29
24-->3
25-->19
26-->11
27-->27
28-->7
29-->23
30-->15
[debug]         Thread run-main-23 exited.

Answer 37

C 41 bytes

g(i,r){for(r=0;r+=r+i%2,i/=2;);return r;}

Input in "i" output the result

Try it online!

Answer 38

Common Lisp, 52 bytes

(parse-integer(reverse(format()"~b"(read))):radix 2)

Try it online!

Answer 39

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.

Answer 40

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 

Answer 41

Julia, 32 bytes

f(n)=parseint(reverse(bin(n)),2)

gives a warning but still runs

Answer 42

Husk, 3 bytes

ḋ↔ḋ

Try it online!

Explanation

Here's an explanation, even if there's not much to it:

     -- implicit input N    | 10
  ḋ  -- convert to base2    | [1,0,1,0]
 ↔   -- reverse             | [0,1,0,1]
ḋ    -- convert from base2  | 5

Answer 43

JavaScript, 44 bytes

f=i=>(a=0,(x=i=>i?(a=a*2+i%2,x(i>>1)):a)(i))

for(i=1;i<10;i++){console.log(i,f(i))}

Answer 44

Add++, 14 bytes

D,f,@,BBBR2@Bb

Try it online!

How it works

D,f,@,   - Create a monadic function named f. Example argument: [10]
      BB - Convert to binary;     STACK = ['1010']
      BR - Reverse the top value; STACK = ['0101']
      2  - Push 2;                STACK = ['0101' 2]
      @  - Reverse the stack;     STACK = [2 '0101']
      Bb - Convert from base;     STACK = [5]
         - Implicit return

Answer 45

RProgN 2, 6 bytes

2Bi2iB

Try it online!

Answer 46

REXX, 46 bytes

say x2d(b2x(reverse(trunc(x2b(d2x(arg(1)))))))

Answer 47

Go, 49 bytes

A function literal based off my Java answer:

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

Try it online!