Take the 2-minute tour ×
Programming Puzzles & Code Golf Stack Exchange is a question and answer site for programming puzzle enthusiasts and code golfers. It's 100% free, no registration required.

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 counts as a standard loophole and 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.

share|improve this question
    
What is meant by "omissions" in "omissions are free game"? –  Todd Lehman 2 days ago
1  
Anything not explicitly stated in the rules. –  impinball 2 days ago
    
Would a 16gb static table be counted as part of the program length? –  Hot Licks yesterday
    
@HotLicks According to the typical interpretation of program, yes. –  FUZxxl yesterday
    
language that only supports 8-bit inputs, can we take input as four 8-bit numbers? –  Sparr yesterday

21 Answers 21

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 abcdefghklmnopqr2 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).

share|improve this answer
    
+1 for using Knuth's CPU :-) –  slebetman yesterday
    
it's the first time I hear about matrix multiplication instruction on a CPU –  Lưu Vĩnh Phúc yesterday
    
@LưuVĩnhPhúc: Not a matrix multiplication, but VAX had an instruction to evaluate a polynomial. –  nneonneo yesterday
    
@nneonneo The POLY instruction of the VAX is basically a fused multiply-and-add with a builtin loop. Similar things also exist in modern architectures (like x86), but they usually don't have a builtin loop to evaluate an entire polynomial at once. –  FUZxxl yesterday

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.

share|improve this answer
1  
You could remove the int function type, and also change return r to something like i=r since most C compilers tend to leave the last operation's result in the return register. It worked on gcc and cl for me. –  Allbeert 2 days ago
1  
You could shave off another 4 bytes by using r(n){...} instead of r(int n){...} –  es1024 yesterday
2  
@FUZxxl you can't drop the int in int r=0,i=32; unless you move them out of the function body. –  es1024 yesterday
1  
@FUZxxl: Shouldn't comment when I'm tired... Arithmetic shift and division are not equivalent; the latter rounds towards zero, while the first rounds towards negative infinity. -1 >> 1 is -1 for AS and 2**31 - 1 for LS, while -1 / 2 is 0. –  Dennis yesterday
1  
@Todd: Any reason you didn't define r and i as arguments? Would save three more bytes... –  Dennis yesterday

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. ";
share|improve this answer

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.

share|improve this answer
3  
This is production code, not golfed code! xD I guess Julia's just great. –  cjfaure yesterday

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
share|improve this answer
    
b=k=0,R=v=>b++<32?R(v>>1,k+=k+(v&1)):k for single use and R=(v,b=0,k=0)=>b<32?R(v>>1,b+1,k+k+(v&1)):k is reusable –  bebe yesterday
    
@bebe :( I was revising my answer using recursion and lost all to read your comment... –  edc65 yesterday
2  
you're at 38 bytes if k<<1 becomes k*2 and v>>1 becomes v/2. it worked for 486. i dont know about other test cases –  bebe yesterday
1  
@bebe v/2 will not work for negative numbers. 486/512 == 0.9... and 486>>9 == 0, trunc it's the same. But -90/128 == -0.7... and -90>>7 ==-1 –  edc65 yesterday

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.

share|improve this answer
    
@MartinBüttner Thanks. I missed that possibility at first. The new code handles two's complement better. –  BeetDemGuise 2 days ago
2  
You can golf that a bit more: ['','-'][n%2] is '-'*(n%2). –  Quincunx yesterday

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
share|improve this answer
    
Does it work with result as a big 32 numbers having leftmost bit at 1? In this case it should output a negative integer. –  edc65 yesterday
    
@edc65 I'm outputting a 32 bit unsigned integer. –  isaacg yesterday

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.

share|improve this answer

80386 assembly (13 bytes)

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

    # inverse bit order of a 32 bit word
    .text
    .globl rbit
    .type rbit,@function
rbit:
    xor  %ecx,%ecx # prepare loop counter
    mov  $32,%cl
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:

31 c9 b1 20 d1 6c 24 04 11 c0 e2 f8 c3

Broken down into instructions:

31 c9       xor  %ecx,%ecx
b1 20       mov  $32,%cl
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.

share|improve this answer
    
+1 Thanks for your last sentence, It's obvious now but I missed that. –  edc65 19 hours ago

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;
 }
share|improve this answer
    
Small things, but you can initialize i when you declare it, and save a byte by removing i++ from the for loop, and instead of comparing the result of 1&... with 0 you can remove the if statement altogether and multiply i by the result giving r|=i*(1&(V>>(31-l++))); inside the loop –  VisualMelon 2 days ago
    
Clever! I had a feeling I was missing something. Thanks! –  WozzeC 2 days ago

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);
}
share|improve this answer

Python - 37

Similar to @isaacg's solution.

f=lambda n:int(bin(n%2**32)[:1:-1],2)
share|improve this answer

C, 162

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

Golfed:

unsigned Q(unsigned&x){unsigned 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; 
} 
share|improve this answer
    
This is a code golf question. Please try to reduce the number of characters in your solution, not the number of operations. –  FUZxxl 23 hours ago

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 http://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
$
share|improve this answer

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

Could also work in C.

share|improve this answer

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)
share|improve this answer
1  
The it may be a function rule means you don't need the alert or prompt –  slebetman yesterday

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",$_'
share|improve this answer

C++ 69

int r(int n){int e=0,i=0;for(;i<32;i++)e|=((n>>i)&1)<<31-i;return e;}
share|improve this answer
    
@bebe what are these e;i;? Declarations without type are not a valid C++. For variables it's not even valid C. –  Ruslan 14 hours ago
    
@Ruslan i didn't recognize '++' in the title, sorry. (i wouldn't agree with your second statement) –  bebe 11 hours ago

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.

share|improve this answer

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

share|improve this answer

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.

share|improve this answer

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.