Re: highest bit, statically determined

[Anatoly Chernyshev <achernyshev@gmail.com>]

On Thursday, October 4, 2012 2:01:50 PM UTC+4, kalvi...@gmail.com wrote:
> maanantai, 1. lokakuuta 2012 11.52.43 UTC+3 Anatoly Chernyshev kirjoitti:
> 
> > > 
> 
> > 
> 
> > >     68580000 1.687923000
> 
> > 
> 
> > > 
> 
> > 
> 
> > >     68580000 1.447859000
> 
> > 
> 
> > > 
> 
> > 
> 
> > >     68580000 24.481472000
> 
> > 
> 
> > 
> 
> > 
> 
> > Yes, that could be expected. Here's the draft lightning-fast version:
> 
> > 
> 
> > 
> 
> > 
> 
> > procedure xx is
> 
> > 
> 
> > last_bit_a: array(0..255) of natural:=(0|1=>0,2|3=>1,4..7=>2, 8..15=>3, 16..31=>4,32..63=>5, 64..127=>6, 128..255=>7);
> 
> > 
> 
> > N:natural;
> 
> > 
> 
> > begin
> 
> > 
> 
> > ...
> 
> > 
> 
> > Highest_Bit_In_Octet:=last_bit_a(N);
> 
> > 
> 
> > ...
> 
> > 
> 
> > end xx;
> 
> 
> 
> This can be optimised for improved size so that we create a lookup table only for a nibble values (0..15), and divide the handling into two parts according to whether the higher nibble is zero or non-zero. The end result would be a slighter slower execution speed but less code space. And this method can easily be extended to larger data sizes, too.
> 
> 
> 
> - Kalvin

If you play with the memory optimization (I'm not very good at it), the array above will be made of 3 bit integers (0 to 7), which occupy lousy 3*256/8= 96 bytes of memory. Laughable by today's standards. Even if you go for long_long_long..._integers, the table will be quite small.