Reverse Bit Order of 32-bit Integers

Question

Write the shortest code to reverse the bit order of a 32-bit integer.

Rules:

1. Input is assumed to be a valid integer or string equivalent if your language doesn't support numerical values (e.g. Windows Batch).
2. Output must be a valid integer or string equivalent if your language doesn't support numerical values (e.g. Windows Batch).
3. Standard library only.
4. It may be a function or a complete program.
5. Input may be either from stdin or as a function argument.
6. Output must be either stdout or as a returned value.
7. If your language has a built-in or standard library function that does this in one step (e.g. rbit in ARM assembly), that cannot be used.

Examples:

Key:

1. decimal
   • binary
   • (reverse)
   • reversed binary
   • decimal output

Examples:

1. -90 (8-bit example for demonstration)

   • 10100110b
   • (reverse)
   • 01100101b
   • 101

2. 486

   • 00000000000000000000000111100110b
   • (reverse)
   • 01100111100000000000000000000000b
   • 1736441856

3. -984802906

   • 11000101010011010001100110100110b
   • (reverse)
   • 01100101100110001011001010100011b
   • 1704506019

Note: Omissions are free game. If I didn't say it, and it's not one of the standard loopholes, then it's completely allowed.

Answer 1

MMIX assembly (28 Bytes)

64 bit numbers

rbit:
    SETH $1,#0102 # load matrix in 16-byte steps
    ORMH $1,#0408
    ORML $1,#1020
    ORL  $1,#4080
    MOR  $0,$1,$0 # multiplication 1
    MOR  $0,$0,$1 # multiplication 2
    POP  1,0      # return

This assembles to:

rbit:
    E0010102 # SETH $1,#0102
    E9010408 # ORMH $1,#0408
    EA011020 # ORML $1,#1020
    EB014080 # ORL  $1,#4080
    DC000100 # MOR  $0,$1,$0
    DC000001 # MOR  $0,$0,$1
    F8010000 # POP  1,0

How does it work?

The MOR instruction performs a matrix multiplication on two 64-bit quantities used as two 8x8 matrices of booleans. A boolean number with digits abcdefghklmnopqr₂ is used as a matrix like this:

/ abcd \
| efgh |
| klmn |
\ opqr /

The MOR instruction multiplies the matrices represented by their arguments where multiplication is and and addition is or. It is:

/ 0001 \      / abcd \      / opqr \
| 0010 |  \/  | efgh |  --  | klmn |
| 0100 |  /\  | klmn |  --  | efgh |
\ 1000 /      \ opqr /      \ abcd /

and furthermore:

/ opqr \      / 0001 \      / rqpo \
| klmn |  \/  | 0010 |  --  | nmlk |
| efgh |  /\  | 0100 |  --  | hgfe |
\ abcd /      \ 1000 /      \ dcba /

which is the reverse order of bits of the original number.

32 bit numbers

If you just want the reverse of a 32 bit number instead of a 64 bit number, you can use this modified method:

rbit:
    SETL   $1,#0408 # load first matrix in two steps
    ORML   $1,#0102
    MOR    $1,$1,$0 # apply first matrix
    SLU    $2,$1,32 # compile second matrix
    16ADDU $1,$2,$1
    MOR    $1,$0,$1 # apply second matrix
    POP    1,0      # return

assembled:

rbit:
    E3010408 # SETL   $1,#0408
    EA010102 # ORML   $1,#0102
    DC010001 # MOR    $1,$1,$0
    3B020120 # SLU    $2,$1,32
    2E010201 # 16ADDU $1,$2,$1
    DC010001 # MOR    $1,$0,$1
    F8010000 # POP    1,0

The first matrix multiplication basically works like this:

/ 0000 \      / 0000 \      / 0000 \
| 0000 |  \/  | 0000 |  --  | 0000 |
| 0001 |  /\  | abcd |  --  | efgh |
\ 0010 /      \ efgh /      \ abcd /

