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.
The following warnings occurred: | |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
Warning [2] Undefined array key 144896 - Line: 275 - File: inc/plugins/threaded_mode.php PHP 8.1.2-1ubuntu2.14 (Linux)
|
Challenge: Mirror bits
|
|
« Next Oldest | Next Newest »
|
▼
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. ▼
12-21-2008, 04:12 PM
I'd approach this one of three ways:
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 ▼
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? ▼
12-21-2008, 05:45 PM
Quote:Something like this: $obits=0; # output bitsYou should be able to do this on the 15C. ▼
12-21-2008, 05:51 PM
This is the naive algorithm I mentioned written as a loop not inline code. - Pauli ▼
12-21-2008, 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
12-21-2008, 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 ▼
12-21-2008, 06:49 PM
Quote:How about: y = ((x * 0x00082082 & 0x01122408) % 255) >> 2; ▼
12-21-2008, 07:45 PM
That works nicely! - Pauli
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 :
Edited: 23 Dec 2008, 11:54 a.m. ▼
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. ▼
12-24-2008, 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 ▼
12-24-2008, 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.
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"
12-21-2008, 11:33 PM
Quote:41CX Version: 01 LBL "RBITS"
12-22-2008, 06:30 AM
turn your calculator by 180 degrees - that should work :)
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" Edited: 22 Dec 2008, 7:30 a.m.
12-22-2008, 07:46 AM
Hmmm, << -> X
▼
12-22-2008, 03:57 PM
Quote:
With bitwise operators: @ Binary integer X at level 1:
Usage :
Edited: 22 Dec 2008, 4:06 p.m.
12-22-2008, 01:45 PM
#1111b XOR ▼
12-22-2008, 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.
▼
12-22-2008, 07:26 PM
Right, after taking some aspirin I found another non-working "solution" ->STR TAIL SREV 1 "#" REPL STR->
12-22-2008, 08:48 PM
Quote:Why NOT? GRIN!
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 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 ▼
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. ▼
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:
*
12-22-2008, 05:42 PM
I thought it would look nice in the language of mathematics:
-Mike
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 M014Very respectfully, David |
Possibly Related Threads… | |||||
Thread | Author | Replies | Views | Last Post | |
Prime Program number of set bits | kris223 | 3 | 1,820 |
10-23-2013, 03:05 PM Last Post: David Hayden |
|
combinations of k bits wp34s | Andrew Nikitin | 11 | 3,018 |
09-02-2013, 07:32 PM Last Post: mjcohen |
|
RE: 35s sorting routine challenge - Gene's Challenge | Miguel Toro | 4 | 1,542 |
08-01-2007, 08:36 AM Last Post: Miguel Toro |
|
HP-15C Mini-Challenge: Bits o'Pi | Valentin Albillo | 67 | 12,106 |
03-24-2007, 03:57 PM Last Post: Karl Schneider |
|
Mini-Challenge: Twiddling the bits | Valentin Albillo | 30 | 6,081 |
06-27-2006, 12:02 AM Last Post: Karl Schneider |
|
HP-71B - HP-41 Translator Bits? | Howard Owen | 19 | 4,150 |
09-13-2005, 07:04 PM Last Post: Eric Smith |
|
28C, other bits. | koyote | 1 | 791 |
04-30-2002, 07:04 AM Last Post: Vieira, Luiz C. (Brazil) |