Bits of integer

[Albert Chan]

(12-06-2022 07:26 PM)robve Wrote:  Very nice. But you can avoid divisions (right shifts) solely by using multiplications (left shifts).

Yes, it can be done this way too.

The problem is, for HP71B, *both* multiply and divide are costly.
Divide a bit worse, but it is in the same ballpark.

Programming in interpreted BASIC is very different than compiled languages.

Also, pow-of-2 and pow-of-10 numbers never match (except for 2^0 = 10^0 = 1)
This required an extra step to correct for the boundary. (bolded line)

Below could optimize a bit, but likely still slower than binary search with DIV (9.97 seconds)

Time = 11.55 seconds Wrote:10 DESTROY ALL @ RANDOMIZE 1 @ T=0 @ SETTIME 0
20 FOR I=1 TO 10000 @ T=T+FNB(IP(RND*999999999999)+1) @ NEXT I
30 DISP T,TIME

100 DEF FNB(X) @ B=40 ! FNB(x >= 2^39) assumed 40
110 Y=X*4294967296 @ IF Y<1E12 THEN X=Y @ B=B-32
120 Y=X*65536 @ IF Y<1E12 THEN X=Y @ B=B-16
130 Y=X*256 @ IF Y<1E12 THEN X=Y @ B=B-8
140 Y=X*16 @ IF Y<1E12 THEN X=Y @ B=B-4
150 Y=X*4 @ IF Y<1E12 THEN X=Y @ B=B-2
160 Y=X*2 @ IF Y<1E12 THEN X=Y @ B=B-1
170 FNB=B-(X<549755813888)
180 END DEF