Find first and last set bit of a long integer
Define routines (or operators) lwb and upb that find the first and last set bit in a binary value. Implement using a binary search to find the location of the particular upper/lower bit.
Find first and last set bit of a long integer is a draft programming task. It is not yet considered ready to be promoted as a complete task, for reasons that should be found in its talk page.
Use primarily bit operations, such as and, or, and bit shifting. Avoid additions, multiplications and especially avoid divisions.
Two implementations:
- For the host word size on the host platform, implement the routine "efficiently" in without looping or recursion.
- For the extended precision/long word implement the algorithm more generally - maybe as a template, and maybe with looping - so that any bits width for a binary type can be accommodated.
Test cases:
- For typical word size: Use the powers of 42 up to the word side to calculate the location of the first and last set bit.
- For the extended precision: Use the powers of 1302 up to 128 bits to calculate the location of the first and last set bit.
Additionally:
In the particular language there maybe (at least) two alternative approaches of calculating the required values:
- Using an external library.
- Using a built-in library.
If one of these approaches are available, then also note the library or built-in name.
See also: