The Museum of HP Calculators

HP Forum Archive 18

[ Return to Index | Top of Index ]

Challenge: Mirror bits
Message #1 Posted by Geir Isene on 21 Dec 2008, 3:07 p.m.

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.

      
Re: Challenge: Mirror bits
Message #2 Posted by Paul Dale on 21 Dec 2008, 4:12 p.m.,
in response to message #1 by Geir Isene

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

            
Re: Challenge: Mirror bits
Message #3 Posted by Geir Isene on 21 Dec 2008, 5:24 p.m.,
in response to message #2 by Paul Dale

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

                  
Re: Challenge: Mirror bits
Message #4 Posted by Egan Ford on 21 Dec 2008, 5:45 p.m.,
in response to message #3 by Geir Isene

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.
                        
Re: Challenge: Mirror bits
Message #5 Posted by Paul Dale on 21 Dec 2008, 5:51 p.m.,
in response to message #4 by Egan Ford

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

- Pauli

                              
Re: Challenge: Mirror bits
Message #6 Posted by Egan Ford on 21 Dec 2008, 6:40 p.m.,
in response to message #5 by Paul Dale

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
                  
Re: Challenge: Mirror bits
Message #7 Posted by Paul Dale on 21 Dec 2008, 5:50 p.m.,
in response to message #3 by Geir Isene

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

                        
Re: Challenge: Mirror bits
Message #8 Posted by Egan Ford on 21 Dec 2008, 6:49 p.m.,
in response to message #7 by Paul Dale

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;
                              
Re: Challenge: Mirror bits
Message #9 Posted by Paul Dale on 21 Dec 2008, 7:45 p.m.,
in response to message #8 by Egan Ford

That works nicely!

- Pauli

                              
Re: Challenge: Mirror bits
Message #10 Posted by C.Ret on 23 Dec 2008, 11:54 a.m.,
in response to message #8 by Egan Ford

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.

                                    
Re: Challenge: Mirror bits
Message #11 Posted by Egan Ford on 23 Dec 2008, 12:04 p.m.,
in response to message #10 by C.Ret

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

                                          
Re: Challenge: Mirror bits
Message #12 Posted by C.Ret on 24 Dec 2008, 3:55 a.m.,
in response to message #11 by Egan Ford

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
                                                
Re: Challenge: Mirror bits
Message #13 Posted by Egan Ford on 24 Dec 2008, 10:33 a.m.,
in response to message #12 by C.Ret

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.

                        
Re: Challenge: Mirror bits
Message #14 Posted by Allen on 21 Dec 2008, 7:17 p.m.,
in response to message #7 by Paul Dale

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.
      
Re: Challenge: Mirror bits
Message #15 Posted by Egan Ford on 21 Dec 2008, 11:33 p.m.,
in response to message #1 by Geir Isene

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
      
one step solution
Message #16 Posted by Frank Boehm (Germany) on 22 Dec 2008, 6:30 a.m.,
in response to message #1 by Geir Isene

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

      
Re: Challenge: Mirror bits
Message #17 Posted by SteveH on 22 Dec 2008, 7:29 a.m.,
in response to message #1 by Geir Isene

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.

      
Re: Challenge: Mirror bits
Message #18 Posted by MikeO on 22 Dec 2008, 7:46 a.m.,
in response to message #1 by Geir Isene

Hmmm, Without bitwise operators: 

<< -> X
  << X 2 MOD 8 *
     X 2 / IP 2 MOD 4 *
     X 4 / IP 2 MOD 2 *
     X 8 / IP + + +
  >>
>>

            
Re: Challenge: Mirror bits
Message #19 Posted by C.Ret on 22 Dec 2008, 3:57 p.m.,
in response to message #18 by MikeO

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.

      
Re: Challenge: Mirror bits
Message #20 Posted by V-PN on 22 Dec 2008, 1:45 p.m.,
in response to message #1 by Geir Isene

#1111b XOR

            
Re: Challenge: Mirror bits
Message #21 Posted by Paul Dale on 22 Dec 2008, 3:59 p.m.,
in response to message #20 by V-PN

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

                  
Re: Challenge: Mirror bits
Message #22 Posted by V-PN on 22 Dec 2008, 7:26 p.m.,
in response to message #21 by Paul Dale

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

            
Re: Challenge: Mirror bits
Message #23 Posted by Allen on 22 Dec 2008, 8:48 p.m.,
in response to message #20 by V-PN

Quote:
#1111b XOR
Why NOT? GRIN!
      
Re: Challenge: Mirror bits - in MCODE
Message #24 Posted by PeterP on 22 Dec 2008, 4:02 p.m.,
in response to message #1 by Geir Isene

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

            
Re: Challenge: Mirror bits - in MCODE
Message #25 Posted by Geir Isene on 22 Dec 2008, 6:12 p.m.,
in response to message #24 by PeterP

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.

                  
Re: Challenge: Mirror bits - in MCODE
Message #26 Posted by Didier Lachieze on 25 Dec 2008, 7:10 p.m.,
in response to message #25 by Geir Isene

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
*
      
Re: Challenge: Mirror bits
Message #27 Posted by MikeO on 22 Dec 2008, 5:42 p.m.,
in response to message #1 by Geir Isene

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

-Mike

      
Re: Challenge: Mirror bits
Message #28 Posted by dbatiz on 23 Dec 2008, 10:28 a.m.,
in response to message #1 by Geir Isene

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

[ Return to Index | Top of Index ]

Go back to the main exhibit hall