473,854 Members | 1,531 Online

# testing if just one bit is set...

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?
Nov 6 '08 #1
32 9695
".rhavin grobert" <cl***@yahoo.de wrote in message
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)
Nov 6 '08 #2
..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,
{
}

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) {
}
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
--
Nov 6 '08 #3
Andrew Koenig wrote:
".rhavin grobert" <cl***@yahoo.de wrote in message
>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
--
Nov 6 '08 #4
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
*/
Nov 6 '08 #5
..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

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 ));
}
Nov 6 '08 #6
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"
{
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
--
Nov 6 '08 #7
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
Nov 6 '08 #8
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
Nov 6 '08 #9
Jeff Schwab wrote:
I've only considered it for two's complement.
Exactly how does two's complement representation kick in with unsigned
values?
Nov 6 '08 #10

This thread has been closed and replies have been disabled. Please start a new discussion.