[lnkForumImage]
TotalShareware - Download Free Software
Confronta i prezzi di migliaia di prodotti.
Asp Forum
 Home | Login | Register | Search 


 

Forums >

comp.lang.c++

testing if just one bit is set...

.rhavin grobert

11/6/2008 6:42:00 PM

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?
33 Answers

Andrew Koenig

11/6/2008 7:09:00 PM

0

".rhavin grobert" <clqrq@yahoo.de> wrote in message
news:ec37ea35-030a-4072-9239-f93ef12f1995@u29g2000pro.googlegroups.com...

> 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)

Victor Bazarov

11/6/2008 7:15:00 PM

0

..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?

I think the "binary search" method is quick enough, but you will need to
measure it. Something like

inline bool moreThanOneBitSet(unsigned value,
unsigned mask1, unsigned mask2)
{
return (value & mask1) && (value & mask2);
}

bool moreThanOneBitSet(unsigned value)
{
static const unsigned masks[] = { 0x0000FFFF,0xFFFF0000,
0x00FF00FF,0xFF00FF00,
0x0F0F0F0F,0xF0F0F0F0,
0x33333333,0xCCCCCCCC,
0x55555555,0xAAAAAAAA };
if (value > 0) {
return moreThanOneBitSet(value, masks[0], masks[1]) ||
moreThanOneBitSet(value, masks[2], masks[3]) ||
moreThanOneBitSet(value, masks[4], masks[5]) ||
moreThanOneBitSet(value, masks[6], masks[7]) ||
moreThanOneBitSet(value, masks[8], masks[9]);
}
else
return false;
}

At most, 10 bitwise AND, 5 logical AND, 5 logical OR, and not sure how
many tests against 0 and jumps...

V
--
Please remove capital 'A's when replying by e-mail
I do not respond to top-posted replies, please don't ask

Victor Bazarov

11/6/2008 7:17:00 PM

0

Andrew Koenig wrote:
> ".rhavin grobert" <clqrq@yahoo.de> wrote in message
> news:ec37ea35-030a-4072-9239-f93ef12f1995@u29g2000pro.googlegroups.com...
>
>> 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)?

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

11/6/2008 7:55:00 PM

0

On Nov 6, 1:42 pm, ".rhavin grobert" <cl...@yahoo.de> 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
*/

Jeff Schwab

11/6/2008 7:58:00 PM

0

..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?

The following is based on an idiom in Hacker's Delight, by Henry S.
Warren, Jr., Addison Wesley, 2003. I've only considered it for two's
complement. If you need a lot of these very low-level shortcuts (or
just like reading about them), buy the book. It's a mind-bender.

bool multiple_bits_set(unsigned n) {
return n & (n - 1);
}

bool exactly_one_bit_set(unsigned n) {
return n && !multiple_bits_set(n);
}

#include <cassert>

int main() {

for (unsigned n = 1; n; n <<= 1) {
assert(exactly_one_bit_set(n));
}

assert(!exactly_one_bit_set(0));
assert(!exactly_one_bit_set(3));
assert(!exactly_one_bit_set(12));
}

Victor Bazarov

11/6/2008 8:02:00 PM

0

Salt_Peter wrote:
> On Nov 6, 1:42 pm, ".rhavin grobert" <cl...@yahoo.de> 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.

> {
> 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

Guy.Tristram

11/6/2008 8:07:00 PM

0

On Nov 6, 7:17 pm, Victor Bazarov <v.Abaza...@comAcast.net> 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/...

Guy

Andrey Tarasevich

11/6/2008 8:09:00 PM

0

Victor Bazarov wrote:
> Andrew Koenig wrote:
>> ".rhavin grobert" <clqrq@yahoo.de> wrote in message
>> news:ec37ea35-030a-4072-9239-f93ef12f1995@u29g2000pro.googlegroups.com...
>>
>>> 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

Juha Nieminen

11/6/2008 9:32:00 PM

0

Jeff Schwab wrote:
> I've only considered it for two's complement.

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

Sana

11/6/2008 9:49:00 PM

0

On Nov 6, 3:09 pm, Andrey Tarasevich <andreytarasev...@hotmail.com>
wrote:
> Victor Bazarov wrote:
> > Andrew Koenig wrote:
> >> ".rhavin grobert" <cl...@yahoo.de> wrote in message
> >>news:ec37ea35-030a-4072-9239-f93ef12f1995@u29g2000pro.googlegroups.com....
>
> >>> 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