Challenge: Mirror bits

[Geir Isene]

Given a four-bit number (0001 - 1111) in Hex (1 - F), what are the steps you would take to mirror the number?

Example: 8 (1000) would become 1 (0001) and 11 (1011) would become 13 (1101)

Edited: 21 Dec 2008, 3:13 p.m.

[Paul Dale]

I'd approach this one of three ways:

1. The naive approach of shifting and testing the low order bit
   
2. Use a 16 element lookup table
   
3. Do the first two steps of this algorithmn.
   

For a 4-bit number, I'd probably go with the naive:

    y = (x & 1 <> 0) * 8 + (x & 2 <> 0) * 4 + (x & 4 <> 0) * 2 + (x & 8 <> 0) * 1

For the firmware I'm working on for the 20b, I used the naive algorithm to do the arbitrary word size bit mirror.

- Pauli

edit: first two steps not three.

Edited: 21 Dec 2008, 5:26 p.m. after one or more responses were posted

[Geir Isene]

How would you do it without going via binary; i.e. how would you manipulate the hex digit directly?

[Egan Ford]

Quote:

---

How would you do it without going via binary; i.e. how would you manipulate the hex digit directly?

---

Something like this:

$obits=0;                          # output bits

$numbits=4;                        # number of bits to reverse

while($bits) {                     # while $bits > 0

    $numbits--;                    # $numbits = $numbits - 1

    if($bits % 2) {                # is $bits MOD 2 a 1?

        $obits += 2**($numbits)    # if so add 2^$numbits

    }

    $bits /= 2;                    # $bits = floor($bits / 2);

}

You should be able to do this on the 15C.

[Paul Dale]

This is the naive algorithm I mentioned written as a loop not inline code.

- Pauli

[Egan Ford]

Yes, but it is the only way to met Geir's second condition:

Quote:

---

How would you do it without going via binary...

---

I am assuming that without going via binary indicates not using bit manipulation.

Here is a crude 15C version of the above Perl snippet:

001  LBL A       015  1           029  LBL .8      

002  STO 0       016  -           030  x<>y        

003  0           017  y^x         031  ENTER       

004  STO 1       018  STO+ 1      032  Rv          

005  4           019  LBL 1       033  x<>y        

006  STO 2       020  RCL 0       034  /           

007  LBL 0       021  2           035  LSTx        

008  RCL 0       022  /           036  x<>y        

009  2           023  INT         037  INT         

010  GSB .8      024  STO 0       038  x           

011  x=0         025  DSE 2       039  R^          

012  GTO 1       026  GTO 0       040  -           

013  2           027  RCL 1       041  CHS         

014  RCL 2       028  RTN         042  RTN         

[Paul Dale]

Based on two just about the reference I posted:

     y = ((x * 0x0802 & 0x22110) | (x * 0x8020 & 0x88440)) * 0x10101 >> 20

or  y = ((x * 0x0202020202 & 0x010884422010) % 1023) >> 4;

I'm sure there is a better algorithm based on these ideas but involving shorter magic numbers.

- Pauli

Edited: 21 Dec 2008, 8:33 p.m. after one or more responses were posted

[Egan Ford]

Quote:

---

y = ((x * 0x0202020202 & 0x010884422010) % 1023) >> 4;

I'm sure there is a better algorithm based on these ideas but involving shorter magic numbers.

---

How about:

y = ((x * 0x00082082 & 0x01122408) % 255) >> 2;

[Paul Dale]

That works nicely!

- Pauli

[C.Ret]

Quote:

---

y = ((x * 0x00082082 & 0x01122408) % 255) >> 2;

---

I have same trouble interpretating this line of code !

As I understand this code :

