Challenge: Mirror bits



#2

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.


#3

I'd approach this one of three ways:

  1. The naive approach of shifting and testing the low order bit
  2. Use a 16 element lookup table
  3. 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


#4

How would you do it without going via binary; i.e. how would you manipulate the hex digit directly?


#5

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.

#6

This is the naive algorithm I mentioned written as a loop not inline code.

- Pauli


#7

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
#8

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


#9

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;

#10

That works nicely!

- Pauli

#11

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.


#12

% 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.


#13

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

#14

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.

#15

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.
#16

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
#17

turn your calculator by 180 degrees - that should work :)

#18

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.

#19

Hmmm,
Without bitwise operators:

<< -> X
<< X 2 MOD 8 *
X 2 / IP 2 MOD 4 *
X 4 / IP 2 MOD 2 *
X 8 / IP + + +
>>
>>


#20

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.

#21

#1111b XOR


#22

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


#23

Right, after taking some aspirin I found another non-working "solution" ->STR TAIL SREV 1 "#" REPL STR->

#24

Quote:
#1111b XOR

Why NOT? GRIN!
#25

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


#26

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.


#27

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
*
#28

I thought it would look nice in the language of mathematics:

-Mike

#29

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 221 10-23-2013, 03:05 PM
Last Post: David Hayden
  combinations of k bits wp34s Andrew Nikitin 11 375 09-02-2013, 07:32 PM
Last Post: mjcohen
  RE: 35s sorting routine challenge - Gene's Challenge Miguel Toro 4 212 08-01-2007, 08:36 AM
Last Post: Miguel Toro
  HP-15C Mini-Challenge: Bits o'Pi Valentin Albillo 67 1,095 03-24-2007, 03:57 PM
Last Post: Karl Schneider
  Mini-Challenge: Twiddling the bits Valentin Albillo 30 783 06-27-2006, 12:02 AM
Last Post: Karl Schneider
  HP-71B - HP-41 Translator Bits? Howard Owen 19 590 09-13-2005, 07:04 PM
Last Post: Eric Smith
  28C, other bits. koyote 1 91 04-30-2002, 07:04 AM
Last Post: Vieira, Luiz C. (Brazil)

Forum Jump: