Bits of integer - Printable Version

Bits of integer - Printable Version

+- HP Forums (https://www.hpmuseum.org/forum)
+-- Forum: HP Calculators (and very old HP Computers) (/forum-3.html)
+--- Forum: General Forum (/forum-4.html)
+--- Thread: Bits of integer (/thread-19258.html)

Pages: 1 2 3

RE: Bits of integer - mfleming - 12-07-2022 09:48 PM

Just for fun, in APL

Code:

    numbits←{⍺←32 ⋄ ⌈/⍸⌽(⍺⍴2)⊤⍵}

    numbits 25

5

    64 numbits 2*32

33

LHS - Bit width of word holding binary equivalent of RHS value (default 32)

Expression evaluates right to left, modified by parentheses
Expression reads left to right:
Find the largest number in the vector indices of ones in the reversed binary representation of a RHS value. (The number of bits will the the index (OPTON BASE 1) of the one that's furthest to the right in the reversed binary vector of ones and zeros.)

We can use the commute operator to rid ourselves of the parentheses

Code:

    numbits2←{⍺←32 ⋄ ⌈/⍸⌽⍵⊤⍨⍺⍴2}

    128 numbits2 2*63

64

Fourteen characters, not counting spaces and braces Smile

~Mark

RE: Bits of integer - pinkman - 12-07-2022 10:13 PM

(12-07-2022 08:00 AM)Werner Wrote: Of course, calling the local variable 'SWAP' is meant to confuse the uninitiated!
But a marvel it is, indeed.
Cheers, Werner

Thanks! Without your comment I was a (16) bit puzzled…

RE: Bits of integer - J-F Garnier - 12-10-2022 09:31 AM

(12-07-2022 02:51 PM)Albert Chan Wrote: log2(2^n ± x) = n + log2(1 ± x/2^n) ≈ n ± x/2^n/ln(2)

--> bits(x) = IP(LOG2(x))+1 only work upto 2^35 - 2 = 34,359,738,366

Applying the same reasoning to the formula:
bits(x) = IP(LOG(x+0.5)/LOG(2))+1
for machines lacking the LOG2 function, we get that this formula works almost up to the same limit, 2^34 - 2.

Bottom line: the LOG2(n) and LOG(n+0.5)/LOG(2) methods work for 32-bit numbers on 12-digits machines.

J-F

RE: Bits of integer - John Keith - 12-11-2022 09:09 PM

For the RPL calculators, in BIN mode:

Code:

\<< R\->B \->STR SIZE 3 -

\>>

Accurate up to 10^12, or up to 2^63 on the 49g/50g with Joe Horn's I->B.

Joe Horn's STEP program listed above takes about 4 * as long but has no limit on size.

We can observe that as a sequence, the bit length is "n occurs 2^(n-1) times". If many values for small numbers are needed, the following program returns a list of the values from 1 to 2^n-1 given n on the stack. It is very fast. Requires HP-48G or newer.

Code:

\<< \-> n

  \<< { 1 } 2 n

    START DUP 1 ADD DUP +

    NEXT n \->LIST \GSLIST

  \>>

\>>

RE: Bits of integer - FLISZT - 12-12-2022 04:54 PM

… and still no solution for the hp-16C ?! Wink

You know, the calculator specially designed for computer scientists... (and of great value for calculator collectors).
Smile

RE: Bits of integer - cdmackay - 12-12-2022 07:28 PM

The 16C can tell you directly ["#B"] how many bits are set in a number, and I wrote something to show which bits they are, something I find useful at work. But that's not quite the same Smile

https://www.hpmuseum.org/forum/thread-12550.html

RE: Bits of integer - FLISZT - 12-12-2022 08:14 PM

(12-12-2022 07:28 PM)cdmackay Wrote: The 16C can tell you directly ["#B"] how many bits are set in a number, and I wrote something to show which bits they are, something I find useful at work. But that's not quite the same

https://www.hpmuseum.org/forum/thread-12550.html

That's not quite the same, but very interesting though!
Thank you! Smile

RE: Bits of integer - mfleming - 12-12-2022 10:07 PM

Why not switch to binary then shift-right until zero?

RE: Bits of integer - Joe Horn - 12-13-2022 02:37 AM

(12-12-2022 10:07 PM)mfleming Wrote: Why not switch to binary then shift-right until zero?

Here's a brute-force implementation of that method:

LBL A, 0, STO I, Rdn, LBL 0, g ISZ, f SR, g x≠0, GTO 0, RCL I, RTN

GSB A in any binary mode returns the number of bits needed to express X.

It works, but it's horrifically slow:
Input 2^40-1 outputs correct result of 40 in 15 seconds. Big Grin

Input 2^40 outputs correct result of 41 in 15 seconds. Big Grin

EDIT: 0 NOT with WSIZE of 64 returns 64 in 22 seconds.

RE: Bits of integer - Joe Horn - 12-13-2022 09:17 AM

(12-13-2022 02:37 AM)Joe Horn Wrote: Here's a brute-force implementation of that method...

Here's a 16C-only routine that doesn't require any looping. The LJ command is on the [g] [A] key. #B is on the [g] [7] key.

LJ, 0, NOT, #B, x<>y, –

As before, put any value in X in any binary mode. The above routine returns the number of bits required to express X. If WSIZE is sufficiently large to put X on the stack, then this routine will always return the correct answer.

Inputs of 2^40-1 and 2^40 return the correct answers (40 and 41 respectively) in roughly 1.5 seconds, with a speed hit for a large WSIZE.

RE: Bits of integer - mfleming - 12-13-2022 12:15 PM

Right tool for the right job...

RE: Bits of integer - Albert Chan - 12-14-2022 02:35 PM

(12-07-2022 09:48 PM)mfleming Wrote: Just for fun, in APL

Code:

numbits←{⍺←32 ⋄ ⌈/⍸⌽(⍺⍴2)⊤⍵} numbits 25 5 64 numbits 2*32 33

Thanks for APL code. I tried this in https://tryapl.org/. (my first APL session!)

It does not work if number more than 53 bits (I think numbers is binary64)
First example, 2^54-1 just round back to 2^54 (half-way to even).

Code:

      64 numbits (2*54)-1

55

      64 numbits (2*54)-2

54

RE: Bits of integer - Gjermund Skailand - 12-14-2022 09:47 PM

Here is a version for HP50G

"
* Number of bits necessary to represent
* an integer Z in binary
* unlimited size of Z.
* Z -> %

!RPL
!NO CODE
::
CK1NOLASTWD (check for at least one argument )
CK&DISPATCH0 ( check for Z integer )
#FF
::
TOTEMPOB
DUP Z0_ Z= casedrop %0 ( special check for 0 )
FPTR2 ^Z>ZH ( convert to hex string )
FPTR2 ^ZBits ( get number of bits )
SWAPDROP
UNCOERCE ( convert to real number )
;
;
@
"
compiles to 52 bytes,
checksum #2FA1h

or you can enter the following string,
attach development lib and run H->
"D9D2079262E136211920FF000D9D20
7566088130BA3721C562D5943739F2
CA6206004F00CA620600D010A12436
F262B2130B2130"
Do not include any space or carriage returns.
run
H-> DUP BYTES
check that size and checksum is correct
before running this code.
Br Gjermund

RE: Bits of integer - mfleming - 12-14-2022 11:16 PM

(12-14-2022 02:35 PM)Albert Chan Wrote: Thanks for APL code. I tried this in https://tryapl.org/. (my first APL session!)

It does not work if number more than 53 bits (I think numbers is binary64)
First example, 2^54-1 just round back to 2^54 (half-way to even).

I couldn't find specifics about integer representation in the language reference manual so I suppose it's platform-dependent. What's interesting is that the function is perfectly happy with floating point numbers.

Dyalog Ltd maintains the tryapl web site in addition to https://aplcart.info/ (look up problems, find APL solutions) and https://aplwiki.com/wiki/Main_Page (all about APL). Here's another version of numbits that shows tail recursion of dfns Smile

Code:

numbits←{⍺←1 ⋄ ⍵≤1:⍺ ⋄ (⍺+1)∇⌊⍵÷2}

The ≤ comparison is there to catch zero or negative values. Computation may be a little cheaper by replacing division with multiplication by 0.5.

Code:

numbits←{⍺←1 ⋄ ⍵≤1:⍺ ⋄ (⍺+1)∇⌊0.5×⍵}

Sadly, decades of procedural programming has left me barely able to grasp APL, but I keep trying (Engineer, not Mathematician) Sad

RE: Bits of integer - robve - 12-15-2022 02:07 AM

Not as nice (and cryptic) as APL:

In Forth we can use pictured numeric output to get the msb of the (typically double cell) value on the stack:
2 base ! <# #s #> nip

With Python we can use formatting to get the msb of n:
len("{0:b}".format(n))

C++20: with std::format
std::format("{0:b}", n).size()

- Rob

RE: Bits of integer - Albert Chan - 12-15-2022 06:08 AM

From https://aplcart.info/, I found a 7 characters solution to get numbits
How does it work ?

numbits ← ≢2∘⊥⍣¯1
numbits ¨⍳9
1 2 2 3 3 3 3 4 4

RE: Bits of integer - EdS2 - 12-15-2022 09:06 AM

How indeed...

Tally(monadic) Two Jot(dyadic) Up Tack (dyadic) Star Diaeresis(dyadic) Negative One

Vaguely speaking, it looks like Up Tack is there to decode (binary into a number) and Star Diaeresis(dyadic) Negative One is there to invert that function.

RE: Bits of integer - Albert Chan - 12-15-2022 12:29 PM

APL is confusing ... Reading comments here clear things up.
(⊥⍣¯1) should be read as 1 dyadic function.

      base ← ⊥⍣¯1

      2 base 123
1 1 1 1 0 1 1
      ≢ 2 base 123
7

4 characters APL code for base conversion ... amazing Smile

RE: Bits of integer - mfleming - 12-15-2022 12:59 PM

Argh! Trai.i.i.ins! My head hurts! Sad

Gotta love APL...

RE: Bits of integer - Thomas Klemm - 12-15-2022 04:08 PM

(12-15-2022 12:29 PM)Albert Chan Wrote: 4 characters APL code for base conversion ... amazing

Can we expect your explanations in APL instead of Lua from now on?