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.
Challenge: Mirror bits
|
|
« Next Oldest | Next Newest »
|
▼
Post: #29
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. ▼
Post: #30
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 ▼
Post: #31
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? ▼
Post: #32
12-21-2008, 05:45 PM
Quote:Something like this: $obits=0; # output bitsYou should be able to do this on the 15C. ▼
Post: #33
12-21-2008, 05:51 PM
This is the naive algorithm I mentioned written as a loop not inline code. - Pauli ▼
Post: #34
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
Post: #35
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 ▼
Post: #36
12-21-2008, 06:49 PM
Quote:How about: y = ((x * 0x00082082 & 0x01122408) % 255) >> 2; ▼
Post: #38
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. ▼
Post: #39
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. ▼
Post: #40
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 ▼
Post: #41
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.
Post: #42
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"
Post: #43
12-21-2008, 11:33 PM
Quote:41CX Version: 01 LBL "RBITS"
Post: #45
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.
Post: #46
12-22-2008, 07:46 AM
Hmmm, << -> X
▼
Post: #47
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. ▼
Post: #49
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.
▼
Post: #50
12-22-2008, 07:26 PM
Right, after taking some aspirin I found another non-working "solution" ->STR TAIL SREV 1 "#" REPL STR->
Post: #52
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 ▼
Post: #53
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. ▼
Post: #54
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:
*
Post: #56
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 |