Challenge: Mirror bits « Next Oldest | Next Newest »

 ▼ Geir Isene Posting Freak Posts: 896 Threads: 183 Joined: Jul 2005 12-21-2008, 03:07 PM 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 Posting Freak Posts: 3,229 Threads: 42 Joined: Jul 2006 12-21-2008, 04:12 PM 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 ▼ Geir Isene Posting Freak Posts: 896 Threads: 183 Joined: Jul 2005 12-21-2008, 05:24 PM How would you do it without going via binary; i.e. how would you manipulate the hex digit directly? ▼ Egan Ford Posting Freak Posts: 1,619 Threads: 147 Joined: May 2006 12-21-2008, 05:45 PM 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 Posting Freak Posts: 3,229 Threads: 42 Joined: Jul 2006 12-21-2008, 05:51 PM This is the naive algorithm I mentioned written as a loop not inline code. - Pauli ▼ Egan Ford Posting Freak Posts: 1,619 Threads: 147 Joined: May 2006 12-21-2008, 06:40 PM 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 Posting Freak Posts: 3,229 Threads: 42 Joined: Jul 2006 12-21-2008, 05:50 PM 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 Posting Freak Posts: 1,619 Threads: 147 Joined: May 2006 12-21-2008, 06:49 PM 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 Posting Freak Posts: 3,229 Threads: 42 Joined: Jul 2006 12-21-2008, 07:45 PM That works nicely! - Pauli C.Ret Senior Member Posts: 260 Threads: 0 Joined: Oct 2008 12-23-2008, 11:54 AM 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 Posting Freak Posts: 1,619 Threads: 147 Joined: May 2006 12-23-2008, 12:04 PM % 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 Senior Member Posts: 260 Threads: 0 Joined: Oct 2008 12-24-2008, 03:55 AM 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 Posting Freak Posts: 1,619 Threads: 147 Joined: May 2006 12-24-2008, 10:33 AM 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 Senior Member Posts: 562 Threads: 27 Joined: Oct 2006 12-21-2008, 07:17 PM 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 Posting Freak Posts: 1,619 Threads: 147 Joined: May 2006 12-21-2008, 11:33 PM 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) Senior Member Posts: 415 Threads: 19 Joined: Jan 2005 12-22-2008, 06:30 AM turn your calculator by 180 degrees - that should work :) SteveH Member Posts: 50 Threads: 16 Joined: Feb 2006 12-22-2008, 07:29 AM 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 Member Posts: 121 Threads: 21 Joined: Jun 2008 12-22-2008, 07:46 AM 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 Senior Member Posts: 260 Threads: 0 Joined: Oct 2008 12-22-2008, 03:57 PM 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 Posting Freak Posts: 785 Threads: 13 Joined: Jan 2005 12-22-2008, 01:45 PM #1111b XOR ▼ Paul Dale Posting Freak Posts: 3,229 Threads: 42 Joined: Jul 2006 12-22-2008, 03:59 PM 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 Posting Freak Posts: 785 Threads: 13 Joined: Jan 2005 12-22-2008, 07:26 PM Right, after taking some aspirin I found another non-working "solution" ->STR TAIL SREV 1 "#" REPL STR-> Allen Senior Member Posts: 562 Threads: 27 Joined: Oct 2006 12-22-2008, 08:48 PM Quote: #1111b XOR Why NOT? GRIN! PeterP Senior Member Posts: 564 Threads: 72 Joined: Sep 2005 12-22-2008, 04:02 PM 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 Posting Freak Posts: 896 Threads: 183 Joined: Jul 2005 12-22-2008, 06:12 PM 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 Member Posts: 248 Threads: 5 Joined: Feb 2008 12-25-2008, 07:10 PM 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 Member Posts: 121 Threads: 21 Joined: Jun 2008 12-22-2008, 05:42 PM I thought it would look nice in the language of mathematics: -Mike dbatiz Member Posts: 64 Threads: 8 Joined: Oct 2006 12-23-2008, 10:28 AM 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

 Possibly Related Threads... Thread Author Replies Views Last Post Prime Program number of set bits kris223 3 357 10-23-2013, 03:05 PM Last Post: David Hayden combinations of k bits wp34s Andrew Nikitin 11 646 09-02-2013, 07:32 PM Last Post: mjcohen RE: 35s sorting routine challenge - Gene's Challenge Miguel Toro 4 333 08-01-2007, 08:36 AM Last Post: Miguel Toro HP-15C Mini-Challenge: Bits o'Pi Valentin Albillo 67 2,017 03-24-2007, 03:57 PM Last Post: Karl Schneider Mini-Challenge: Twiddling the bits Valentin Albillo 30 1,371 06-27-2006, 12:02 AM Last Post: Karl Schneider HP-71B - HP-41 Translator Bits? Howard Owen 19 887 09-13-2005, 07:04 PM Last Post: Eric Smith 28C, other bits. koyote 1 150 04-30-2002, 07:04 AM Last Post: Vieira, Luiz C. (Brazil)

Forum Jump: