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).
Can I have the checkmark? – Adám – 2017-01-04T19:09:52.787
What is meant by "omissions" in "omissions are free game"? – Todd Lehman – 2014-08-15T18:01:04.603
1Anything not explicitly stated in the rules. – Isiah Meadows – 2014-08-15T18:05:56.957
Would a 16gb static table be counted as part of the program length? – Hot Licks – 2014-08-15T21:24:02.597
@HotLicks According to the typical interpretation of program, yes. – FUZxxl – 2014-08-15T22:08:15.810
language that only supports 8-bit inputs, can we take input as four 8-bit numbers? – Sparr – 2014-08-16T18:57:50.900
@Sparr Yes. <placeholder text> – Isiah Meadows – 2014-08-16T18:59:01.847
Windows Batch hater detected. :D – Kroltan – 2014-08-17T21:18:15.940
@Kroltan Actually, that's where I really learned when goto is or isn't a good thing. There are times when a structured goto is better than anything else, and I get annoyed on occasion on its lack of existence in JavaScript. If you could jump out of a for loop early and skip a section of code (like Python's for else), it could all but eliminate the need for exception handling (which can be a code smell of its own). – Isiah Meadows – 2014-08-17T21:37:30.727
@Kroltan On the contrary, it is possible to abuse it. My first programs featuring goto tended to be slightly spaghetti code, especially when I hadn't learned yet about multi-statement if, else, and for statements. – Isiah Meadows – 2014-08-17T21:39:48.957