Bits of integer

[Albert Chan]

All codes (sorted from slowest to fastest) produced a sum of 388874.
All codes were run combined with below test codes.

Test Code 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

General binary search function turns out much slower, perhaps due to cost of array lookup.
But, binary search code might be useful for other applications, so I post it here.

Below, all timings done on Emu71/DOS WinXP (~ 200X speed)

Note: H=N+1 is an exclusive upper bound

Time = 18.6 seconds Wrote:15 N=39 @ DIM A(N) @ X=1 @ FOR I=1 TO N @ X=X+X @ A(I)=X @ NEXT I

100 DEF FNB(X) @ L=1 @ H=N+1
110 WHILE L<H @ M=IP((L+H)*.5) @ IF X<A(M) THEN H=M ELSE L=M+1
120 END WHILE @ FNB=L @ END DEF

With inclusive upper bound, binary search code look like this:

Code:

100 DEF FNB(X) @ L=1 @ H=N
110 WHILE L<=H @ M=IP((L+H)*.5) @ IF X<A(M) THEN H=M-1 ELSE L=M+1
120 END WHILE @ FNB=L @ END DEF

Avoiding array lookup, even with slow DIV, binary search is faster.

Time = 9.97 seconds Wrote:100 DEF FNB(X) @ B=1
110 IF X>=4294967296 THEN X=X DIV 4294967296 @ B=B+32
120 IF X>=65536 THEN X=X DIV 65536 @ B=B+16
130 IF X>=256 THEN X=X DIV 256 @ B=B+8
140 IF X>=16 THEN X=X DIV 16 @ B=B+4
150 FNB=B+(X>=2)+(X>=4)+(X>=8)
160 END DEF

Hard-coded binary search without DIV is possible, but messy, with many branches.
To give an idea of timing, I did a linear search for hex digit, then zero-in to bits.

Time = 8.25 seconds Wrote:100 DEF FNB(X) @ SELECT X
110 CASE >=68719476736 @ FNB=37+(X>=137438953472)+(X>=274877906944)+(X>=549755813888)
120 CASE >=4294967296 @ FNB=33+(X>=8589934592)+(X>=17179869184)+(X>=34359738368)
130 CASE >=268435456 @ FNB=29+(X>=536870912)+(X>=1073741824)+(X>=2147483648)
140 CASE >=16777216 @ FNB=25+(X>=33554432)+(X>=67108864)+(X>=134217728)
150 CASE >=1048576 @ FNB=21+(X>=2097152)+(X>=4194304)+(X>=8388608)
160 CASE >=65536 @ FNB=17+(X>=131072)+(X>=262144)+(X>=524288)
170 CASE >=4096 @ FNB=13+(X>=8192)+(X>=16384)+(X>=32768)
180 CASE >=256 @ FNB=9+(X>=512)+(X>=1024)+(X>=2048)
190 CASE >=16 @ FNB=5+(X>=32)+(X>=64)+(X>=128)
200 CASE ELSE @ FNB=1+(X>=2)+(X>=4)+(X>=8)
210 END SELECT @ END DEF

J-F Garnier code, limit size of LOG2 argument.

Time = 7.72 seconds Wrote:100 DEF FNB(X)
110 IF X<1048576 THEN FNB=IP(LOG2(X))+1 ELSE FNB=IP(LOG2(X DIV 1048576))+21
120 END DEF

J-F Garnier code, binary string length, fastest of them all! Thanks!

Time = 5.81 seconds Wrote:100 DEF FNB(N)=LEN(BSTR$(N,2))