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

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

+- HP Forums (https://www.hpmuseum.org/forum)
+-- Forum: HP Software Libraries (/forum-10.html)
+--- Forum: General Software Library (/forum-13.html)
+--- Thread: (16C) show which bits are set in a number (/thread-12550.html)

(16C) show which bits are set in a number - cdmackay - 03-04-2019 12:57 AM

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.

RE: (16C) show which bits are set in a number - Thomas Klemm - 03-04-2019 02:15 AM

(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

RE: (16C) show which bits are set in a number - cdmackay - 03-04-2019 04:02 PM

(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 Smile

thanks.

RE: (16C) show which bits are set in a number - Thomas Klemm - 03-04-2019 05:37 PM

(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

RE: (16C) show which bits are set in a number - cdmackay - 03-04-2019 06:42 PM

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 Smile

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 Smile

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.

RE: (16C) show which bits are set in a number - Thomas Klemm - 03-04-2019 08:22 PM

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

RE: (16C) show which bits are set in a number - cdmackay - 03-04-2019 10:35 PM

(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 Smile

thanks.

RE: (16C) show which bits are set in a number - wynen - 03-06-2019 09:41 AM

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

RE: (16C) show which bits are set in a number - Dieter - 03-06-2019 06:57 PM

(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

RE: (16C) show which bits are set in a number - wynen - 03-06-2019 10:16 PM

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

RE: (16C) show which bits are set in a number - Sylvain Cote - 03-07-2019 12:45 AM

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

Sylvain

RE: (16C) show which bits are set in a number - cdmackay - 03-07-2019 01:41 AM

(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…

RE: (16C) show which bits are set in a number - cdmackay - 03-07-2019 01:45 AM

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 Smile

RE: (16C) show which bits are set in a number - wynen - 03-07-2019 09:45 AM

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?

RE: (16C) show which bits are set in a number - cdmackay - 03-07-2019 08:31 PM

(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 Smile

thanks again.

RE: (16C) show which bits are set in a number - cdmackay - 03-30-2019 11:33 PM

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?

RE: (16C) show which bits are set in a number - cdmackay - 03-31-2019 02:40 PM

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

CLx
NOT
B#

that might be simpler still Smile