Prime Program number of set bits - Printable Version +- HP Forums ( https://archived.hpcalc.org/museumforum)+-- Forum: HP Museum Forums ( https://archived.hpcalc.org/museumforum/forum-1.html)+--- Forum: Old HP Forum Archives ( https://archived.hpcalc.org/museumforum/forum-2.html)+--- Thread: Prime Program number of set bits ( /thread-253543.html) |

Prime Program number of set bits - kris223 - 10-22-2013
Hello, I thought I'd share a simple program to determine the number of set bits in a base ten number. This is useful to me as I need to group numbers based on the number of ones in them for the Quine-McCluskey method of reducing Boolean functions. Although one can do 4 bit numbers in one's head easily, its nice to double check quickly and if a 5 bit number is needed it could be more helpful then. I may continue with the idea and try to program the whole method. Anyway, it was fun to do.
EXPORT numSetBits(n)
Note: "→" is actually "->" as in R->B(n);Enter a number onto the stack and execute the program and it will return the number of ones in the binary value.
15 #15d = #1111b ... 4 ones #6d = #110b ... 2 ones If anyone sees some improvements I could make, please let me know as I'm new to Prime programming.
Re: Prime Program number of set bits - Joe Horn - 10-22-2013
Can't help with programming, but here are two ideas regarding counting how many 1's are in the binary form of an integer x. Method 1: hamdist(x,0) This only works for small numbers, < 2^30, roughly 9 decimal digits. But it's a single fast command, which is cool. Method 2: SigmaLIST(convert(x,base,2)) This only works in CAS. Replace "Sigma" with the Sigma character of course, and be sure to type "convert" in lowercase or it won't work (unfortunately the Toolbox Catalog echoes it in uppercase). This method works for any exact CAS integer that Prime can handle (7999 bits, roughly 2048 decimal digits). Using this method, the emulator takes 0.83 seconds to count all 7998 1's in 2^7998-1 on my laptop.
-Joe-
Re: Prime Program number of set bits - kris223 - 10-22-2013
I really like hamming distance. Who would of thought? I need to learn more about the function available on the calc. Thanks!
Re: Prime Program number of set bits - David Hayden - 10-23-2013
There's a very fast algorithm for counting the number of bits. Suppose you have a 32 bit binary number n where each 16-bit half contains the number of bits that your starting number had in each half. You can add these two numbers together with: tmp := BITSR(n,16);
In a similar way, if n contains 4 fields of 8 bits each, you can add combine adjacent fields to form two 16 bit fields like this: tmp := BITSR(n, 8);
The idea can be extended all the way down to 1-bit fields. So the code to count the bits is: EXPORT numsetbits(n) |