The Museum of HP Calculators

HP Forum Archive 18

 Challenge: Mirror bitsMessage #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 bitsMessage #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: The naive approach of shifting and testing the low order bit Use a 16 element lookup table 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 bitsMessage #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 bitsMessage #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 bitsMessage #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 bitsMessage #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 bitsMessage #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 bitsMessage #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 bitsMessage #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 bitsMessage #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 bitsMessage #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 bitsMessage #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 bitsMessage #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 bitsMessage #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 bitsMessage #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 solutionMessage #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 bitsMessage #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 bitsMessage #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 bitsMessage #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 bitsMessage #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 bitsMessage #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 bitsMessage #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 bitsMessage #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 MCODEMessage #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 MCODEMessage #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 MCODEMessage #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 bitsMessage #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 bitsMessage #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

Go back to the main exhibit hall