From mboxrd@z Thu Jan  1 00:00:00 1970
X-Spam-Checker-Version: SpamAssassin 3.4.4 (2020-01-24) on polar.synack.me
X-Spam-Level: 
X-Spam-Status: No, score=-1.9 required=5.0 tests=BAYES_00 autolearn=ham
	autolearn_force=no version=3.4.4
X-Google-Thread: a07f3367d7,7e15102eb14c0020
X-Google-Attributes: gida07f3367d7,public,usenet
X-Google-NewGroupId: yes
X-Google-Language: ENGLISH,ASCII-7-bit
Received: by 10.181.12.101 with SMTP id ep5mr40024wid.1.1349942136333;
        Thu, 11 Oct 2012 00:55:36 -0700 (PDT)
Path: 
 q11ni134269134wiw.1!nntp.google.com!feeder1.cambriumusenet.nl!feeder3.cambriumusenet.nl!feed.tweaknews.nl!216.40.29.245.MISMATCH!novia!border4.nntp.dca.giganews.com!border2.nntp.dca.giganews.com!border3.nntp.dca.giganews.com!border1.nntp.dca.giganews.com!nntp.giganews.com!news.glorb.com!weretis.net!feeder4.news.weretis.net!news.teledata-fn.de!newsfeed.arcor.de!newsspool2.arcor-online.net!news.arcor.de.POSTED!not-for-mail
User-Agent: NewsTap/3.5.5 (iPad)
From: Georg Bauhaus <rm-host.bauhaus@maps.arcor.de>
Newsgroups: comp.lang.ada
Mime-Version: 1.0
Message-ID: 
 <441830536370982493.692537rm-host.bauhaus-maps.arcor.de@news.arcor.de>
Subject: Re: highest bit, statically determined
References: <cd5ac9f5-ebd4-4c1a-8fee-478dd2680a43@googlegroups.com>
Date: 03 Oct 2012 18:54:07 GMT
Organization: Arcor
NNTP-Posting-Date: 03 Oct 2012 20:54:07 CEST
NNTP-Posting-Host: 27ab9806.newsspool1.arcor-online.net
X-Trace: 
 DXC=jim25mMN<UgOKO]LCQ@0g`ic==]BZ:afn4Fo<]lROoRankgeX?EC@@`hXZIWVe1=PlPCY\c7>ejVhZEoXj9QACFc_e9_o>`D1ih
X-Complaints-To: usenet-abuse@arcor.de
Content-Type: text/plain; charset=UTF-8
Content-Transfer-Encoding: 8bit
Date: 2012-10-03T20:54:07+02:00
List-Id: <comp.lang.ada>

<kalvink65@gmail.com> wrote:
> How about binary search algorithm with constant execution time:
> 
> Binary_Search_Highest_Bit_In_Octet_2012 : constant :=
>       (if N > (2**4)-1 then -- determine upper or lower nibble
>           -- upper nibble
>           if N > (2**6)-1
>             -- bits 7 and 6
>             if N > (2**7)-1 then
>                 

Isn't this about the same as the recursive one?
(It uses Boolean'Pos around the third if.)

Also, I don't think its complexity is constant, since the number
of conditionals depends on the position of the first 1 bit.
That dependence is gone with the table.

Relative performance might depend on whether shift
and jump is more expensive than another branch of
conditionals. I'm guessing.