Given a fourbit 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.
Challenge: Mirror bits


« Next Oldest  Next Newest »

▼
12212008, 03:07 PM
Given a fourbit 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. ▼
12212008, 04:12 PM
I'd approach this one of three ways:
For a 4bit 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 ▼
12212008, 05:24 PM
How would you do it without going via binary; i.e. how would you manipulate the hex digit directly? ▼
12212008, 05:45 PM
Quote:Something like this: $obits=0; # output bitsYou should be able to do this on the 15C. ▼
12212008, 05:51 PM
This is the naive algorithm I mentioned written as a loop not inline code.  Pauli ▼
12212008, 06:40 PM
Yes, but it is the only way to met Geir's second condition: Quote: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
12212008, 05:50 PM
Based on two just about the reference I posted:
y = ((x * 0x0802 & 0x22110)  (x * 0x8020 & 0x88440)) * 0x10101 >> 20 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 ▼
12212008, 06:49 PM
Quote:How about: y = ((x * 0x00082082 & 0x01122408) % 255) >> 2; ▼
12212008, 07:45 PM
That works nicely!  Pauli
12232008, 11:54 AM
Quote:y = ((x * 0x00082082 & 0x01122408) % 255) >> 2; I have same trouble interpretating this line of code !
As I understand this code :
Edited: 23 Dec 2008, 11:54 a.m. ▼
12232008, 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. ▼
12242008, 03:55 AM
Thank you for the information and your time.
It is always time to learn something :)
Translate into RPL the mirror operation may be translate to : << #00082082h * @ multiplication by a binary convert result to It's work perfectly ! But I still analysing why !
The trick is certainly based on the magic numbers : #00082082h = # 00000000000010000010000010000010_b ▼
12242008, 10:33 AM
Quote: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.
12212008, 07:17 PM
At the risk of oversimplifying, may I offer a simple stackswap program for 41/42? Assumes exactly 4 binary digits are entered into ALPHA reg. The Rv is ROLLDOWN. 01>LBL "REV"
12212008, 11:33 PM
Quote:41CX Version: 01 LBL "RBITS"
12222008, 06:30 AM
turn your calculator by 180 degrees  that should work :)
12222008, 07:29 AM
Here's a program I wrote some years ago for my HP42S to perform this operation of flipping the bits in a 32bit word. It's a trivial exercise to convert this for 4bit use.
LBL "FLIP" Edited: 22 Dec 2008, 7:30 a.m.
12222008, 07:46 AM
Hmmm, << > X
▼
12222008, 03:57 PM
Quote:
With bitwise operators: @ Binary integer X at level 1:
Usage :
Edited: 22 Dec 2008, 4:06 p.m.
12222008, 01:45 PM
#1111b XOR ▼
12222008, 03:59 PM
Not there unfortunately. From the initial problem definition:
Quote: Now 1111 XOR 1000 = 0111 which is wrong. We are not trying to invert the bits, just reverse the order of them.
▼
12222008, 07:26 PM
Right, after taking some aspirin I found another nonworking "solution" >STR TAIL SREV 1 "#" REPL STR>
12222008, 08:48 PM
Quote:Why NOT? GRIN!
12222008, 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 assuming that the problem is for hex numbers, the mirroring of even number of hex digits in MCODE is trivial (using PQ as location postfix 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 ▼
12222008, 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. ▼
12252008, 07:10 PM
The following routine from the XFunction VASM listing page 22 seems to do the same for 8 bits:
*
12222008, 05:42 PM
I thought it would look nice in the language of mathematics:
Mike
12232008, 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 M014Very respectfully, David 
Possibly Related Threads...  
Thread  Author  Replies  Views  Last Post  
Prime Program number of set bits  kris223  3  606 
10232013, 03:05 PM Last Post: David Hayden 

combinations of k bits wp34s  Andrew Nikitin  11  1,017 
09022013, 07:32 PM Last Post: mjcohen 

RE: 35s sorting routine challenge  Gene's Challenge  Miguel Toro  4  593 
08012007, 08:36 AM Last Post: Miguel Toro 

HP15C MiniChallenge: Bits o'Pi  Valentin Albillo  67  3,437 
03242007, 03:57 PM Last Post: Karl Schneider 

MiniChallenge: Twiddling the bits  Valentin Albillo  30  2,119 
06272006, 12:02 AM Last Post: Karl Schneider 

HP71B  HP41 Translator Bits?  Howard Owen  19  1,338 
09132005, 07:04 PM Last Post: Eric Smith 

28C, other bits.  koyote  1  259 
04302002, 07:04 AM Last Post: Vieira, Luiz C. (Brazil) 