combinations of k bits wp34s



#2

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.


#3

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


#4

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

[<->] XYLX

Cheers

Thomas


#5

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


#6

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:-)


#7

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


#8

This is a bug. Soon to be fixed.


- Pauli

#9

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


- Pauli

#10

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.


#11

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

- Pauli

#12

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.


#13

The book you want is

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

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


Possibly Related Threads…
Thread Author Replies Views Last Post
  Prime Program number of set bits kris223 3 1,963 10-23-2013, 03:05 PM
Last Post: David Hayden
  [WP34S] WP34S firmware on the AT91SAM7L-STK dev kit? jerome ibanes 1 1,247 10-04-2012, 04:59 PM
Last Post: Paul Dale
  Question about a "combinations" algorithm Namir 9 2,633 09-20-2012, 04:51 PM
Last Post: Gilles Carpentier
  [wp34s] Incomplete Gamma on the wp34s Les Wright 18 5,347 12-06-2011, 11:07 AM
Last Post: Namir
  [wp34s] Romberg Integration on the wp34s Les Wright 2 1,519 12-04-2011, 10:49 PM
Last Post: Les Wright
  Challenge: Mirror bits Geir Isene 27 6,148 12-23-2008, 10:28 AM
Last Post: dbatiz
  HP-15C Mini-Challenge: Bits o'Pi Valentin Albillo 67 13,168 03-24-2007, 03:57 PM
Last Post: Karl Schneider
  Mini-Challenge: Twiddling the bits Valentin Albillo 30 6,552 06-27-2006, 12:02 AM
Last Post: Karl Schneider
  HP-71B - HP-41 Translator Bits? Howard Owen 19 4,566 09-13-2005, 07:04 PM
Last Post: Eric Smith
  hp49g+ bug? Combinations, sums, and equivalence Eddie Shore 6 1,738 03-15-2005, 07:56 AM
Last Post: Veli-Pekka Nousiainen

Forum Jump: