Velocity Reviews - Computer Hardware Reviews

Velocity Reviews > Newsgroups > Programming > C++ > testing if just one bit is set...

Reply
Thread Tools

testing if just one bit is set...

 
 
.rhavin grobert
Guest
Posts: n/a
 
      11-06-2008
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?
 
Reply With Quote
 
 
 
 
Andrew Koenig
Guest
Posts: n/a
 
      11-06-2008
".rhavin grobert" <(E-Mail Removed)> wrote in message
news:(E-Mail Removed)...

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


 
Reply With Quote
 
 
 
 
Salt_Peter
Guest
Posts: n/a
 
      11-06-2008
On Nov 6, 1:42 pm, ".rhavin grobert" <(E-Mail Removed)> 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
*/
 
Reply With Quote
 
Guy.Tristram@gmail.com
Guest
Posts: n/a
 
      11-06-2008
On Nov 6, 7:17*pm, Victor Bazarov <(E-Mail Removed)> 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
 
Reply With Quote
 
Andrey Tarasevich
Guest
Posts: n/a
 
      11-06-2008
Victor Bazarov wrote:
> Andrew Koenig wrote:
>> ".rhavin grobert" <(E-Mail Removed)> wrote in message
>> news:(E-Mail Removed)...
>>
>>> 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
 
Reply With Quote
 
Juha Nieminen
Guest
Posts: n/a
 
      11-06-2008
Jeff Schwab wrote:
> I've only considered it for two's complement.


Exactly how does two's complement representation kick in with unsigned
values?
 
Reply With Quote
 
Sana
Guest
Posts: n/a
 
      11-06-2008
On Nov 6, 3:09*pm, Andrey Tarasevich <(E-Mail Removed)>
wrote:
> Victor Bazarov wrote:
> > Andrew Koenig wrote:
> >> ".rhavin grobert" <(E-Mail Removed)> wrote in message
> >>news:(E-Mail Removed)....

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

 
Reply With Quote
 
Andrey Tarasevich
Guest
Posts: n/a
 
      11-06-2008
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
 
Reply With Quote
 
Andrey Tarasevich
Guest
Posts: n/a
 
      11-06-2008
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
 
Reply With Quote
 
Salt_Peter
Guest
Posts: n/a
 
      11-06-2008
On Nov 6, 3:01 pm, Victor Bazarov <(E-Mail Removed)> wrote:
> Salt_Peter wrote:
> > On Nov 6, 1:42 pm, ".rhavin grobert" <(E-Mail Removed)> 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


 
Reply With Quote
 
 
 
Reply

Thread Tools

Posting Rules
You may not post new threads
You may not post replies
You may not post attachments
You may not edit your posts

BB code is On
Smilies are On
[IMG] code is On
HTML code is Off
Trackbacks are On
Pingbacks are On
Refbacks are Off


Similar Threads
Thread Thread Starter Forum Replies Last Post
What is the point of having 16 bit colour if a computer monitor can only display 8 bit colour? How do you edit 16 bit colour when you can only see 8 bit? Scotius Digital Photography 6 07-13-2010 03:33 AM
Reversing Bit Order.. i.e. MSB becomes bit 0, LSB becomes bit 15 benn686@hotmail.com C++ 9 08-22-2007 12:13 AM
"LoadLibrary" of a 32 bit so with 64 bit java on a 64 bit machine markryde@gmail.com Java 3 01-19-2007 10:30 PM
64 bit - Windows Liberty 64bit, Windows Limited Edition 64 Bit, Microsoft SQL Server 2000 Developer Edition 64 Bit, IBM DB2 64 bit - new ! vvcd Computer Support 0 09-17-2004 08:15 PM
64 bit - Windows Liberty 64bit, Windows Limited Edition 64 Bit,Microsoft SQL Server 2000 Developer Edition 64 Bit, IBM DB2 64 bit - new! Ionizer Computer Support 1 01-01-2004 07:27 PM



Advertisments