the corresponding octabyte is #0000000001020408 which we load in the first two instructions. The second multiplication looks like this:

/ 0000 \      / 0001 \      / 0000 \
| 0000 |  \/  | 0010 |  --  | 0000 |
| efgh |  /\  | 0100 |  --  | hgfe |
\ abcd /      \ 1000 /      \ dcba /

The corresponding octabyte is #0102040810204080 which we create from the first matrix like this:

SLU $2,$1,#32   # $2 = #0102040800000000
16ADDU $1,$2,$1 # $2 = $2 + $1 << 4
                     = $2 + #0000000010204080
                #    = #0102040810204080

The second multiplication is business as usual, the resulting code has the same length (28 bytes).

Answer 2

80386 assembly (13 12 bytes)

As a function in AT&T syntax using the cdecl calling convention.

    # reverse bits of a 32 bit word
    .text
    .globl rbit
    .type rbit,@function
rbit:
    push $32       # prepare loop counter
    pop %ecx
0:  shrl 4(%esp)   # shift lsb of argument into carry flag
    adc  %eax,%eax # shift carry flag into lsb
    loop 0b        # decrement %ecx and jump until ecx = 0
    ret            # return

This function assembles to the following byte sequence:

6a 20 59 d1 6c 24 04 11 c0 e2 f8 c3

Broken down into instructions:

6a 20       push $32
59          pop %ecx
d1 6c 24 04 shrl 0x4(%esp)
11 c0       adc  %eax,%eax
e2 f8       loop .-6
c3          ret    

It works like this: In each of the 32 iterations of the loop, the argument, which is located at 4(%esp), is right shifted by one position. The last bit is implicitly shifted into the carry flag. The adc instruction adds two values and adds the value of the carry flag to the result. If you add a value to itself, i.e. %eax, you effectively left-shift it by one position. This makes adc %eax,%eax a convenient way to left shift %eax by one position while shifting the content of the carry flag into the low-order bit.

I repeat this process 32 times so that the entire content of 4(%esp) is dumped into %eax. I never explicitly initialize %eax as its previous contents are shifted out during the loop.

Answer 3

C,   63    52   48

Original version:

int r(int n){int r=0,i=32;for(;i--;r=r<<1|n&1,n>>=1);return r;}

---

Updated version (with changes suggeted by Allbeert, es1024, and Dennis):

r(n){int r,i=32;for(;i--;r=r*2|n&1,n>>=1);return r;}

Note: Since the second version omits setting r=0, the code is assuming that an int is 32 bits. If this assumption is false, the function will most likely produce an incorrect result, depending on the initial state of r on entry to the function.

---

Final version (with further changes suggested by Dennis and Alchymist):

r(n,r,i){for(;32-i++;r=r*2|n&1,n>>=1);return r;}

Note: This puts the declaration of the work variables r and i into the parameter list. Parameters are as follows: n is the number to be bit-reversed. r and i are work variables that must be passed as 0.

Answer 4

x86 assemply, 10 Bytes

   f9                      stc    
   d1 d8            1:     rcr    %eax
   74 05                   je     2f
   d1 d2                   rcl    %edx
   f8                      clc    
   eb f7                   jmp    1b
                    2:

This assume input in eax, output in edx. (Also, on output eax is zero and CF and ZF are set, if anyone cares).

Instead of a counter, an additional 1 is pushed in in the beginning as end-of data marker

Answer 5

Julia 0.2, 33 bytes

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

Does what it looks like.

