(16C) show which bits are set in a number
03-04-2019, 12:57 AM
Post: #1
 cdmackay Senior Member Posts: 453 Joined: Sep 2018
(16C) show which bits are set in a number
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.

Cambridge, UK
41CL/DM41X 12/15C/16C DM15/16 71B 17B/BII/bII+ 28S 42S/DM42 48GX 50g 35s 30b/WP34S Prime G2
& Casios, Rockwell 18R :)
03-04-2019, 02:15 AM
Post: #2
 Thomas Klemm Senior Member Posts: 1,447 Joined: Dec 2013
RE: (16C) show which bits are set in a number
(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
03-04-2019, 04:02 PM
Post: #3
 cdmackay Senior Member Posts: 453 Joined: Sep 2018
RE: (16C) show which bits are set in a number
(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.

Cambridge, UK
41CL/DM41X 12/15C/16C DM15/16 71B 17B/BII/bII+ 28S 42S/DM42 48GX 50g 35s 30b/WP34S Prime G2
& Casios, Rockwell 18R :)
03-04-2019, 05:37 PM (This post was last modified: 03-04-2019 08:23 PM by Thomas Klemm.)
Post: #4
 Thomas Klemm Senior Member Posts: 1,447 Joined: Dec 2013
RE: (16C) show which bits are set in a number
(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
03-04-2019, 06:42 PM
Post: #5
 cdmackay Senior Member Posts: 453 Joined: Sep 2018
RE: (16C) show which bits are set in a number
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.

Cambridge, UK
41CL/DM41X 12/15C/16C DM15/16 71B 17B/BII/bII+ 28S 42S/DM42 48GX 50g 35s 30b/WP34S Prime G2
& Casios, Rockwell 18R :)
03-04-2019, 08:22 PM
Post: #6
 Thomas Klemm Senior Member Posts: 1,447 Joined: Dec 2013
RE: (16C) show which bits are set in a number
(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.
03-04-2019, 10:35 PM
Post: #7
 cdmackay Senior Member Posts: 453 Joined: Sep 2018
RE: (16C) show which bits are set in a number
(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.

Cambridge, UK
41CL/DM41X 12/15C/16C DM15/16 71B 17B/BII/bII+ 28S 42S/DM42 48GX 50g 35s 30b/WP34S Prime G2
& Casios, Rockwell 18R :)
03-06-2019, 09:41 AM
Post: #8
 wynen Junior Member Posts: 12 Joined: Sep 2014
RE: (16C) show which bits are set in a number
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
03-06-2019, 06:57 PM
Post: #9
 Dieter Senior Member Posts: 2,397 Joined: Dec 2013
RE: (16C) show which bits are set in a number
(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
03-06-2019, 10:16 PM (This post was last modified: 03-06-2019 10:17 PM by wynen.)
Post: #10
 wynen Junior Member Posts: 12 Joined: Sep 2014
RE: (16C) show which bits are set in a number
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
03-07-2019, 12:45 AM
Post: #11
 Sylvain Cote Senior Member Posts: 1,226 Joined: Dec 2013
RE: (16C) show which bits are set in a number
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
03-07-2019, 01:41 AM
Post: #12
 cdmackay Senior Member Posts: 453 Joined: Sep 2018
RE: (16C) show which bits are set in a number
(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…

Cambridge, UK
41CL/DM41X 12/15C/16C DM15/16 71B 17B/BII/bII+ 28S 42S/DM42 48GX 50g 35s 30b/WP34S Prime G2
& Casios, Rockwell 18R :)
03-07-2019, 01:45 AM
Post: #13
 cdmackay Senior Member Posts: 453 Joined: Sep 2018
RE: (16C) show which bits are set in a number
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

Cambridge, UK
41CL/DM41X 12/15C/16C DM15/16 71B 17B/BII/bII+ 28S 42S/DM42 48GX 50g 35s 30b/WP34S Prime G2
& Casios, Rockwell 18R :)
03-07-2019, 09:45 AM
Post: #14
 wynen Junior Member Posts: 12 Joined: Sep 2014
RE: (16C) show which bits are set in a number
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?
03-07-2019, 08:31 PM
Post: #15
 cdmackay Senior Member Posts: 453 Joined: Sep 2018
RE: (16C) show which bits are set in a number
(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.

Cambridge, UK
41CL/DM41X 12/15C/16C DM15/16 71B 17B/BII/bII+ 28S 42S/DM42 48GX 50g 35s 30b/WP34S Prime G2
& Casios, Rockwell 18R :)
03-30-2019, 11:33 PM
Post: #16
 cdmackay Senior Member Posts: 453 Joined: Sep 2018
RE: (16C) show which bits are set in a number
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?

Cambridge, UK
41CL/DM41X 12/15C/16C DM15/16 71B 17B/BII/bII+ 28S 42S/DM42 48GX 50g 35s 30b/WP34S Prime G2
& Casios, Rockwell 18R :)
03-31-2019, 02:40 PM
Post: #17
 cdmackay Senior Member Posts: 453 Joined: Sep 2018
RE: (16C) show which bits are set in a number
Although now that mfleming has updated their program to be as simple as:

CLx
NOT
B#

that might be simpler still

Cambridge, UK
41CL/DM41X 12/15C/16C DM15/16 71B 17B/BII/bII+ 28S 42S/DM42 48GX 50g 35s 30b/WP34S Prime G2
& Casios, Rockwell 18R :)
 « Next Oldest | Next Newest »

User(s) browsing this thread: 1 Guest(s)