testing if just one bit is set...

Discussion in 'C++' started by .rhavin grobert, Nov 6, 2008.

  1. guess you have a processor that can handle 32bit natively and you have
    a 32-bit-int. im now looking for some *ultrafast* way to determine if
    an int has more than one bit set. any ideas?
     
    .rhavin grobert, Nov 6, 2008
    #1
    1. Advertising

  2. ".rhavin grobert" <> wrote in message
    news:...

    > guess you have a processor that can handle 32bit natively and you have
    > a 32-bit-int. im now looking for some *ultrafast* way to determine if
    > an int has more than one bit set. any ideas?


    If n has an unsigned type (i.e. unsigned int or unsigned long), then (n&-n)
    is equal to n unless n has more than one bit set.
    So the expression you're looking for is n!=(n&-n)
     
    Andrew Koenig, Nov 6, 2008
    #2
    1. Advertising

  3. .rhavin grobert

    Salt_Peter Guest

    On Nov 6, 1:42 pm, ".rhavin grobert" <> wrote:
    > guess you have a processor that can handle 32bit natively and you have
    > a 32-bit-int. im now looking for some *ultrafast* way to determine if
    > an int has more than one bit set. any ideas?


    an int is not necessarily 32 bits. That depends on the platform.
    bitset has a member function count() which returns a count of bits
    set.
    Use that. If thats too slow for you, try release mode instead of
    debug.

    #include <iostream>
    #include <bitset>

    template< typename T >
    bool checkbits(const std::bitset< sizeof(T) * 8 >& r)
    {
    return (r.count() > 1) ? true : false;
    }

    int main ()
    {
    int n(257);
    std::bitset< sizeof(int) * 8 > b(n);

    for (std::size_t i = b.size(); i > 0; --i)
    {
    std::cout << b.test(i - 1);
    if((i-1)%4 == 0)
    std::cout << " ";
    }
    std::cout << std::endl;

    if(checkbits< int >(b))
    std::cout << "more than one bit set\n";
    else
    std::cout << "less than 2 bits set\n";
    }

    /*
    0000 0000 0000 0000 0000 0001 0000 0000
    result: less than 2 bits set
    */
     
    Salt_Peter, Nov 6, 2008
    #3
  4. .rhavin grobert

    Guest

    On Nov 6, 7:17 pm, Victor Bazarov <> wrote:
    > Andrew Koenig wrote:
    > > If n has an unsigned type (i.e. unsigned int or unsigned long), then (n&-n)
    > > is equal to n unless n has more than one bit set.
    > > So the expression you're looking for is n!=(n&-n)

    >
    > Wow...  Does it work for any representation (two's complement, one's
    > complement, signed magnitude)?


    There's a good page on this type of trick here:

    http://realtimecollisiondetection.net/blog/?p=78

    Guy
     
    , Nov 6, 2008
    #4
  5. Victor Bazarov wrote:
    > Andrew Koenig wrote:
    >> ".rhavin grobert" <> wrote in message
    >> news:...
    >>
    >>> guess you have a processor that can handle 32bit natively and you have
    >>> a 32-bit-int. im now looking for some *ultrafast* way to determine if
    >>> an int has more than one bit set. any ideas?

    >>
    >> If n has an unsigned type (i.e. unsigned int or unsigned long), then
    >> (n&-n) is equal to n unless n has more than one bit set.
    >> So the expression you're looking for is n!=(n&-n)

    >
    > Wow... Does it work for any representation (two's complement, one's
    > complement, signed magnitude)?


    Unsigned values don't vary in representation. "Two's complement, one's
    complement, signed magnitude" come into play with signed representations
    only.

    --
    Best regards,
    Andrey Tarasevich
     
    Andrey Tarasevich, Nov 6, 2008
    #5
  6. Jeff Schwab wrote:
    > I've only considered it for two's complement.


    Exactly how does two's complement representation kick in with unsigned
    values?
     
    Juha Nieminen, Nov 6, 2008
    #6
  7. .rhavin grobert

    Sana Guest

    On Nov 6, 3:09 pm, Andrey Tarasevich <>
    wrote:
    > Victor Bazarov wrote:
    > > Andrew Koenig wrote:
    > >> ".rhavin grobert" <> wrote in message
    > >>news:....

    >
    > >>> guess you have a processor that can handle 32bit natively and you have
    > >>> a 32-bit-int. im now looking for some *ultrafast* way to determine if
    > >>> an int has more than one bit set. any ideas?

    >
    > >> If n has an unsigned type (i.e. unsigned int or unsigned long), then
    > >> (n&-n) is equal to n unless n has more than one bit set.
    > >> So the expression you're looking for is n!=(n&-n)

    >
    > > Wow...  Does it work for any representation (two's complement, one's
    > > complement, signed magnitude)?

    >
    > Unsigned values don't vary in representation. "Two's complement, one's
    > complement, signed magnitude" come into play with signed representations
    > only.


    Assuming a 32 bit system, and let n be an unsigned int of value
    0xFFFFFFFF (all bits set)
    What would be the value of -n in the expression n & -n?

    Thanks,
    Sana
     
    Sana, Nov 6, 2008
    #7
  8. Sana wrote:
    > Assuming a 32 bit system, and let n be an unsigned int of value
    > 0xFFFFFFFF (all bits set)
    > What would be the value of -n in the expression n & -n?


    '-n' in this case would be '1' (0x00000001). See 5.3/7: "The negative of
    an unsigned quantity is computed by subtracting its value from 2^n,
    where n is the number of bits in the promoted operand".

    --
    Best regards,
    Andrey Tarasevich
     
    Andrey Tarasevich, Nov 6, 2008
    #8
  9. Jeff Schwab wrote:
    >
    > Are you asking why the representation is relevant? As far as I know,
    > all of the representations allowed by the Standard are equivalent for
    > purposes of this discussion. The only one I've really considered is
    > two's complement, though. That doesn't mean I think there's any
    > particular problem with the other allowed representations, just that I
    > don't know enough about them to know whether there are any gotchas.


    Well, unsigned values in C++ have one and only one [allowed]
    representation. Which is why some people might find any mention of
    "other representations" to be confusing (equivalent or not).

    --
    Best regards,
    Andrey Tarasevich
     
    Andrey Tarasevich, Nov 6, 2008
    #9
  10. .rhavin grobert

    Salt_Peter Guest

    On Nov 6, 3:01 pm, Victor Bazarov <> wrote:
    > Salt_Peter wrote:
    > > On Nov 6, 1:42 pm, ".rhavin grobert" <> wrote:
    > >> guess you have a processor that can handle 32bit natively and you have
    > >> a 32-bit-int. im now looking for some *ultrafast* way to determine if
    > >> an int has more than one bit set. any ideas?

    >
    > > an int is not necessarily 32 bits. That depends on the platform.
    > > bitset has a member function count() which returns a count of bits
    > > set.
    > > Use that. If thats too slow for you, try release mode instead of
    > > debug.

    >
    > > #include <iostream>
    > > #include <bitset>

    >
    > > template< typename T >
    > > bool checkbits(const std::bitset< sizeof(T) * 8 >& r)

    >
    > What's the "8" for? Consider your own words "depends on the platform"
    > before giving your answer.


    Couldn't agree with you more, what do you suggest? sizeof(char) ?
    The n!=(n&-n) solution is better, but for the sake of platform...

    >
    > > {
    > > return (r.count() > 1) ? true : false;

    >
    > Wouldn't it be clearer to write
    >
    > return r.count() > 1;
    >
    > ?
    >
    > > }

    >
    > Also, consider rewriting so that the type doesn't have to be explicitly
    > specified. Perhaps something like
    >
    > template<typename T> bool checkbits(T t)
    > {
    > std::bitset<..whatever..> r(t);
    > ...
    >
    >
    >
    > > int main ()
    > > {
    > > int n(257);
    > > std::bitset< sizeof(int) * 8 > b(n);

    >
    > Here it is again... What's the meaning of "8" here?
    >
    >
    >
    >
    >
    > > for (std::size_t i = b.size(); i > 0; --i)
    > > {
    > > std::cout << b.test(i - 1);
    > > if((i-1)%4 == 0)
    > > std::cout << " ";
    > > }
    > > std::cout << std::endl;

    >
    > > if(checkbits< int >(b))
    > > std::cout << "more than one bit set\n";
    > > else
    > > std::cout << "less than 2 bits set\n";
    > > }

    >
    > > /*
    > > 0000 0000 0000 0000 0000 0001 0000 0000
    > > result: less than 2 bits set
    > > */

    >
    > V
    > --
    > Please remove capital 'A's when replying by e-mail
    > I do not respond to top-posted replies, please don't ask
     
    Salt_Peter, Nov 6, 2008
    #10
  11. .rhavin grobert

    James Kanze Guest

    On Nov 6, 10:55 pm, Jeff Schwab <> wrote:
    > Juha Nieminen wrote:
    > > Jeff Schwab wrote:
    > >> I've only considered it for two's complement.


    > > Exactly how does two's complement representation kick in
    > > with unsigned values?


    > Are you asking why the representation is relevant? As far as
    > I know, all of the representations allowed by the Standard are
    > equivalent for purposes of this discussion.


    Yes and no. For signed values, the bit pattern of -n will
    depend on the representation. For unsigned values, the standard
    defines -i to be 2^n-i (where n is the number of value bits in
    the unsigned). Which by a curious bit of chance:)-)) just
    happens to correspond to what you'd get for 2's complement
    signed values.

    > The only one I've really considered is two's complement,
    > though. That doesn't mean I think there's any particular
    > problem with the other allowed representations, just that I
    > don't know enough about them to know whether there are any
    > gotchas.


    On thing is immediately certain, the bit pattern of -n will
    depend on the representation if the type is signed. Which means
    that it probably will not work.

    --
    James Kanze (GABI Software) email:
    Conseils en informatique orientée objet/
    Beratung in objektorientierter Datenverarbeitung
    9 place Sémard, 78210 St.-Cyr-l'École, France, +33 (0)1 30 23 00 34
     
    James Kanze, Nov 7, 2008
    #11
  12. .rhavin grobert

    James Kanze Guest

    On Nov 6, 11:47 pm, Jeff Schwab <> wrote:
    > Andrey Tarasevich wrote:
    > > Well, unsigned values in C++ have one and only one [allowed]
    > > representation. Which is why some people might find any
    > > mention of "other representations" to be confusing
    > > (equivalent or not).


    > We're not only discussing unsigned values.


    > The OP was specifically asking about the number of bits set in
    > a 32-bit int; by definition, that depends on the
    > representation.


    Of course, the obvious solution is to cast to unsigned, and then
    procede. Except that if he really is concerned with signed
    values, casting to unsigned may change the bit pattern (and thus
    the number of bits). A reinterpret_cast involving references
    might do the trick (to make the compiler access the value as if
    it were unsigned), although even there, on at least one machine,
    unsigned is implemented by simply masking out the sign bit (i.e.
    UINT_MAX == INT_MAX).

    Given that the original poster specified 32 bits, however, I
    rather suspect that total portability wasn't a concern; all of
    the 32 bit machines I know today use 2's complement, where
    converting an int to an unsigned doesn't change the bit pattern.

    --
    James Kanze (GABI Software) email:
    Conseils en informatique orientée objet/
    Beratung in objektorientierter Datenverarbeitung
    9 place Sémard, 78210 St.-Cyr-l'École, France, +33 (0)1 30 23 00 34
     
    James Kanze, Nov 7, 2008
    #12
  13. .rhavin grobert

    Kai-Uwe Bux Guest

    blargg wrote:

    > In article <phHQk.18329$>,
    > "Andrew Koenig" <> wrote:
    >
    >> ".rhavin grobert" <> wrote in message
    >> news:...
    >>
    >> > guess you have a processor that can handle 32bit natively and you have
    >> > a 32-bit-int. im now looking for some *ultrafast* way to determine if
    >> > an int has more than one bit set. any ideas?

    >>
    >> If n has an unsigned type (i.e. unsigned int or unsigned long), then
    >> (n&-n) is equal to n unless n has more than one bit set.
    >> So the expression you're looking for is n!=(n&-n)

    >
    > What about
    >
    > (n-1)&n
    >
    > which probably involves fewer operations (negate+and+compare versus
    > subtract+and)? Non-zero if more than one bit is set.


    For the OP, that would work too. Which one is faster, only measurement can
    show.

    As for the two methods, n & -n has the nice feature of having all but the
    lowest order bit in n equal to 0. Thus, it provides essentially a way to
    extract the lowest order bit.


    Best

    Kai-Uwe Bux
     
    Kai-Uwe Bux, Nov 7, 2008
    #13
  14. .rhavin grobert

    James Kanze Guest

    On Nov 7, 12:59 pm, Jeff Schwab <> wrote:
    > James Kanze wrote:
    > > On Nov 6, 11:47 pm, Jeff Schwab <> wrote:
    > >> Andrey Tarasevich wrote:
    > >>> Well, unsigned values in C++ have one and only one [allowed]
    > >>> representation. Which is why some people might find any
    > >>> mention of "other representations" to be confusing
    > >>> (equivalent or not).


    > >> We're not only discussing unsigned values.

    > > Of course, the obvious solution is to cast to unsigned, and
    > > then procede. Except that if he really is concerned with
    > > signed values, casting to unsigned may change the bit
    > > pattern (and thus the number of bits). A reinterpret_cast
    > > involving references might do the trick (to make the
    > > compiler access the value as if it were unsigned),


    > Is that UB? It reminds me of the old "access the other member
    > of the union" trick.


    Yes and no. Casting a pointer or a reference is the
    "officially" sanctionned way of type punning, but of course, you
    don't get any guarantees with regards to the meaning of the
    results in general. In this one particular case, you are
    guaranteed that 1) the size of a signed integral type and its
    corresponding unsigned is the same, and 2) that non-negative
    values will have the same representation. So unless the sign
    bit acts funny, you should be OK. (The C standard more or less
    sanctions it, too, in that it allows you to pass signed integers
    to match a "%x" format specifier.)

    > > although even there, on at least one machine, unsigned is
    > > implemented by simply masking out the sign bit (i.e.
    > > UINT_MAX == INT_MAX).


    > What machine is that? I don't doubt that such platforms
    > exist, but that sounds more exotic than anything I've
    > targeted.


    Unisys MCP. It's an interesting machine; it descends from the
    old Burroughs line of machines, uses a stack instead of
    registers, and has a tagged architecture; there's only one add,
    sub, etc. instruction, which works for floating point or
    integral values. I've not got access to one to do any testing,
    but given the way it works, I suspect that an overflow in
    integral arithmetic could lead to some very strange behavior.

    --
    James Kanze (GABI Software) email:
    Conseils en informatique orientée objet/
    Beratung in objektorientierter Datenverarbeitung
    9 place Sémard, 78210 St.-Cyr-l'École, France, +33 (0)1 30 23 00 34
     
    James Kanze, Nov 7, 2008
    #14
  15. .rhavin grobert

    James Kanze Guest

    On Nov 7, 12:01 pm, (blargg) wrote:
    > James Kanze wrote:


    > [...]
    > but because two's complement is the most
    > natural representation.


    What does "the most natural representation" mean? I would have
    thought that the most natural representation would be base 10
    (which is forbidden for ints).

    2's complement has one very big problem: - INT_MIN isn't
    representable. 1's complement and signed magnitude have to
    consider signed 0, but IMHO, that's a lesser problem; in
    addition, it can be handled by hardware in a transparent manner.

    --
    James Kanze (GABI Software) email:
    Conseils en informatique orientée objet/
    Beratung in objektorientierter Datenverarbeitung
    9 place Sémard, 78210 St.-Cyr-l'École, France, +33 (0)1 30 23 00 34
     
    James Kanze, Nov 7, 2008
    #15
  16. .rhavin grobert

    James Kanze Guest

    On Nov 8, 12:02 pm, (blargg) wrote:
    > James Kanze wrote:
    > > On Nov 7, 12:01 pm, (blargg) wrote:
    > > > James Kanze wrote:


    > > > [...]
    > > > but because two's complement is the most natural
    > > > representation.


    > > What does "the most natural representation" mean?


    > Two's complement is the natural way to represent negative
    > values, since things like add, subtract, multiply (both by a
    > power of two using a shift, and by an arbitrary value) can use
    > the same hardware as the unsigned equivalents.


    In other words, it's not the most natural, it's the cheapest.

    > [...]> 2's complement has one very big problem: - INT_MIN isn't
    > > representable.


    > [...]


    > How is this a big problem? Since trying to generate a value
    > outside the range of a signed type is UB, one could just treat
    > the most negative as UB by making INT_MIN == -INT_MAX.


    To begin with, you can't write the value directly as an integral
    literal. And you have to special case it in a lot of cases.

    --
    James Kanze (GABI Software) email:
    Conseils en informatique orientée objet/
    Beratung in objektorientierter Datenverarbeitung
    9 place Sémard, 78210 St.-Cyr-l'École, France, +33 (0)1 30 23 00 34
     
    James Kanze, Nov 9, 2008
    #16
  17. "Victor Bazarov" <> wrote in message
    news:gevfrd$q4n$...

    >> If n has an unsigned type (i.e. unsigned int or unsigned long), then
    >> (n&-n) is equal to n unless n has more than one bit set.
    >> So the expression you're looking for is n!=(n&-n)


    > Wow... Does it work for any representation (two's complement, one's
    > complement, signed magnitude)?


    Just 2's complement -- but that's what everyone uses these days anyway.
     
    Andrew Koenig, Nov 14, 2008
    #17
  18. "Andrey Tarasevich" <> wrote in message
    news:gevisn$hss$...

    > Unsigned values don't vary in representation. "Two's complement, one's
    > complement, signed magnitude" come into play with signed representations
    > only.


    The question is whether the meaning of -n depends on the representation of
    signed values.
     
    Andrew Koenig, Nov 14, 2008
    #18
  19. Andrew Koenig wrote:
    >
    >> Unsigned values don't vary in representation. "Two's complement, one's
    >> complement, signed magnitude" come into play with signed representations
    >> only.

    >
    > The question is whether the meaning of -n depends on the representation of
    > signed values.


    And the answer is no. Within the pre-condition of 'n' being of type
    'unsigned int' or 'unsigned long' (set in your original message) it
    doesn't. The meaning of unary '-' for these types is defined by the
    language specification without any dependency on signed representations,
    meaning that the result is always the same regardless of signed
    representation used by the implementation.

    --
    Best regards,
    Andrey Tarasevich
     
    Andrey Tarasevich, Nov 14, 2008
    #19
  20. .rhavin grobert

    James Kanze Guest

    On Nov 14, 6:48 pm, "Andrew Koenig" <> wrote:
    > "Victor Bazarov" <> wrote in message


    > news:gevfrd$q4n$...


    > >> If n has an unsigned type (i.e. unsigned int or unsigned
    > >> long), then (n&-n) is equal to n unless n has more than one
    > >> bit set. So the expression you're looking for is n!=(n&-n)

    > > Wow...  Does it work for any representation (two's
    > > complement, one's complement, signed magnitude)?


    > Just 2's complement -- but that's what everyone uses these
    > days anyway.


    Andy, what's up? In your posting, you specifically said "If n
    has an unsigned type". And you know very well that the standard
    defines - for unsigned types exactly.

    And not everyone uses 2's complement. There are at least two
    architectures being sold today that don't: one with 36 bit 1's
    complement, and another with 48 bit signed magnitude. (Since
    they're mainframes, a lot of programmers don't see them, but
    they are there.)

    --
    James Kanze (GABI Software) email:
    Conseils en informatique orientée objet/
    Beratung in objektorientierter Datenverarbeitung
    9 place Sémard, 78210 St.-Cyr-l'École, France, +33 (0)1 30 23 00 34
     
    James Kanze, Nov 14, 2008
    #20
    1. Advertising

Want to reply to this thread or ask your own question?

It takes just 2 minutes to sign up (and it's free!). Just click the sign up button to choose a username and then you can ask your own questions on the forum.
Similar Threads
  1. Replies:
    3
    Views:
    1,766
    Timothy Bendfelt
    Jan 19, 2007
  2. Replies:
    9
    Views:
    981
    Juha Nieminen
    Aug 22, 2007
  3. Jeff.M
    Replies:
    6
    Views:
    179
    Lasse Reichstein Nielsen
    May 4, 2009
  4. Charles Hixson

    bit count or bit set && Python3

    Charles Hixson, Oct 25, 2012, in forum: Python
    Replies:
    5
    Views:
    213
    Charles Hixson
    Oct 26, 2012
  5. MRAB
    Replies:
    0
    Views:
    154
Loading...

Share This Page