* stand for arimethic multiplication operator (which seems to apply to numeric, binary and a mix of theses.

& stand for binary AND operator

Ox is the prefix of hexadecimal integer ( Ox00082082 seems to be equivalent to #00082082h )

= is not the equal sign of an equality but surrely correspond to assignment operation to 'y' register.



But what are % and >> operators standing for ?

Edited: 23 Dec 2008, 11:54 a.m.

[Egan Ford]

% is MOD

>> 2 is right shift 2 bits, I could have used /2/2 or /4 instead.

The above notation is common in some structured programming languages, e.g. C and Perl.

Edited: 23 Dec 2008, 12:05 p.m.

[C.Ret]

Thank you for the information and your time.

It is always time to learn something :-)
I prefer to ask for some light than staying in the darkness!
The binary operator of C was out of my tiny notions of C (and fullpart of my ignorance in Perl).

I am now able to interpret your line of code, but still not sure to understand the amazing arimetic and magic of this algorithm.

Translate into RPL the mirror operation may be translate to :

<< #00082082h *           @ multiplication by a binary convert result to

                          @ binary whatever is first argument is real or binary

   #01122408h AND         

   B->R 255 MOD R->R      @ MOD only apply on real on my HP

   SR SR

>>

'Y' STO

It's work perfectly ! But I still analysing why !

The trick is certainly based on the magic numbers :

#00082082h = # 00000000000010000010000010000010_b

#01122408h = # 00000001000100100010010000001000_b

[Egan Ford]

Quote:

---

The trick is certainly based on the magic numbers :

#00082082h = # 00000000000010000010000010000010_b

#01122408h = # 00000001000100100010010000001000_b

---

The source of the magic numbers are from: http://home.pipeline.com/~hbaker1/hakmem/hacks.html#item167. Perhaps you can find a pattern.

If you like playing with bits you may like the book, "Hacker's Delight", by Henry S. Warren, Jr. In particular Ch. 7. "Rearranging Bits and Bytes".

Edited: 24 Dec 2008, 10:43 a.m.

[Allen]

At the risk of oversimplifying, may I offer a simple stack-swap program for 41/42? Assumes exactly 4 binary digits are entered into ALPHA reg. The Rv is ROLL-DOWN.

01>LBL "REV"

02 ATOX

03 ATOX

04 ATOX

05 ATOX

06 XTOA

07 Rv

08 XTOA

09 Rv

10 XTOA

11 Rv

12 XTOA

13 AVIEW

14 .END.

[Egan Ford]

Quote:

---

Given a four-bit number (0001 - 1111) in Hex (1 - F), what are the steps you would take to mirror the number?

---

41CX Version:

01 LBL "RBITS"

02 X<>F

03 CLST

04 FS? 00

05 8

06 FS? 01

07 4

08 FS? 02

09 2

10 FS? 03

11 1

12 +

13 +

14 +

15 END

[Frank Boehm (Germany)]

turn your calculator by 180 degrees - that should work :)

[SteveH]

Here's a program I wrote some years ago for my HP-42S to perform this operation of flipping the bits in a 32-bit word. It's a trivial exercise to convert this for 4-bit use.

LBL "FLIP"

STO 00

0

STO 01

1

STO 02

32

STO "COUNT"

LBL 01

RCL "COUNT"

1

-

RCL 00

X<>Y

BIT?

XEQ 02

2

STO X 02

DSE "COUNT"

GTO 01

GTO 03

LBL 02

RCL 02

STO + 01

RTN

LBL 03

RCL 01

END

Edited: 22 Dec 2008, 7:30 a.m.

[MikeO]

Hmmm,
Without bitwise operators:

<< -> X

  << X 2 MOD 8 *

     X 2 / IP 2 MOD 4 *

     X 4 / IP 2 MOD 2 *

     X 8 / IP + + +

  >>

>>

[C.Ret]

Quote:

---

Without bitwise operators:

---

With bitwise operators:

                    @  Binary integer X at level 1:

<< #0b SWAP         @  Initiate mirror result M at level 2:

   DO

      DUP #1b AND   @  Extract last bit of X (right-most)

      ROT           @  Recall previous mirror result M from lvl 2:

      SL            @  shift M one bit to the left

      OR            @  add last bit to shifted mirror result

      SWAP          @  store new miror result M to level 2:

      ASR           @  arithmetic shift right X at level 1:

   UNTIL

     DUP #0b ==     @  repeat until X is null

   END

   DROP             @  Remove null X from level 1:

>>                 

'BMIRR' STO

Usage :
#1011b [BMIRR] returns #1101b

#11100110101b [BMIRR] returns #10101100111b



Other binary integer representations may be used as well :

#61EFh [BMIRR] returns #7BC3h

#10011h [BMIRR] returns #11001h

#3210o [BMIRR] returns #213o

#110111o [BMIRR] returns #111011o

