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]

Re: testing if just one bit is set...

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

[Victor Bazarov]

Re: testing if just one bit is set...

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

Re: testing if just one bit is set...

Andrew Koenig wrote:

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

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]

Re: testing if just one bit is set...

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]

Re: testing if just one bit is set...

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

Re: testing if just one bit is set...

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<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@gmail.com]

Re: testing if just one bit is set...

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]

Re: testing if just one bit is set...

Victor Bazarov wrote:

Andrew Koenig wrote:

>".rhavin grobert" <clqrq@yahoo.de wrote in message
>news:ec37ea3 5-030a-4072-9239-f93ef12f1995@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]

Re: testing if just one bit is set...

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]

Re: testing if just one bit is set...

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:ec37ea3 5-030a-4072-9239-f93ef12f1995@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.

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

[Jeff Schwab]

Re: testing if just one bit is set...

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

[Andrey Tarasevich]

Re: testing if just one bit is set...

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]

Re: testing if just one bit is set...

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

[Salt_Peter]

Re: testing if just one bit is set...

On Nov 6, 3:01 pm, Victor Bazarov <v.Abaza...@com Acast.netwrote:

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.

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