bits gives you the bit representation (respecting two's complement). parseint doesn't care about two's complement, but returns a 32 bit integer, so the two's complement is simply handled by overflow.

According to the changelogs, overflow detection was added to parseint in Julia 0.3, so this might not work any more.

Answer 6

Python 2, 50

print int("{:032b}".format(input()%2**32)[::-1],2)

Broadly the same as my Pyth solution. Take the input mod 2**32, convert to 32-bit padded binary, reverse, convert binary sting back to decimal and print.

Answer 7

CJam, 15 bytes

li4H#+2bW%32<2b

Try it online.

"Free game" joker used: The output will always be an unsigned integer.

Test cases

$ cjam reverse32.cjam <<< 486; echo
1736441856
$ cjam reverse32.cjam <<< -984802906; echo
1704506019

How it works

li   " Read from STDIN and cast to integer. ";
4H#+ " Add 4 ** 17 to avoid special cases. ";
2b   " Convert into array of digits in base 2. ";
W%   " Reverse the order. ";
32<  " Discard the 33th and all following digits. ";
2b   " Convert the array of digits into an integer. ";

Answer 8

JavaScript (E6) 37 39 40 50

Function, number input and returning reversed number. Most basic algorithm, probably can be golfed more with some smart trick.

Edit Recursion instead of loop

Edit 2 Following @bebe suggestion k*2 instead of k<<1

Edit 3 Something I had missed at all: it's a full 32 bit loop, no need to initialize k. Thanks @FUZxxl

R=(v,b=32,k)=>b?R(v>>1,b-1,k*2|v&1):k

It was

R=v=>{for(k=b=0;b++<32;)k+=k+(v&1),v>>=1;return k}

Test In FireFox console, test using numbers in OP and some more random 16 and 32 bit numbers

Bin=x=>('0'.repeat(32)+(x<0?-x-1:x).toString(2)).slice(-32).replace(/./g,d=>x>0?d:1-d),
Dec=x=>(' '.repeat(11)+x).slice(-11),
R16=_=>Math.random()*65536|0,  
R32=_=>(Math.random()*65536<<16)|R16(),  
[-90,486,-984802906,R16(),R16(),R16(),R32(),R32(),R32(),R32()]
 .forEach(n=> console.log(Dec(n)+' '+Bin(n)+' '+Dec(R(n))+' '+Bin(R(n))))

Example of test output

        -90 11111111111111111111111110100110  1711276031 01100101111111111111111111111111
        486 00000000000000000000000111100110  1736441856 01100111100000000000000000000000
 -984802906 11000101010011010001100110100110  1704506019 01100101100110001011001010100011
      45877 00000000000000001011001100110101 -1395851264 10101100110011010000000000000000
      39710 00000000000000001001101100011110  2027487232 01111000110110010000000000000000
      56875 00000000000000001101111000101011  -730136576 11010100011110110000000000000000
-1617287331 10011111100110100010011101011101 -1159439879 10111010111001000101100111111001
-1046352169 11000001101000011110111011010111  -344488573 11101011011101111000010110000011
 1405005770 01010011101111101010111111001010  1408597450 01010011111101010111110111001010
  -35860252 11111101110111001101000011100100   655047615 00100111000010110011101110111111

Answer 9

Dyalog APL, 10 bytes

2⊥⌽⎕⊤⍨32/2

2⊥ from-base-2 of

⌽ the reversed

⎕ numeric input

⊤⍨ in the number system consisting of

32/2 32 bits

TryAPL online!

Answer 10

J (17 15 13 bytes)

_32#.@|.@{.#:

Here is an explicit definition to explain what it does:

3 : '#. |. _32 {. #: y'

1. #: y represents y as a base 2 number using as many places as necessary.
2. x {. y takes |x (magnitude of x) items from y, from the front if x is positive, from the back if x is negative. If we take more items than present, the result is padded with zeroes. _32 {. #: y effectively pads #: y to 32 bits.
3. |. y flips y, i.  reverses the order of items in y.
4. #. y interprets y as a base-2 number.

Answer 11

Python - 89

def r(n):
 if n<0:n=~n^0xFFFFFFFF
 print int(['','-'][n%2]+'{:032b}'.format(n)[::-1],2)

Python represents negative binary numbers as simply -0b{positive_number}. So to deal with this, complement negative numbers and then XOR with all 1's.

After that, create the string representation of the integer based on the format {:032b} which provides the 32bit representation of the number. Finally, reverse the string and turn it back into an integer.

EDIT

Thanks to @Martin Büttner for pointing out a two's complement issue. If n ends in a 1 then by two's complement the reversed version would be negative.

Luckily, as explained above, Python likes negative binary numbers in a pretty simple way. Also luckily, Python's int function allows optional sign characters in its first argument.

So now, add a minus sign if n is odd to satisfy two's complement.

Answer 12

Pyth, 33 32 22

v_%"%032db0"vsc%Q^2 32

Explanation:

                 Q             Evaluated input.
                %Q^2 32        Q mod 2^32. Same 32 bit binary representation as Q.
             vsc%Q^2 32        Convert to binary string, then that to decimal int.
   %"%032db0"vsc%Q^2 32        Pad above number to 32 bits, and append b0.
  _%"%032db0"vsc%Q^2 32        Reverse it.
 v_%"%032db0"vsc%Q^2 32        Eval and print. Due to leading "0b", eval as binary.

Golfs:

33 -> 32: Moved add to before reversing to save an end-quote.

32 -> 22: Used Q mod 2^32 instead of complicated machinery. Combined both strings into one.

Test cases:

$ cat rev_bits 
v_%"%032db0"vsc%Q^2 32

$ ./pyth.py rev_bits <<< -984802906
1704506019

$ ./pyth.py rev_bits <<< 486
1736441856

$ ./pyth.py rev_bits <<< 0
0

Answer 13

GNU dc, 27 bytes

0?[2~rssr2*+dlsz34>m]dsmx+p

Output:

$ dc revbits.dc <<< 15
4026531840
$ dc revbits.dc <<< 255
4278190080
$ dc revbits.dc <<< 65535
4294901760
$ dc revbits.dc <<< 4294901760
65535
$ dc revbits.dc <<< 4278190080
255
$ dc revbits.dc <<< 4026531840
15
$ 

---

Bash+coreutils, 45 bytes

n=`dc -e2do32^n$1p`
dc -e2i`rev<<<${n: -32}`p

Output:

$ ./revbits.sh 15
4026531840
$ ./revbits.sh 255
4278190080
$ ./revbits.sh 65535
4294901760
$ ./revbits.sh 4294901760
65535
$ ./revbits.sh 4278190080
255
$ ./revbits.sh 4026531840
15
$ 

---

C function, 89 bytes

Same idea as https://codegolf.stackexchange.com/a/36289/11259 - using the Stanford bit twiddling hacks. Not going to win the golfing, but interesting nonetheless:

// 89 byte function:
i;r(v){for(i=1;i<32;i*=2)v=v>>i&(1L<<32)/((1<<i)+1)|(v&(1L<<32)/((1<<i)+1))<<i;return v;}

// Test program:
#include <stdio.h>

int main (int argc, char **argv)
{
    printf("r(0x0000000f) = 0x%08x\n", r(0x0000000f));
    printf("r(0x000000ff) = 0x%08x\n", r(0x000000ff));
    printf("r(0x0000ffff) = 0x%08x\n", r(0x0000ffff));
    printf("r(0xffffffff) = 0x%08x\n", r(0xffffffff));
    printf("r(0x0f0f0f0f) = 0x%08x\n", r(0x0f0f0f0f));
    printf("r(0xf0f0f0f0) = 0x%08x\n", r(0xf0f0f0f0));
}

Output:

$ ./revbits 
r(0x0000000f) = 0xf0000000
r(0x000000ff) = 0xff000000
r(0x0000ffff) = 0xffff0000
r(0xffffffff) = 0xffffffff
r(0x0f0f0f0f) = 0xf0f0f0f0
r(0xf0f0f0f0) = 0x0f0f0f0f
$

Answer 14

Java function, 64 chars.

 int r(int n){int r=0,i=32;for(;i-->0;n>>=1)r=r<<1|n&1;return r;}

Should also work in C.

Answer 15

PHP, 46 Bytes

Online Versions

for(;$i<32;)$t.=$argn>>$i++&1;echo bindec($t);

or

<?=bindec(strrev(sprintf("%064b",$argn<<32)));

Answer 16

x86 assembly, 9 bytes

    xor eax, eax
    inc eax
myloop:
    shr ecx, 1
    adc eax, eax
    jnc short myloop

In byte form: 33 C0 40 D1 E9 13 C0 73 FA, 9 bytes.

Answer 17

JS 115

Well that doesn't look good at all :D

n=+prompt();alert(eval('0b'+(Array(33).join(0)+(n<0?n>>>0:n).toString(2)).slice(-32).split('').reverse().join('')))

@Florian F's method in JS is 53 bytes long:

for(n=+prompt(r=0),i=32;i--;n>>=1)r=r<<1|n&1;alert(r)

Answer 18

C# 81 74

int R(int V){int l,r=l=0,i=1;for(;i>0;i*=2)r|=i*(1&V>>(31-l++));return r;}

Bit operations which most likely can be done shorter in all programming languages.

Basically, loop through all powers of 2 up to integer maximum+1(Which turns into a power of two) and since (2,147,483,647+1)=0 I can loop to 0. Bit shift Left to right to move the bit into the first position. Last bit at place 32 goes 31 steps to the right, second last goes 30 etc. So by using AND operator with 1 i will know if it is 1 or 0. If it is 1 I will add the current i value to the result and return it.

int R(int V)
{
    int l,r=l=0,i=1;
    for(;i>0;i*=2)
        r|=i*(1&(V>>(31-l++)));
    return r;
 }

Answer 19

C# 142

using System;using System.Linq;int f(int n){return Convert.ToInt32(new string(Convert.ToString(n,2).PadLeft(32,'0').Reverse().ToArray()),2);}

Expanded

int f(int n)
{
    return Convert.ToInt32(
        new string(
            Convert.ToString(n, 2)
            .PadLeft(32, '0')
            .Reverse()
            .ToArray()), 2);
}

Answer 20

Python - 37

Similar to @isaacg's solution.

f=lambda n:int(bin(n%2**32)[:1:-1],2)

Answer 21

C++, 160

This isn't the shortest one, however it uses only 24 operations.
Taken from Hacker's Delight book.

Golfed:

typedef unsigned U;U R(U&x){U a=-1u/3,b=-1u/5,c=-1u/17,d=65280;x=(x&a)*2|(x/2)&a;x=(x&b)*4|(x/4)&b;x=(x&c)<<4|(x>>4)&c;x=(x<<24)|((x&d)<<8)|((x>>8)&d)|(x>>24);}

Ungolfed:

unsigned R(unsigned x) {
    x = (x & 0x55555555) <<  1 | (x >>  1) & 0x55555555; 
    x = (x & 0x33333333) <<  2 | (x >>  2) & 0x33333333; 
    x = (x & 0x0F0F0F0F) <<  4 | (x >>  4) & 0x0F0F0F0F; 
    x = (x << 24) | ((x & 0xFF00) << 8) | ((x >> 8) & 0xFF00) | (x >> 24); 
    return x; 
} 

Answer 22

Haskell, 145 - no bitwise operations

Bit-twiddling strikes me as the antithesis of Haskell, so I've avoided any use of bitwise operators. The resulting program is certainly not the shortest contestant, but I thought the use of math instead of bit-twiddling was interesting at least.

import Data.Tuple
import Data.List
f m=foldl1((+).(*2))$take 32$(unfoldr(\n->if n==0 then Nothing else Just$swap$divMod n 2)$mod m$2^32)++[0,0..]

Explanation

f m=foldl1((+).(*2))$take 32$(unfoldr(\n->if n==0 then Nothing else Just$swap$divMod n 2)$mod m$2^32)++[0,0..]
    |------5-------|---4----|--------------------------2---------------------------------|----1-----|---3----|

1. uses modulo to bring the result into 32-bit range
2. constructs a list of 0s and 1s, least significant bit first by repeatedly dividing by 2 and taking the remainder
3. concatenates an infinite list of 0s to the end of this list
4. grabs the first 32 elements of the list (These last two were needed to ensure the list is actually 32 bits long.)
5. converts a list of 0 and 1 into an integer assuming the most significant bit is first (repeated double and add).

I'm not quite sure what constitutes "the standard library" in Haskell so I assumed Data.Tuple and Data.List were OK (they are pretty standard).

Also, the output is an unsigned 32-bit integer since changing that would cost me bytes: I'm arguing this under "omissions are free game".

Answer 23

PHP, 46 41 bytes

try them online

while($i<32)$r=$r*2|$argn>>$i++&1;echo$r;

bitwise ... more or less. Run as pipe with php -nR '<code>'.

PHP, 46 bytes

while($i<32)$r|=($argn>>$i&1)<<31-$i++;echo$r;

a pure bitwise solution; run as pipe with -nR.

PHP, 47 59 bytes

<?=bindec(str_pad(strrev(substr(decbin($argn),-32)),32,0));

another built-in approach; save to file and run as pipe with -F.

Answer 24

ARM Thumb machine code, 10 bytes

00000000: 01 20 49 08 40 41 fc d3 70 47            . [email protected]

As per request, this does not use the rbit instruction.

    .syntax unified
    .arch armv7-a
    .thumb
    .globl rbit
    .thumb_func
    // input: r1
    // output: r0
rbit:
    // sentinel bit
    movs    r0, #1
.Lloop:
    // shift the lowest bit into the carry flag
    lsrs    r1, #1
    // shift in with adc, put highest bit in carry flag
    adcs    r0, r0
    // when the carry is set we flipped all 32 bits
    bcc     .Lloop
    // return
    bx      lr

---

ARM Thumb machine code (with builtins), 6 bytes

00000000: 90 fa a0 f0 70 47                   ....pG

This is literally the rbit instruction that was explicitly disallowed but I am providing for reference

    .syntax unified
    .arch armv7-a
    .thumb
    .globl rbit_cheater
    .thumb_func
    // input: r0
    // output: r0
rbit_cheater:
    // Trivialize the challenge.
    rbit   r0, r0
    // Return
    bx     lr

Answer 25

Perl - 60

$_=unpack"N",pack"B*",scalar reverse unpack"B32",pack"N",$_

+1 for the p flag (let me know if I'm counting this wrong).

Run with:

echo 486 | perl -pe'$_=unpack"N",pack"B32",scalar reverse unpack"B32",pack"N",$_'

Answer 26

C++ 69

int r(int n){int e=0,i=0;for(;i<32;i++)e|=((n>>i)&1)<<31-i;return e;}

Answer 27

R, 45

f=function(x)packBits(intToBits(x)[32:1],"i")

Examples:

f(486)
# [1] 1736441856
f(-984802906)
# [1] 1704506019

Always just shy of the Python answers. That damn function keyword.

Answer 28

Ruby, 43 41 bytes

def r(n)(0..31).inject(0){|a,b|a*2+n[b]}end

In Ruby, using the bracket index notation (foo[i]) returns the bit at the nth place.

--Edit--

Refactoring the inject functionality shaves a couple bytes

def r(n)z=0;32.times{|i|z=z*2+n[i]};z;end

Answer 29

Perl5: 46

sub r{for(0..31){$a=$a*2|$_[0]&1;$_[0]>>=1}$a}

Nothing fancy. It shifts output left, copy lsb before shifting source right.

Answer 30

Clojure, 202 156 142

#(read-string (let [s (clojure.pprint/cl-format nil "~2r" %)](apply str (reverse (apply str (concat (repeat (- 32 (count s)) "0") s "r2"))))))