testing if just one bit is set...

[.rhavin grobert]

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?

[Andrew Koenig]

".rhavin grobert" <cl***@yahoo.de wrote in message
news:ec******** *************** ***********@u29 g2000pro.google groups.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]

..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 moreThanOneBitS et(unsigned value,
unsigned mask1, unsigned mask2)
{
return (value & mask1) && (value & mask2);
}

bool moreThanOneBitS et(unsigned value)
{
static const unsigned masks[] = { 0x0000FFFF,0xFF FF0000,
0x00FF00FF,0xFF 00FF00,
0x0F0F0F0F,0xF0 F0F0F0,
0x33333333,0xCC CCCCCC,
0x55555555,0xAA AAAAAA };
if (value 0) {
return moreThanOneBitS et(value, masks[0], masks[1]) ||
moreThanOneBitS et(value, masks[2], masks[3]) ||
moreThanOneBitS et(value, masks[4], masks[5]) ||
moreThanOneBitS et(value, masks[6], masks[7]) ||
moreThanOneBitS et(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]

Andrew Koenig wrote:

".rhavin grobert" <cl***@yahoo.de wrote in message
news:ec******** *************** ***********@u29 g2000pro.google groups.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]

On Nov 6, 1:42 pm, ".rhavin grobert" <[e-mail] 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]

..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_s et(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]

Salt_Peter wrote:

On Nov 6, 1:42 pm, ".rhavin grobert" <[e-mail] 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<typena me Tbool checkbits(T t)
{
std::bitset<..w hatever..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]

On Nov 6, 7:17*pm, Victor Bazarov <v.Abaza...@com Acast.netwrote:

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

[Andrey Tarasevich]

Victor Bazarov wrote:

Andrew Koenig wrote:

>".rhavin grobert" <cl***@yahoo.de wrote in message
news:ec******* *************** ************@u2 9g2000pro.googl egroups.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]

Jeff Schwab wrote:

I've only considered it for two's complement.

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