The following warnings occurred:
Warning [2] Undefined array key 253543 - Line: 275 - File: inc/plugins/threaded_mode.php PHP 8.1.2-1ubuntu2.14 (Linux)
File Line Function
/inc/class_error.php 153 errorHandler->error
/inc/plugins/threaded_mode.php 275 errorHandler->error_callback
/inc/plugins/threaded_mode.php 23 ThreadedMode::showthread_threaded
/inc/class_plugins.php 142 threaded_mode_showthread_threaded
/showthread.php 918 pluginSystem->run_hooks
Warning [2] Undefined array key 253628 - Line: 275 - File: inc/plugins/threaded_mode.php PHP 8.1.2-1ubuntu2.14 (Linux)
File Line Function
/inc/class_error.php 153 errorHandler->error
/inc/plugins/threaded_mode.php 275 errorHandler->error_callback
/inc/plugins/threaded_mode.php 23 ThreadedMode::showthread_threaded
/inc/class_plugins.php 142 threaded_mode_showthread_threaded
/showthread.php 918 pluginSystem->run_hooks
Warning [2] Undefined array key 253644 - Line: 275 - File: inc/plugins/threaded_mode.php PHP 8.1.2-1ubuntu2.14 (Linux)
File Line Function
/inc/class_error.php 153 errorHandler->error
/inc/plugins/threaded_mode.php 275 errorHandler->error_callback
/inc/plugins/threaded_mode.php 23 ThreadedMode::showthread_threaded
/inc/class_plugins.php 142 threaded_mode_showthread_threaded
/showthread.php 918 pluginSystem->run_hooks
Warning [2] Undefined array key 253714 - Line: 275 - File: inc/plugins/threaded_mode.php PHP 8.1.2-1ubuntu2.14 (Linux)
File Line Function
/inc/class_error.php 153 errorHandler->error
/inc/plugins/threaded_mode.php 275 errorHandler->error_callback
/inc/plugins/threaded_mode.php 23 ThreadedMode::showthread_threaded
/inc/class_plugins.php 142 threaded_mode_showthread_threaded
/showthread.php 918 pluginSystem->run_hooks
Warning [2] Undefined variable $thread - Line: 295 - File: inc/plugins/threaded_mode.php PHP 8.1.2-1ubuntu2.14 (Linux)
File Line Function
/inc/class_error.php 153 errorHandler->error
/inc/plugins/threaded_mode.php 295 errorHandler->error_callback
/inc/plugins/threaded_mode.php 23 ThreadedMode::showthread_threaded
/inc/class_plugins.php 142 threaded_mode_showthread_threaded
/showthread.php 918 pluginSystem->run_hooks
Warning [2] Trying to access array offset on value of type null - Line: 295 - File: inc/plugins/threaded_mode.php PHP 8.1.2-1ubuntu2.14 (Linux)
File Line Function
/inc/class_error.php 153 errorHandler->error
/inc/plugins/threaded_mode.php 295 errorHandler->error_callback
/inc/plugins/threaded_mode.php 23 ThreadedMode::showthread_threaded
/inc/class_plugins.php 142 threaded_mode_showthread_threaded
/showthread.php 918 pluginSystem->run_hooks
Warning [2] Undefined variable $fid - Line: 295 - File: inc/plugins/threaded_mode.php PHP 8.1.2-1ubuntu2.14 (Linux)
File Line Function
/inc/class_error.php 153 errorHandler->error
/inc/plugins/threaded_mode.php 295 errorHandler->error_callback
/inc/plugins/threaded_mode.php 23 ThreadedMode::showthread_threaded
/inc/class_plugins.php 142 threaded_mode_showthread_threaded
/showthread.php 918 pluginSystem->run_hooks
Warning [2] Undefined array key 253644 - Line: 331 - File: inc/plugins/threaded_mode.php PHP 8.1.2-1ubuntu2.14 (Linux)
File Line Function
/inc/class_error.php 153 errorHandler->error
/inc/plugins/threaded_mode.php 331 errorHandler->error_callback
/inc/plugins/threaded_mode.php 332 ThreadedMode::buildtree
/inc/plugins/threaded_mode.php 332 ThreadedMode::buildtree
/inc/plugins/threaded_mode.php 304 ThreadedMode::buildtree
/inc/plugins/threaded_mode.php 23 ThreadedMode::showthread_threaded
/inc/class_plugins.php 142 threaded_mode_showthread_threaded
/showthread.php 918 pluginSystem->run_hooks
Warning [2] Undefined array key 253714 - Line: 331 - File: inc/plugins/threaded_mode.php PHP 8.1.2-1ubuntu2.14 (Linux)
File Line Function
/inc/class_error.php 153 errorHandler->error
/inc/plugins/threaded_mode.php 331 errorHandler->error_callback
/inc/plugins/threaded_mode.php 332 ThreadedMode::buildtree
/inc/plugins/threaded_mode.php 304 ThreadedMode::buildtree
/inc/plugins/threaded_mode.php 23 ThreadedMode::showthread_threaded
/inc/class_plugins.php 142 threaded_mode_showthread_threaded
/showthread.php 918 pluginSystem->run_hooks
Warning [2] Undefined variable $theme - Line: 3 - File: inc/plugins/threaded_mode.php(305) : eval()'d code PHP 8.1.2-1ubuntu2.14 (Linux)
File Line Function
/inc/class_error.php 153 errorHandler->error
/inc/plugins/threaded_mode.php(305) : eval()'d code 3 errorHandler->error_callback
/inc/plugins/threaded_mode.php 305 eval
/inc/plugins/threaded_mode.php 23 ThreadedMode::showthread_threaded
/inc/class_plugins.php 142 threaded_mode_showthread_threaded
/showthread.php 918 pluginSystem->run_hooks
Warning [2] Trying to access array offset on value of type null - Line: 3 - File: inc/plugins/threaded_mode.php(305) : eval()'d code PHP 8.1.2-1ubuntu2.14 (Linux)
File Line Function
/inc/class_error.php 153 errorHandler->error
/inc/plugins/threaded_mode.php(305) : eval()'d code 3 errorHandler->error_callback
/inc/plugins/threaded_mode.php 305 eval
/inc/plugins/threaded_mode.php 23 ThreadedMode::showthread_threaded
/inc/class_plugins.php 142 threaded_mode_showthread_threaded
/showthread.php 918 pluginSystem->run_hooks
Warning [2] Undefined variable $theme - Line: 3 - File: inc/plugins/threaded_mode.php(305) : eval()'d code PHP 8.1.2-1ubuntu2.14 (Linux)
File Line Function
/inc/class_error.php 153 errorHandler->error
/inc/plugins/threaded_mode.php(305) : eval()'d code 3 errorHandler->error_callback
/inc/plugins/threaded_mode.php 305 eval
/inc/plugins/threaded_mode.php 23 ThreadedMode::showthread_threaded
/inc/class_plugins.php 142 threaded_mode_showthread_threaded
/showthread.php 918 pluginSystem->run_hooks
Warning [2] Trying to access array offset on value of type null - Line: 3 - File: inc/plugins/threaded_mode.php(305) : eval()'d code PHP 8.1.2-1ubuntu2.14 (Linux)
File Line Function
/inc/class_error.php 153 errorHandler->error
/inc/plugins/threaded_mode.php(305) : eval()'d code 3 errorHandler->error_callback
/inc/plugins/threaded_mode.php 305 eval
/inc/plugins/threaded_mode.php 23 ThreadedMode::showthread_threaded
/inc/class_plugins.php 142 threaded_mode_showthread_threaded
/showthread.php 918 pluginSystem->run_hooks
Warning [2] Undefined variable $lang - Line: 5 - File: inc/plugins/threaded_mode.php(305) : eval()'d code PHP 8.1.2-1ubuntu2.14 (Linux)
File Line Function
/inc/class_error.php 153 errorHandler->error
/inc/plugins/threaded_mode.php(305) : eval()'d code 5 errorHandler->error_callback
/inc/plugins/threaded_mode.php 305 eval
/inc/plugins/threaded_mode.php 23 ThreadedMode::showthread_threaded
/inc/class_plugins.php 142 threaded_mode_showthread_threaded
/showthread.php 918 pluginSystem->run_hooks
Warning [2] Attempt to read property "messages_in_thread" on null - Line: 5 - File: inc/plugins/threaded_mode.php(305) : eval()'d code PHP 8.1.2-1ubuntu2.14 (Linux)
File Line Function
/inc/class_error.php 153 errorHandler->error
/inc/plugins/threaded_mode.php(305) : eval()'d code 5 errorHandler->error_callback
/inc/plugins/threaded_mode.php 305 eval
/inc/plugins/threaded_mode.php 23 ThreadedMode::showthread_threaded
/inc/class_plugins.php 142 threaded_mode_showthread_threaded
/showthread.php 918 pluginSystem->run_hooks





