473,854 Members | 1,531 Online
Bytes | Software Development & Data Engineering Community
+ Post

Home Posts Topics Members FAQ

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
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)
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,
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
Nov 6 '08 #3
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
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
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 ));
}
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"
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
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.

Similar topics

0
1778
by: Jonathan Allen | last post by:
We have found that our method of testing does not match traditional text-book methodologies. I decided to write a short white paper on it so that I could get your opinions. Does anyone else use this method? If so, what the heck is it called? Do you think it would work in other projects, or did we just luck out? Jonathan Allen *****************
0
1498
by: Brian Russell | last post by:
We have three servers (beyond my development box) in our organization. The first is a testing server that has IIS and SQL Server on it. The second is another testing server that also has IIS and SQL Server. The final is the production box that only has IIS. I develop on my own machine, copy to the first testing server, the code is tested, copy the code from testing 1 to testing 2, the code is tested again, and then copy testing 2 code...
2
1292
by: Ken | last post by:
I'd like to know how others approach testing. I work for a bank and there are some fairly paranoid people here. My philosophy is to test only the webforms that were changed. But people here are telling me the whole app needs to be tested. I think that's crazy. What's your opinion? Thanks Ken
72
5291
by: Jacob | last post by:
I have compiled a set og unit testing recommendations based on my own experience on the concept. Feedback and suggestions for improvements are appreciated: http://geosoft.no/development/unittesting.html Thanks.
58
3576
by: nw | last post by:
Hi, I have been asked to teach a short course on testing in C++. Until now I have used my own testing classes (which from what I've seen seem similar to the boost unit testing classes). Considering I have a limited amount of time what do readers of this group think would be useful to cover in this course? Is boost the way to go? Sorry if this is off-topic in this group.
18
2406
by: Andrew Wan | last post by:
I have been developing web applications with ASP & Javascript for a long time. I have been using Visual Studio 2003.NET. While VS2003 is okay for intellisense of ASP & Javascript, it's still not that great. One of the cons of ASP & Javascript is that they're both interpreted, which means one has twice the amount of work to do interms of syntax checking & semantic/runtime checking. Another bad thing is that ASP & Javascript doesn't have...
24
2536
by: David | last post by:
Hi list. What strategies do you use to ensure correctness of new code? Specifically, if you've just written 100 new lines of Python code, then: 1) How do you test the new code? 2) How do you ensure that the code will work correctly in the future? Short version:
0
1383
by: Matthew Fitzgibbons | last post by:
I'm by no means a testing expert, but I'll take a crack at it. Casey McGinty wrote: I've never run into this. Rule of thumb: always separate software from hardware. Write mock classes or functions that do your hardware/file access that always return known data (but remember to test for alpha and beta errors--make sure both valid and invalid data are handled correctly). That way you can test the client code that is accessing the...
0
9901
marktang
by: marktang | last post by:
ONU (Optical Network Unit) is one of the key components for providing high-speed Internet services. Its primary function is to act as an endpoint device located at the user's premises. However, people are often confused as to whether an ONU can Work As a Router. In this blog post, we’ll explore What is ONU, What Is Router, ONU & Router’s main usage, and What is the difference between ONU and Router. Let’s take a closer look ! Part I. Meaning of...
0
11024
Oralloy
by: Oralloy | last post by:
Hello folks, I am unable to find appropriate documentation on the type promotion of bit-fields when using the generalised comparison operator "<=>". The problem is that using the GNU compilers, it seems that the internal comparison operator "<=>" tries to promote arguments from unsigned to signed. This is as boiled down as I can make it. Here is my compilation command: g++-12 -std=c++20 -Wnarrowing bit_field.cpp Here is the code in...
0
10675
jinu1996
by: jinu1996 | last post by:
In today's digital age, having a compelling online presence is paramount for businesses aiming to thrive in a competitive landscape. At the heart of this digital strategy lies an intricately woven tapestry of website design and digital marketing. It's not merely about having a website; it's about crafting an immersive digital experience that captivates audiences and drives business growth. The Art of Business Website Design Your website is...
1
10749
by: Hystou | last post by:
Overview: Windows 11 and 10 have less user interface control over operating system update behaviour than previous versions of Windows. In Windows 11 and 10, there is no way to turn off the Windows Update option using the Control Panel or Settings app; it automatically checks for updates and installs any it finds, whether you like it or not. For most users, this new feature is actually very convenient. If you want to control the update process,...
0
9512
agi2029
by: agi2029 | last post by:
Let's talk about the concept of autonomous AI software engineers and no-code agents. These AIs are designed to manage the entire lifecycle of a software development project—planning, coding, testing, and deployment—without human intervention. Imagine an AI that can take a project description, break it down, write the code, debug it, and then launch it, all on its own.... Now, this would greatly impact the work of software developers. The idea...
1
7912
isladogs
by: isladogs | last post by:
The next Access Europe User Group meeting will be on Wednesday 1 May 2024 starting at 18:00 UK time (6PM UTC+1) and finishing by 19:30 (7.30PM). In this session, we are pleased to welcome a new presenter, Adolph Dupré who will be discussing some powerful techniques for using class modules. He will explain when you may want to use classes instead of User Defined Types (UDT). For example, to manage the data in unbound forms. Adolph will...
0
7079
by: conductexam | last post by:
I have .net C# application in which I am extracting data from word file and save it in database particularly. To store word all data as it is I am converting the whole word file firstly in HTML and then checking html paragraph one by one. At the time of converting from word file to html my equations which are in the word document file was convert into image. Globals.ThisAddIn.Application.ActiveDocument.Select();...
0
5740
by: TSSRALBI | last post by:
Hello I'm a network technician in training and I need your help. I am currently learning how to create and manage the different types of VPNs and I have a question about LAN-to-LAN VPNs. The last exercise I practiced was to create a LAN-to-LAN VPN between two Pfsense firewalls, by using IPSEC protocols. I succeeded, with both firewalls in the same network. But I'm wondering if it's possible to do the same thing, with 2 Pfsense firewalls...
0
5939
by: adsilva | last post by:
A Windows Forms form does not have the event Unload, like VB6. What one acts like?

By using Bytes.com and it's services, you agree to our Privacy Policy and Terms of Use.

To disable or enable advertisements and analytics tracking please visit the manage ads & tracking page.