#123456789d [BMIRR] returns #88448727d

#10110011d [BMIRR] returns #14426713d

...and so on, due to respective binary internal representation of any "binary integers".

Edited: 22 Dec 2008, 4:06 p.m.

[V-PN]

#1111b XOR

[Paul Dale]

Not there unfortunately.

From the initial problem definition:

Quote:

---

(1000) would become 1 (0001)

---

Now 1111 XOR 1000 = 0111 which is wrong.

We are not trying to invert the bits, just reverse the order of them.

- Pauli

[V-PN]

Right, after taking some aspirin I found another non-working "solution" ->STR TAIL SREV 1 "#" REPL STR->

[Allen]

Quote:

---

#1111b XOR

---

Why NOT? GRIN!

[PeterP]

not sure if this is what you might be interested in, but I believe the below would work in MCODE.

Assume desired hex digit to be mirrored in C[0] with rest of C[S&X] = 0. CPU in HexMode

R=	0

A=C	S&X	;save value to be mirrored into A

LDIS&X	003	;load 0011 pattern to extract Bit 1&2

C=CANDA		;extract bits 1&2 from value

C=C+C	@R	; x2 = shift left 1 bit

C=C+C	@R	; x2 = shift left 1 bit

B<>C	@R	;save result into B[0]

LDIS&X	00C	;load 1100 pattern to extract bit 3&4

C=CANDA		;extract bits 3&4

C=C+C	S&X	;x2

C=C+C	S&X	;x4

RSHFC	S&X	;=> /4 = shift right 2 bits

A<>B	@R	;bring first result into A

C=A+C	@R	;mirrored result in C[0]

assuming that the problem is for hex numbers, the mirroring of even number of hex digits in MCODE is trivial (using P-Q as location post-fix with C<>A etc commands and the correct RCR's). For odd number of hex digits, only the middle one has to be mirrored with a code like the one above sketched out, while the remaining 'even' hex digits can be mirrored in the trivial fashion.

hope that helps.

Cheers

Peter

[Geir Isene]

I was fishing for ideas to use in my ICEBOX.ROM - and PeterP jumped right on it and created the code for me - way above my expectations. Thank you very much. Great input from others as well. Thanks.

[Didier Lachieze]

The following routine from the X-Function VASM listing page 22 seems to do the same for 8 bits:

*

*

*******************************

*  SWPBIT — ROUTINE TO REVERSE THE 8 BITS IN A[1:0] 

*    INPUT : A[1:0] = THE 8 BITS

*    OUTPUT: A[1:0] = SWAPPED 8 BITS

*            PT     = 1

*    USED A.X, C.X, PT   +0 SUBLEVEL

  1134                  ENTRY  SWPBIT

*

  1136 1756 SWPBIT 1134 PT=    9

  1137 1757        1746 A SL   X             A[2:1] = STATUS BYTE

  1138 1760         246 AC EX  X             C[2:1]= REMAINING STATUS BYTE

  1139 1761 STS30    26 A=0    XS            A[1:0]= SWITCHED STATUS BYTE

  1140 1762         746 C=C+C  X

  1141 1763          23 GONC   STS40 (1765)

  1142 1764         566 A=A+1  XS

  1143 1765 STS40   246 AC EX  X

  1144 1766         746 C=C+C  X

  1145 1767         746 C=C+C  X

  1146 1770         746 C=C+C  X

  1147 1771        1706 C SR   X

  1148 1772         246 AC EX  X

  1149 1773        1724 DEC PT

  1150 1774        1424 ? PT=  1

  1151 1775        1643 GONC   STS30 (1761)

  1152 1776        1740 RTN

*

[MikeO]

I thought it would look nice in the language of mathematics:

-Mike

[dbatiz]

This doesn't address the 4 bit requirement, but will produce the decimal equivelent of the biary mirror image for any natural number, decimal input:

Written for the HP35s

M001 LBL M   M011 GTO M014

M002 STO A   M012 1

M003 0       M013 STO+ B

M004 STO B   M014 RCL A

M005 2       M015 IP

M006 STO* B  M016 STO A

M007 STO/ A  M017 x>0?

M008 RCL A   M018 GTO M005

M009 FP      M019 RCL B

M010 X=0?    M020 RTN

Very respectfully,

David