(16C) show which bits are set in a number

[cdmackay]

I just wrote my first (!) RPN program.

I'm posting it here not because I think it will be of any great use to anyone but me, as it's likely naive in the extreme, but I would appreciate any criticism on how it might be improved, better RPN techniques, etc. It turned out rather more unwieldy than I'd hoped.

I'm not concerned about performance, but I would like minimise the precious resources used, e.g. registers/lines/labels.

It simply shows what bit positions are set in whatever is in X, using a single PSE to show each bit position.

When I'm decoding values, I often find myself counting bits: ah yes, bits 15 and 11 are set in that MMU register, let's see what that means. And I'm often miscounting, losing place, etc.

Alternatively, debugging C code like:

Code:

if (value & 0x00003800)
    do_one();

and having to work out: which bits are those being tested?

Here's the code:

Code:

LBL A
STO 0                           # X -> R0
#B                                # number of bits set -> RI
STO I                            #    as a decrementing loop index
RCL 0                           # original number
0                                  # start testing at bit 0
STO 1                           # bit to test
LBL 0
B?                                 # if bit is set
GTO 2                           #    jump down to show bit
LBL 1                            # else continue
RCL 1                           # incr bit to test
1
+
STO 1
GTO 0                           # jump up to re-test
LBL 2
RCL 1
PSE                             # show bit
RCL 0                           # recall original number
DSZ                              # if --RI != 0 (more bits to test?)
GTO 1                          #    jump back up
RTN                             # else Return; original number will be displayed


Register use
Index   number of bits set in original number
R0      original number
R1      bit currently being tested


Labels: A, 0–2

Thanks very much indeed for any comments.

[Thomas Klemm]

(03-04-2019 12:57 AM)cdmackay Wrote:  I just wrote my first (!) RPN program.

Welcome to the club!

Quote:I'm not concerned about performance, but I would like minimise the precious resources used, e.g. registers/lines/labels.

I have just removed the use of registers (besides register I):

Code:

001-43,22, A :   ▸LBL A
002-    43 7 :    #B
003-   44 32 :    STO I
004-   43 36 :    LSTx
005-       0 :    0
006-43,22, 0 :   ▸LBL 0
007-    42 6 :    B?
008-    22 2 :    GTO 2
009-   43 36 :    LSTx
010-43,22, 1 :   ▸LBL 1
011-       1 :    1
012-      40 :    +
013-    22 0 :    GTO 0
014-43,22, 2 :   ▸LBL 2
015-   43 36 :    LSTx
016-   43 34 :    PSE
017-   43 23 :    DSZ
018-    22 1 :    GTO 1
019       33 :    R↓
020-   43 21 :    RTN

Example:

23 d
GSB A

»0 d«
»1 d«
»2 d«
»4 d«
23 d

Cheers
Thomas

[cdmackay]

(03-04-2019 02:15 AM)Thomas Klemm Wrote:  I have just removed the use of registers (besides register I):

oh! that's great, thanks very much indeed, Thomas. I'd forgotten about using LSTX/Rv in a program. And it saves 3 lines too

thanks.

[Thomas Klemm]

(03-04-2019 04:02 PM)cdmackay Wrote:  I'd forgotten about using LSTX/Rv in a program.

I'm not that familiar with the HP-16C, so I was a little surprised that the B? command consumes the x-register.
Since the next command is a branch-instruction, the LSTx command to recover x has to be executed twice in lines 009 and 015.
Otherwise we could remove these two commands.

Check-commands like x=y don't modify the stack, so this behaviour isn't consistent.
However it might be beneficial when register I is used as the index.

Congratulations! That's a nice little program.
I like particularly that its flow is like a backstitch when returning to the top after displaying the index.

Cheers
Thomas

[cdmackay]

thanks very much again, Thomas.

(03-04-2019 05:37 PM)Thomas Klemm Wrote:  I'm not that familiar with the HP-16C, so I was a little surprised that the B? command consumes the x-register.

I was also surprised to find that it can't usefully be used in Run mode, as far as I can see. I'd have thought a shortcut to checking whether bit n is set would be generally useful, other than solely as a branch control in a program.

Without that, if you want to check bit 52, for example, you need to work out mentally that you need WINDOW 6, then count along 4 bits. That's a bit (ahem) error-prone, at least when I do it. Alternatively: "1 52 RLn X<>Y AND". Then LSTx your original number.

That led me to the trivial:

Code:

LBL B
B?
1
0

e.g: "X 52 GSB B"

Perhaps I'm missing something obvious

Quote:I like particularly that its flow is like to a backstitch when returning to the top after displaying the index.

I won't take any credit: it just fell out that way

