The Museum of HP Calculators

HP Forum Archive 21

[ Return to Index | Top of Index ]

combinations of k bits wp34s
Message #1 Posted by Andrew Nikitin on 24 Aug 2013, 12:51 a.m.

The bitwise operations on a calculator is surprisingly fun.

// If input word contains k bits, then the result is next word 
// containing k bits
// Must be in integer (binary?) mode
// Start with MASKR k
  LBL'NXC'
    RCL X
    +/-
    RCL Y
    AND
    RCL+ Y
    RCL L
    RCL Z
    RCL Z
    NOT
    AND
    x[<->] Y
    /
    SR 01
    +
    RTN

I would love to hear stories about using them (bitwise operations) in realistic problems.

      
Re: combinations of k bits wp34s
Message #2 Posted by Paul Dale on 24 Aug 2013, 1:08 a.m.,
in response to message #1 by Andrew Nikitin

Nice program, one of the few I've seen so far that use integer mode. You might need to specify the integer sign mode though.

Also, the shuffle [<->] command would save a couple of steps I think.

- Pauli

            
Re: combinations of k bits wp34s
Message #3 Posted by Thomas Klemm on 24 Aug 2013, 6:38 a.m.,
in response to message #2 by Paul Dale

Is there a reason why the use of L is not supported as in: 

[<->] XYLX

Cheers
Thomas

                  
Re: combinations of k bits wp34s
Message #4 Posted by Paul Dale on 24 Aug 2013, 7:54 a.m.,
in response to message #3 by Thomas Klemm

Blame Walter :-) The shuffle command originally accepted five registers and L was permitted in any position, then it was removed and later reinstated in its current form after much discussion and finally the keyboard and display code was added.

Allowing the fifth register was an unnecessary complication and the current form fits the opcode layout a lot better.

- Pauli

                        
Re: combinations of k bits wp34s
Message #5 Posted by Walter B on 24 Aug 2013, 10:28 a.m.,
in response to message #4 by Paul Dale

I don't remember the L-part of that discussion ;-) One could ask, however, why that command doesn't allow for shuffling A, B, C, and D as well to generate maximum confusion. Luckily, we don't have sufficient op-codes left. Anyway, enough potential to create a big mess on the stack.

d:-)

                              
Re: combinations of k bits wp34s
Message #6 Posted by Thomas Klemm on 24 Aug 2013, 3:35 p.m.,
in response to message #5 by Walter B

It was confusing that the letter L was accepted but instead Y is used. The same happens for A, B, C, D and J, K. This might be a remainder of this discussion?

Cheers
Thomas

                                    
Re: combinations of k bits wp34s
Message #7 Posted by Paul Dale on 24 Aug 2013, 8:46 p.m.,
in response to message #6 by Thomas Klemm

This is a bug. Soon to be fixed.

- Pauli

                              
Re: combinations of k bits wp34s
Message #8 Posted by Paul Dale on 24 Aug 2013, 8:47 p.m.,
in response to message #5 by Walter B

The L part was very very early on before the command was dropped.

- Pauli

      
Re: combinations of k bits wp34s
Message #9 Posted by Didier Lachieze on 25 Aug 2013, 6:11 p.m.,
in response to message #1 by Andrew Nikitin

Very nice program! Here is a slightly more compact version (3 steps less):

  LBL'NXC'
    FILL
    +/-
    AND
    STO T
    +
    STO Z
    NOT
    AND
    RCL/ Z
    SR 01
    +
    RTN

Btw I would be interested by a detailed explanation of how you found this formula.

Edited: 25 Aug 2013, 6:22 p.m.

            
Re: combinations of k bits wp34s
Message #10 Posted by Paul Dale on 25 Aug 2013, 6:39 p.m.,
in response to message #9 by Didier Lachieze

I found this pretty quickly, although it doesn't appear to be exactly the same algorithm, it is pretty well explained.

- Pauli

            
Re: combinations of k bits wp34s
Message #11 Posted by Andrew Nikitin on 25 Aug 2013, 10:20 p.m.,
in response to message #9 by Didier Lachieze

I once read a book about combinatorial algorithms. From there I learned a trick: x&(-x) leaves the lowest set bit in x. I do not remember the exact details, but it dawned on me that I can use that to implement standard "next combination" generation algorithm (locate rightmost group of consecutive ones, in that group move leftmost bit one step left, move others all the way to the right) entirely in mix of bitwise/arithmetic operations. Turned out, you do not even need too many.

Edited: 25 Aug 2013, 10:24 p.m.

                  
Re: combinations of k bits wp34s
Message #12 Posted by mjcohen on 2 Sept 2013, 7:32 p.m.,
in response to message #11 by Andrew Nikitin

The book you want is

Hacker's Delight (2nd Edition) by Henry S. Warren.

It's even available in a Kindle edition for $26.

[ Return to Index | Top of Index ]

Go back to the main exhibit hall