Bits of integer

[robve]

(12-06-2022 06:49 PM)Albert Chan Wrote:  All codes (sorted from slowest to fastest) produced a sum of 388874.
All codes were run combined with below test codes.

Very nice. But you can avoid divisions (right shifts) solely by using multiplications (left shifts). Do you see what I mean and how to do that?

Also, in general, to find the leading bit in a n-bit binary number is asymptotically faster with binary search taking O(log(n)) asymptotic execution time as opposed to producing a string of 1 to n bits, which takes O(n) time.

The (im)practical aspects of the HP-71B makes binary search slow. Its BASIC is not suitable for this approach, especially when using costly divisions. Using hard coded branches and complicated expressions isn't helping performance either.

(12-06-2022 12:15 AM)Albert Chan Wrote:  Hi, robve
[...]
It would be nice if HP71B has built-in binary search code.
Getting it right is hard.
Are you one of the 10% of programmers who can write a binary search?
Binary Search and Exclusive Upper Bounds

The bit-shift binary search has no issues with edge cases, since we're dealing with integers of 32 bit (or 8, 16, 32, 64 bit for that matter, with a tweak to the code):
1: 0
2: 1
3: 1
4: 2
5: 2
6: 2
7: 2
8: 3
9: 3
10: 3
11: 3
12: 3
13: 3
14: 3
15: 3
16: 4
17: 4
...
511: 8
512: 9
...
4294967292: 31
4294967293: 31
4294967294: 31
4294967295: 31

Sure works like a charm. I like it because the underlying machine code is simple and efficient.

- Rob