Find first and last set bit of a long integer: Difference between revisions

''Clarification: This task is asking for the position of two bits in the binary representation of a positive integer. Some parts of this task assume that this is the native representation in the language you are working in. Any part of this task which makes assumptions about native representation should be treated as a recommendation which is only relevant in some contexts. A bit is defined as the exponent in a binary polynomial -- an exponent corresponding to a power of 2 which has a non-zero multiplier in the summation sequence of powers of two which yields the desired positive integer, where the only allowed coefficients are 0 and 1.''

 

Use primarily '''bit''' operations, such as '''and''', '''or''', and bit shifting. Avoid additions, multiplications and especially avoid divisions.

 

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

 

# For the host machine word size: Use the powers of 42 up to host's the "natural" word size to calculate the index of the first and last set bit.

# For the extended precision: Use the powers of 1302 up to the host's next "natural" '''long''' host ''word'' size to calculate the index of the first and last set bit.

# Output bit indexes in [[wp:Bit_numbering#LSB_0_bit_numbering|LSB 0 bit numbering]].

 

 

In a particular language, there maybe (at least) two alternative approaches of calculating the required values:

* Using an external library.

* Using a built-in library.

If any of these approaches are available, then ''also'' note the library or built-in name.

 

* [http://graphics.stanford.edu/~seander/bithacks.html#IntegerLog Find the log base 2 of an N-bit integer in O(lg(N)) operations]

* [http://pdos.csail.mit.edu/6.858/2011/readings/i386/BSF.htm 80386 Instruction Set - BSF -- Bit Scan Forward]

 

=={{header|ALGOL 68}}==