Re: [CHALLENGE] finding rightmost zero bit



Bart Vandewoestyne wrote: 
On 2005-08-29, Michel OLAGNON <molagnon@xxxxxxxxxxxxxxxxx> wrote:


I claim the slowest


bartv@vonneumann:~/fortran$ ./time_findpos huge(n) is 2147483647.
Enter first number: 1
Enter last number: 147483647
Total bits counted: 294967286
Bart1's method did it from 1 to 147483647 in 1.82 seconds.
Total bits counted: 294967286
Bart2's method did it from 1 to 147483647 in 1.88 seconds.
Total bits counted: 294967286
Bart3's method did it from 1 to 147483647 in 1.89 seconds.
Total bits counted: 294967286
Michel's method did it from 1 to 147483647 in 18.50 seconds.

*fwew*... that's indeed slow :-) 

OK. Here is a reasonable version of the same algorithm:

  function findpos_mich3(n) result (pos)

    integer(kind=i4b), intent(in) :: n
    integer(kind=i4b)             :: pos
    integer(kind=i4b)             :: temp

    temp = ieor(n,n+1)+1

    select case (temp)
    case (0)
      pos = bit_size(n)
    case (1)
      pos = bit_size(n) + 1
    case (2)
      pos = 1
    case (4)
      pos = 2
    case (8)
      pos = 3
    case (16)
      pos = 4
    case (32)
      pos = 5
    case (64)
      pos = 6
    case (128)
      pos = 7
    case (256)
      pos = 8
    case (512)
      pos = 9
    case (1024)
      pos = 10
    case (2048)
      pos = 11
    case (4096)
      pos = 12
    case (8192)
      pos = 13
    case (16384)
      pos = 14
    case (32768)
      pos = 15
    case default
      pos = 15
      do
      temp = temp / 65536
      select case (temp)
      case (1)
        pos = pos + 1
      case (2)
        pos = pos + 2
      case (4)
        pos = pos + 3
      case (8)
        pos = pos + 4
      case (16)
        pos = pos + 5
      case (32)
        pos = pos + 6
      case (64)
        pos = pos + 7
      case (128)
        pos = pos + 8
      case (256)
        pos = pos + 9
      case (512)
        pos = pos + 10
      case (1024)
         pos = pos + 11
      case (2048)
        pos = pos + 12
      case (4096)
        pos = pos + 13
      case (8192)
        pos = pos + 14
      case (16384)
        pos = pos + 15
      case (32768)
        pos = pos + 16
      case default
        pos = pos + 16
        cycle
      end select
      exit
      enddo
    end select

  end function findpos_mich3





but it's a one-liner:

pos = nint (log (real(ieor(n,n+1)+1, kind=renough)) / log (2.0_renough))

:-) 


OK.  Bonus-point for you :-)

Regards,
Bart


.

Relevant Pages

  • Re: CListCtrl, hide and edit
    ... bool CDialogWithList::CompareAndSwapString1(int pos, bool bAscending) ... CMyObjectInfo *temp; ... bool bNotDone = TRUE; ... So I don't use the sort mechanism in the list control at all. ...
    (microsoft.public.vc.mfc)
  • Re: Sorting a CObArray?
    ... Derive a class from CObArray ... BOOL CSortObArray_DerivedClass::CompareAndSwap(int pos) ... SetAt(posNext, temp); ... CString in the CStringArrays. ...
    (microsoft.public.vc.mfc)
  • Re: how can I sum up the values with more than 15 significant digits?
    ... Dim temp As Variant ... Optional Commas As Boolean = True) As String ... Dim Pos As Long ...
    (microsoft.public.excel.misc)
  • Re: Which is best - recordsets/VBA V SQL statements for updating data
    ... If you've analyzed the problem, etc, etc and concluded a temp table is called for, then by all means go for it. ... It has data added to it in the POS screen. ... Once the order has been finished and payment has been received, the data is Inserted from the temp table to the Billing table via an INSERT TO query and then deleted from the temp table. ... The MDB with the temp table in it is compacted when the app is open, each user has their own copy of the temp table MDB in their TEMP folder. ...
    (comp.databases.ms-access)
  • Re: opos vb net code examples
    ... I am new to POS programming and have since found that there is a Pos.net ... > How to send raw data to a printer by using Visual Basic .NET ... > the Pos driver development or the pos printer vendor. ... > Best regards, ...
    (microsoft.public.dotnet.languages.vb)