
Boost : 
From: Maarten Kronenburg (M.Kronenburg_at_[hidden])
Date: 20060531 09:23:21
Rene,
Also I will change the complexity
of get_sub into:
O(1)O(N) depending on the value of nbits
and add to the requirements:
The internal representation is such that
the sign and the binary representation of
the absolute value are stored separately.
This means that the bit access function get_sub
is sign independent
Regards, Maarten.
"Rene Rivera" <grafik.list_at_[hidden]> wrote in message
news:447CACE0.20907_at_redshiftsoftware.com...
> Maarten Kronenburg wrote:
> > Rene,
> > In the meantime the get_sub has been
> > added for bit access, see below.
>
> Yes, I saw that before I sent the email. Hence I don't think it's
> sufficient.
>
> > This is not an iterator, but it may be
> > sufficient for access of the binary
> > representation.
> > Is this also usefull for you?
> >
> > size_type highest_bit() const;
> > Complexity: O(N)
> >
> > size_type lowest_bit() const;
> > Complexity: O(N)
> >
> > const integer get_sub( size_type startbit, size_type nbits ) const;
> > Complexity: O(N)
>
> There are a few problems with using those for "binary" access:
>
> * It is not optimal. Using the above would result in an O(N^2) algo for
> something that most of the time would be an O(1) operation (depending on
> the internal representation, at worse would be O(N)).
>
> * The representation that get_sub, highest_bit, lowest_bit, operate on
> is not defined. I don't see such a definition in the document either,
> AFAICT. So one couldn't even use the faster "int x =
> to_int(I.get_sub(0,16));"
>
> I don't care that much what the form of access looks like. The important
> aspect is having a *defined representation* that users can convert to
> and from. For example other access methods might be:
>
> // Iterators, like std::string::data:
> std::pair<word_type const *, word_type const *> integer::data() const;
>
> // Inserter, like std::string::copy:
> template <typename OutputIterator>
> void integer::copy(OutputIterator) const;
>
> // Stream like:
> template <typename Container>
> operator << (Container &, integer const &);
>
> Of course there would need to be a corresponding constructor to have the
> data round trip.
>
>
>
> 
>  Grafik  Don't Assume Anything
>  Redshift Software, Inc.  http://redshiftsoftware.com
>  rrivera/acm.org  grafik/redshiftsoftware.com
>  102708583/icq  grafikrobot/aim  grafikrobot/yahoo
> _______________________________________________
> Unsubscribe & other changes:
http://lists.boost.org/mailman/listinfo.cgi/boost
>
Boost list run by bdawes at acm.org, gregod at cs.rpi.edu, cpdaniel at pacbell.net, john at johnmaddock.co.uk