Post Reply 
Bits of integer
12-05-2022, 10:06 PM (This post was last modified: 12-06-2022 02:50 AM by robve.)
Post: #6
RE: Bits of integer
(12-05-2022 12:12 PM)Albert Chan Wrote:  This was a PM that I thought wothy of starting a thread: Number of Bits in a Integer

Albert Chan Wrote:Unless you have correct implementation of log2 (or binary logb), do this instead:

It seems it is harder than it look, even with "perfect" log2

>20 def FNB(N) = IP(LOG2(N))+1
>X = 2^35
>X, FNB(X-1), FNB(X), FNB(X+1)
 34359738368      36      36      36

For binary machine, code is trivial, bit_length(x) = logb(x) + 1

For decimal machine, we may be hit with rounding errors. Any ideas ?

For C (and lua etc) I came up with a simple binary search to find the position of the leading bit in a 32 bit integer in 5 search steps:

Code:
  unsigned int n, k, v = <number>;
  k = -!!(v >> 16) & 16;
  n = k;
  v >>= k;
  k = -!!(v >> 8) & 8;
  n += k;
  v >>= k;
  k = -!!(v >> 4) & 4;
  n += k;
  v >>= k;
  k = -!!(v >> 2) & 2;
  n += k;
  v >>= k;
  k = -!!(v >> 1) & 1;
  n += k;
  v >>= k;

It's fast in C, since the compiled code operates with a few registers using bit-wise operations. But on the HP-71B we will need to shift with integer division and integer multiplication. Forth has shift words.

Another trick is to normalize the integer to a clean form before taking the log2, similar to this:

Code:
x |= (x >> 1);
x |= (x >> 2);
x |= (x >> 4);
x |= (x >> 8);
x |= (x >> 16);
n = log2(x & ~(x >> 1)));

As a side note, the LZCNT CPU instruction counts leading zeros and can be used in e.g. C/C++ with __builtin_clz(). The POPCNT CPU instruction counts the number of nonzero bits. That neither work with a HP-71B of course.

- Rob

"I count on old friends" -- HP 71B,Prime|Ti VOY200,Nspire CXII CAS|Casio fx-CG50...|Sharp PC-G850,E500,2500,1500,14xx,13xx,12xx...
Visit this user's website Find all posts by this user
Quote this message in a reply
Post Reply 


Messages In This Thread
Bits of integer - Albert Chan - 12-05-2022, 12:12 PM
RE: Bits of integer - Werner - 12-05-2022, 12:41 PM
RE: Bits of integer - J-F Garnier - 12-05-2022, 02:55 PM
RE: Bits of integer - Albert Chan - 12-05-2022, 04:13 PM
RE: Bits of integer - Valentin Albillo - 12-05-2022, 04:29 PM
RE: Bits of integer - J-F Garnier - 12-06-2022, 08:29 AM
RE: Bits of integer - robve - 12-05-2022 10:06 PM
RE: Bits of integer - Albert Chan - 12-06-2022, 12:15 AM
RE: Bits of integer - John Keith - 12-06-2022, 07:15 PM
RE: Bits of integer - robve - 12-06-2022, 08:15 PM
RE: Bits of integer - Thomas Klemm - 12-06-2022, 07:41 AM
RE: Bits of integer - Albert Chan - 12-06-2022, 06:49 PM
RE: Bits of integer - robve - 12-06-2022, 07:26 PM
RE: Bits of integer - Albert Chan - 12-06-2022, 09:34 PM
RE: Bits of integer - FLISZT - 12-07-2022, 12:52 AM
RE: Bits of integer - Paul Dale - 12-07-2022, 06:33 AM
RE: Bits of integer - J-F Garnier - 12-07-2022, 08:41 AM
RE: Bits of integer - Albert Chan - 12-07-2022, 02:51 PM
RE: Bits of integer - J-F Garnier - 12-10-2022, 09:31 AM
RE: Bits of integer - Joe Horn - 12-07-2022, 07:18 AM
RE: Bits of integer - Werner - 12-07-2022, 08:00 AM
RE: Bits of integer - pinkman - 12-07-2022, 10:13 PM
RE: Bits of integer - mfleming - 12-07-2022, 09:48 PM
RE: Bits of integer - John Keith - 12-11-2022, 09:09 PM
RE: Bits of integer - FLISZT - 12-12-2022, 04:54 PM
RE: Bits of integer - cdmackay - 12-12-2022, 07:28 PM
RE: Bits of integer - FLISZT - 12-12-2022, 08:14 PM
RE: Bits of integer - mfleming - 12-12-2022, 10:07 PM
RE: Bits of integer - Joe Horn - 12-13-2022, 02:37 AM
RE: Bits of integer - Joe Horn - 12-13-2022, 09:17 AM
RE: Bits of integer - mfleming - 12-13-2022, 12:15 PM
RE: Bits of integer - Albert Chan - 12-14-2022, 02:35 PM
RE: Bits of integer - mfleming - 12-14-2022, 11:16 PM
RE: Bits of integer - Gjermund Skailand - 12-14-2022, 09:47 PM
RE: Bits of integer - robve - 12-15-2022, 02:07 AM
RE: Bits of integer - Albert Chan - 12-15-2022, 06:08 AM
RE: Bits of integer - EdS2 - 12-15-2022, 09:06 AM
RE: Bits of integer - Albert Chan - 12-15-2022, 12:29 PM
RE: Bits of integer - mfleming - 12-15-2022, 12:59 PM
RE: Bits of integer - Thomas Klemm - 12-15-2022, 04:08 PM
RE: Bits of integer - Albert Chan - 12-15-2022, 07:44 PM
RE: Bits of integer - FLISZT - 12-17-2022, 02:31 AM



User(s) browsing this thread: 1 Guest(s)