Bits of integer

[mfleming]

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
~Mark

[pinkman]

(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…

[J-F Garnier]

(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

[John Keith]

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
  \>>
\>>

[FLISZT]

… and still no solution for the hp-16C ?!
You know, the calculator specially designed for computer scientists... (and of great value for calculator collectors).

[cdmackay]

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

[FLISZT]

(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!

[mfleming]

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

[Joe Horn]

(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.
Input 2^40 outputs correct result of 41 in 15 seconds.

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

[Joe Horn]

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

[mfleming]

Right tool for the right job...

[Albert Chan]

(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

[Gjermund Skailand]

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

[mfleming]

(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

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)

[robve]

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

[Albert Chan]

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

[EdS2]

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.

[Albert Chan]

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

[mfleming]

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

Gotta love APL...

[Thomas Klemm]

(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?