I liked that I could use #B to initialise the loop index so I stop as soon as I've found all the set bits, without having to check WSIZE bits.


I was going to have it also output #B, but since the original number is preserved, the user can simply do it themselves immediately after, or do "#B LSTx" before.

[Thomas Klemm]

(03-04-2019 06:42 PM)cdmackay Wrote:  I was also surprised to find that it can't usefully be used in Run mode, as far as I can see.

IIRC all checks executed in Run mode single step the program counter if the result is false.
Not sure if that could be used though.

[cdmackay]

(03-04-2019 08:22 PM)Thomas Klemm Wrote:  IIRC all checks executed in Run mode single step the program counter if the result is false.

yup, confirmed. An odd way to check though

thanks.

[wynen]

Here is another approach using the bit shift features of the HP-16C:

Code:


001-43,22, A : ->LBL A
002-       0 :   0
003-   44 32 :   STO I     // I = bit number
004-      33 :   Rdown
005-      36 :   Enter     // x = y = input
006-43,22, 0 : ->LBL 0
007-   42  b :   SR
008-43, 6, 4 :   F? 4      // carry set?
009-   43  2 :   x<0       // yes, but x<0 is always false (because of shift right)
010-   22  1 :   GTO 1     // carry not set
011-   45 32 :   RCL I     // carry set, show bit number
012-   43 34 :   PSE
013-      33 :   Rdown
014-43,22, 1 : ->LBL 1     // increment bit number
015-   43 24 :   ISZ
016-   43 48 :   x<>0      // are there any bits left?
017-   22  0 :   GTO 0     // yes, go on
018-      33 :   Rdown     // no, show original input
019-   43 21 :   RTN

Thank you for this nice littly problem.

Hartmut

[Dieter]

(03-06-2019 09:41 AM)wynen Wrote:  

Code:

008-43, 6, 4 :   F? 4      // carry set?
009-   43  2 :   x<0       // yes, but x<0 is always false (because of shift right)
010-   22  1 :   GTO 1     // carry not set

Ah, great – one of the good old tricks from the golden days of RPN programming: have a test followed by another one that always tests false, and you get an inverse test. So the combination of F? 4 and x<0? tests if flag 4 is clear.

I wouldn't have expected that anyone may still remember these things. ;-)

Dieter

[wynen]

But the trick is not needed and the program could be smaller

Code:


001-43,22, A : ->LBL A
002-       0 :   0
003-   44 32 :   STO I     // I = bit number
004-      33 :   Rdown
005-      36 :   Enter     // x = y = number to test
006-43,22, 0 : ->LBL 0
007-   42  b :   SR
008-   45 32 :   RCL I
009-43, 6, 4 :   F? 4      // carry set?
010-   43 34 :   PSE
011-      33 :   Rdown
012-   43 24 :   ISZ
013-   43 48 :   x<>0      // are there any bits left?
014-   22  0 :   GTO 0     // yes, go on
015-      33 :   Rdown     // no, show original input
016-   43 21 :   RTN

Registers: I
Labels: A. 0

Hartmut

[Sylvain Cote]

Personally, I would add clear flag 4 just to be tidy

Code:

016-43, 5, 4 :   CF 4      // clear carry bit

Nice programs by the way.
Sylvain

[cdmackay]

(03-06-2019 09:41 AM)wynen Wrote:  Here is another approach using the bit shift features of the HP-16C:

thanks very much! I'll study this tomorrow, too late tonight…

[cdmackay]

One slight inefficiency is that you test all the bits; i might add back in my use of #b so we can stop when we know we've found them all.

but I like the shifting technique, thanks

[wynen]

In fact your program will test all the bits beginning with LSB as well and stops when all bits set where found. This is the same behaviour as in my program.

Code:

013-   43 48 :   x<>0      // are there any bits left?

[cdmackay]

(03-07-2019 09:45 AM)wynen Wrote:  In fact your program will test all the bits beginning with LSB as well and stops when all bits set where found. This is the same behaviour as in my program.

Code:

013-   43 48 :   x<>0      // are there any bits left?

argh! sorry, missed that test

thanks again.

[cdmackay]

Having seen mfleming's (to whom thanks) recently-posted program to work out the current WSIZE, I realised that you get this almost for free with the program I posted here.

All that's needed — I think — is something like:

Code:

LBL B    # WSIZE?
1
RR
GSB A    # or however my program is labelled

and then add one to get the word size. Haven't checked whether there are any nasties depending on complement, yet. No need to clear carry as A should do that (as Sylvain suggested)

I might change my original program so that it doesn't recall the original number, and then the above could do the addition to present the WSIZE directly.

Any good?

[cdmackay]

Although now that mfleming has updated their program to be as simple as:

CLx
NOT
B#

that might be simpler still