Prime Program number of set bits



#5

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)
// Oct 2013
// return the number of ones in n
BEGIN
LOCAL i := 0; //index of ones
LOCAL defB := Base; //save default base
LOCAL binB := 0; //binary base
LOCAL bVal := 0; //conversion to binary

Base := binB;
bVal := R→B(n);

WHILE bVal≠0 DO
i:=i+1;
bVal:= bVal AND bVal-#1b;
END;

//set default base to original val
Base := defB;

RETURN i;
END;

Note:
I don't know how to format the following text here ...

"→" is actually "->" as in R->B(n);

"≠" is actually the "does not equal" symbol. (bVal!=0 doesn't work either one must use the Prime key it seems)

Enter a number onto the stack and execute the program and it will return the number of ones in the binary value.

15
ENTER
numSetBits()
ENTER
4
6
ENTER
numSetBits()
ENTER
2

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


Edited: 22 Oct 2013, 1:53 a.m.


#6

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-


#7

I really like hamming distance. Who would of thought? I need to learn more about the function available on the calc. Thanks!

#8

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);
n := BITAND(n, #0000FFFFh);
tmp := BITAND(tmp, #0000FFFFh);
n := n + tmp;
return n;

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);
n := BITAND(n, #00FF00FFh);
tmp := BITAND(tmp, #00FF00FFh);
n := n + tmp;

The idea can be extended all the way down to 1-bit fields. So the code to count the bits is:

EXPORT numsetbits(n)
BEGIN
LOCAL tmp;

tmp := BITSR(n);

n := BITAND(n, #55555555h);
tmp := BITAND(tmp, #55555555h);
n := n + tmp;

// n is now broken into fields of 2 bits
// each. Each field contains the number of
// bits that were set in it.

tmp := BITSR(n, 2);
n := BITAND(n, #33333333h);
tmp := BITAND(tmp, #33333333h);
n := n + tmp;

// now each field is 4 bits wide
tmp := BITSR(n, 4);
n := BITAND(n, #0F0F0F0Fh);
tmp := BITAND(tmp, #0F0F0F0Fh);
n := n + tmp;

// Fields are now 8 bits

tmp := BITSR(n, 8);
n := BITAND(n, #00FF00FFh);
tmp := BITAND(tmp, #00FF00FFh);
n := n + tmp;

tmp := BITSR(n,16);
n := BITAND(n, #0000FFFFh);
tmp := BITAND(tmp, #0000FFFFh);
n := n + tmp;
return n;
END;


Possibly Related Threads…
Thread Author Replies Views Last Post
  Sending little images to the Prime (...and Program name bug?) Erwin Ried 19 7,136 12-10-2013, 05:35 PM
Last Post: Erwin Ried
  Problem with debug HP prime program, somebody help me? Carlos CM (Mexico) 6 3,216 12-05-2013, 03:07 PM
Last Post: Carlos CM (Mexico)
  HP PRIME: APP program code DISAPPEARS !! Joseph Ec 0 1,166 11-25-2013, 11:35 AM
Last Post: Joseph Ec
  A fast Bernoulli Number method for the HP Prime Namir 16 5,346 11-22-2013, 04:46 PM
Last Post: Namir
  Prime: Placing more than 1 item on the RPN stack in a single program? John Colvin 4 2,198 11-19-2013, 08:59 AM
Last Post: Miguel Toro
  Prime: Program size limited to 64K? Erwin Ried 4 1,979 11-17-2013, 11:42 PM
Last Post: Joseph Ec
  Complex Number Entry on Prime Jeff O. 19 4,952 11-16-2013, 12:34 PM
Last Post: Jeff O.
  [HP-Prime] Picking elements from a List in a program Jean-Michel 3 1,920 11-15-2013, 04:16 AM
Last Post: dg1969
  HP Prime: Recommendation for future RPN Program Mode BruceTTT 3 2,091 11-13-2013, 10:03 PM
Last Post: BruceTTT
  [HP Prime] Calculating Prandtl Number with Units (bug found in USIMPLIFY) Timothy Roche 1 1,320 11-13-2013, 04:07 PM
Last Post: cyrille de Brébisson

Forum Jump: