Advertisement

03.11.2008 at 11:39AM PDT, ID: 23232803
[x]
Attachment Details
[x]
The Solution Rating System

With so many solutions, how can you tell which solutions are most likely to help you and which ones are not? To provide you with a tool to use, we rate our solutions based on various elements that most accurately determine if a solution is a quality solution. To explain what factors affect the solution rating, here are the elements we take into consideration when formulating our solution rating.

  • The Grade of the Solution
  • The Zone Rank of the Expert Providing the Solution
  • The Number of Author and Expert Comments
  • The Number of Experts Contributing
  • The Feedback of the Community

Your Input Matters
Because of the way the system is set up, the most important variable in this equation is you. As a member of Experts Exchange, you are able to cast your vote on the quality of the solutions in regard to how complete, accurate, helpful and easy to understand each solution is. When you provide your feedback, each rating is adjusted accordingly. So, if you see a solution that has a poor rating that you think is a good solution, let us know by rating it. As you do, the rating will be adjusted and will become more accurate for other members of our site.

If you have any suggestions that you would like to make for our rating system, please ask a question in the Suggestions Zone of Community Support.

Thank you!

Question about bitfield

Tags: C C++
Is there a simple way to check a bitfield of an undefined unsigned integer type to see if one and only one bit is set? This test will be done repeatedly and needs to be part of a high performance solution so, ideally, I'm not looking for a solution that finds the size of the type and then enumerate the bits; rather, I'm wondering if there is some clever binary maths trick I can perform.

Thanks.
Start your free trial to view this solution
Question Stats
Zone: Programming
Question Asked By: evilrix
Solution Provided By: ozo
Participating Experts: 5
Solution Grade: A
Views: 24
Translate:
Loading Advertisement...
03.11.2008 at 11:47AM PDT, ID: 21098743

Rank: Sage

All comments and solutions are available to Premium Service Members only.

Start your 7 day free trial and see for yourself why Experts Exchange is the easiest and most proven technology resource in the world. Get Started

Already a member? Login to view this solution.

 
03.11.2008 at 11:49AM PDT, ID: 21098764

Rank: Guru

All comments and solutions are available to Premium Service Members only.

Start your 7 day free trial and see for yourself why Experts Exchange is the easiest and most proven technology resource in the world. Get Started

Already a member? Login to view this solution.

 
03.11.2008 at 11:52AM PDT, ID: 21098796

All comments and solutions are available to Premium Service Members only.

Start your 7 day free trial and see for yourself why Experts Exchange is the easiest and most proven technology resource in the world. Get Started

Already a member? Login to view this solution.

 
03.11.2008 at 11:56AM PDT, ID: 21098832

Rank: Guru

All comments and solutions are available to Premium Service Members only.

Start your 7 day free trial and see for yourself why Experts Exchange is the easiest and most proven technology resource in the world. Get Started

Already a member? Login to view this solution.

 
03.11.2008 at 12:02PM PDT, ID: 21098901

Rank: Genius

All comments and solutions are available to Premium Service Members only.

Start your 7 day free trial and see for yourself why Experts Exchange is the easiest and most proven technology resource in the world. Get Started

Already a member? Login to view this solution.

 
03.11.2008 at 12:03PM PDT, ID: 21098905

All comments and solutions are available to Premium Service Members only.

Start your 7 day free trial and see for yourself why Experts Exchange is the easiest and most proven technology resource in the world. Get Started

Already a member? Login to view this solution.

 
03.11.2008 at 12:06PM PDT, ID: 21098928

All comments and solutions are available to Premium Service Members only.

Start your 7 day free trial and see for yourself why Experts Exchange is the easiest and most proven technology resource in the world. Get Started

Already a member? Login to view this solution.

 
03.11.2008 at 12:07PM PDT, ID: 21098940

Rank: Wizard

All comments and solutions are available to Premium Service Members only.

Start your 7 day free trial and see for yourself why Experts Exchange is the easiest and most proven technology resource in the world. Get Started

Already a member? Login to view this solution.

 
03.11.2008 at 12:14PM PDT, ID: 21099005

Rank: Sage

All comments and solutions are available to Premium Service Members only.

Start your 7 day free trial and see for yourself why Experts Exchange is the easiest and most proven technology resource in the world. Get Started

Already a member? Login to view this solution.

 
03.11.2008 at 12:20PM PDT, ID: 21099079

Rank: Wizard

All comments and solutions are available to Premium Service Members only.

Start your 7 day free trial and see for yourself why Experts Exchange is the easiest and most proven technology resource in the world. Get Started

Already a member? Login to view this solution.

 
03.11.2008 at 12:23PM PDT, ID: 21099103

All comments and solutions are available to Premium Service Members only.

Start your 7 day free trial and see for yourself why Experts Exchange is the easiest and most proven technology resource in the world. Get Started

Already a member? Login to view this solution.

 
03.11.2008 at 12:23PM PDT, ID: 21099110

Rank: Wizard

All comments and solutions are available to Premium Service Members only.

Start your 7 day free trial and see for yourself why Experts Exchange is the easiest and most proven technology resource in the world. Get Started

Already a member? Login to view this solution.

 
03.11.2008 at 12:26PM PDT, ID: 21099129

All comments and solutions are available to Premium Service Members only.

Start your 7 day free trial and see for yourself why Experts Exchange is the easiest and most proven technology resource in the world. Get Started

Already a member? Login to view this solution.

 
03.11.2008 at 12:26PM PDT, ID: 21099131

Rank: Genius

All comments and solutions are available to Premium Service Members only.

Start your 7 day free trial and see for yourself why Experts Exchange is the easiest and most proven technology resource in the world. Get Started

Already a member? Login to view this solution.

 
03.11.2008 at 12:48PM PDT, ID: 21099374

Rank: Sage

All comments and solutions are available to Premium Service Members only.

Start your 7 day free trial and see for yourself why Experts Exchange is the easiest and most proven technology resource in the world. Get Started

Already a member? Login to view this solution.

 
03.11.2008 at 01:01PM PDT, ID: 21099516

All comments and solutions are available to Premium Service Members only.

Start your 7 day free trial and see for yourself why Experts Exchange is the easiest and most proven technology resource in the world. Get Started

Already a member? Login to view this solution.

 
03.11.2008 at 02:17PM PDT, ID: 21100473

All comments and solutions are available to Premium Service Members only.

Start your 7 day free trial and see for yourself why Experts Exchange is the easiest and most proven technology resource in the world. Get Started

Already a member? Login to view this solution.

 
 
Loading Advertisement...
Microsoft
  • Internet Protocols
  • Applications
  • Development
  • OS
  • Hardware
  • Windows Security
Apple
  • Operating Systems
  • Hardware
  • Programming
  • Networking
  • Software
Internet
  • Search Engines
  • File Sharing
  • WebTrends / Stats
  • Spy / Ad Blockers
  • Web Browsers
  • New Net Users
  • Web Development
  • Chat / IM
  • Anti Spam
  • Web Servers
  • Anti-Virus
  • Email Clients
Gamers
  • Tips
  • Online / MMORPG
  • Puzzle
  • Emulators
  • Action / Adventure
  • Role Playing
  • Consoles
  • Game Programming
  • Strategy
  • Sports
  • Misc
  • Computer Games
Digital Living
  • Hardware
  • New Net Users
  • New Users
  • Software
  • Digital Music
  • Gaming World
  • Home Security
  • Apple
  • Networking Hardware
Virus & Spyware
  • Vulnerabilities
  • IDS
  • Encryption
  • Anti-Virus
  • Operating Systems Security
  • Software Firewalls
  • WebApplications
  • Cell Phones
  • Operating Systems
  • Internet
  • Hardware Firewalls
Hardware
  • Handhelds / PDAs
  • Displays / Monitors
  • Components
  • Networking Hardware
  • Peripherals
  • Laptops/Notebooks
  • Storage
  • Servers
  • Desktops
  • New Users
  • Misc
  • Apple
Software
  • System Utilities
  • Industry Specific
  • Network Management
  • Photos / Graphics
  • Page Layout
  • VMWare
  • Misc
  • Web Development
  • OS
  • CYGWIN
  • Voice Recognition
  • Message Queue
  • Quality Assurance
  • Security
  • Firewalls
  • MultiMedia Applications
  • Development
  • Database
  • Office / Productivity
  • Business Management
  • OS/2 Apps
  • Server Software
  • Internet / Email
ITPro
  • OS
  • Storage
  • Encryption
  • Operating Systems Security
  • Apple Hardware
  • Laptops & Notebooks
  • Servers
  • Networking Hardware
  • Peripherals
  • Devices
  • Displays / Monitors
  • WebTrends / Stats
  • Search Engines
  • Firewalls
  • WebApplications
  • IDS
  • Vulnerabilities
  • Email Clients
  • File Sharing
  • Spy / Ad Blockers
  • Web Browsers
  • Web Servers
  • Networking
  • Anti-Virus
  • Chat / IM
  • Anti Spam
Developer
  • Web Servers
  • Web Browsers
  • Game Programming
  • Dev Tools
  • Industry Specific
  • Office / Productivity
  • Database
  • CYGWIN
  • Web Development
  • Search Engines
  • File Sharing
  • WebTrends / Stats
  • Programming
  • Content Management
  • Application Servers
  • Protocols
Storage
  • Removable Backup Media
  • Storage Technology
  • Servers
  • Grid
  • Remote Access
  • Backup / Restore
  • Misc
  • Hard Drives
OS
  • Miscellaneous
  • Security
  • Development
  • Linux
  • VMWare
  • MainFrame OS
  • Unix
  • Apple
  • OS / 2
  • AS / 400
  • BeOS
  • Microsoft
  • VMS / OpenVMS
Database
  • Oracle
  • Miscellaneous
  • MySQL
  • Software
  • Sybase
  • Contact Management
  • PostgreSQL
  • Data Manipulation
  • Clarion
  • InterSystems Cache
  • Siebel
  • MUMPS
  • OLAP
  • SQLBase
  • SAS
  • GIS & GPS
  • 4GL
  • Berkeley DB
  • DB2
  • Informix
  • Interbase / Firebird
  • FoxPro
  • Reporting
  • LDAP
  • Filemaker Pro
  • MS SQL Server
  • dBase
  • MS Access
Security
  • Misc
  • Web Browsers
  • Software Firewalls
  • Operating Systems Security
  • File Sharing
  • Spy / Ad Blockers
  • Vulnerabilities
  • WebApplications
  • IDS
  • Anti-Virus
  • Encryption
  • Anti Spam
  • Email Clients
  • VPN
  • Chat / IM
Programming
  • Editors IDEs
  • Installation
  • Handhelds / PDAs
  • Multimedia Programming
  • System / Kernel
  • Algorithms
  • Game
  • Signal Processing
  • Project Management
  • Open Source
  • Database
  • Misc
  • Languages
  • Processor Platforms
  • Theory
Web Development
  • Scripting
  • Blogs
  • Web Servers
  • Software
  • Search Engines
  • Web Graphics
  • Images
  • Internet Marketing
  • Images and Photos
  • Components
  • Document Imaging
  • Web Languages/Standards
  • Illustration
  • WebApplications
  • Fonts
  • WebTrends / Stats
  • Authoring
  • Digital Camera Software
  • Miscellaneous
Networking
  • Protocols
  • Apple Networking
  • Network Management
  • Message Queue
  • Application Servers
  • Content Management
  • File Servers
  • Email Servers
  • Misc
  • Java Editors & IDEs
  • Wireless
  • Networking Hardware
  • Backup / Restore
  • System Utilities
  • ISPs & Hosting
  • Web Servers
  • Storage Technology
  • Removable Backup Media
  • Servers
  • Broadband
  • Grid
  • OS / 2
  • Novell Netware
  • Unix Networking
  • Windows Networking
  • Security
  • Telecommunications
  • Operating Systems
  • Linux Networking
Other
  • Community Advisor
  • Lounge
  • Community Support
  • New Net Users
  • Philosophy / Religion
  • Math / Science
  • Miscellaneous
  • URLs
  • Expert Lounge
  • Politics
  • Puzzles / Riddles
Community Support
  • Suggestions
  • New to EE
  • New Topics
  • Community Advisor
  • CleanUp
  • Announcements
  • General
  • Feedback
  • Input
  • EE Bugs
 
03.11.2008 at 11:47AM PDT, ID: 21098743

Rank: Sage

Hi evilrix,

Yep.  :)

  unsigned int Word;
  unsigned int Test;
  unsigned int Comp;

  Test = Word - 1;       //  If word contains exactly 1 bit, Test will be all bits to the right of the original bit.
  Comp = ~Word;        //  Bit complement of the original value.
  if ((Comp & Test) + 1 == Word)
   //  Only one bit in the original value was set.


Good Luck,
Kent
 
03.11.2008 at 11:49AM PDT, ID: 21098764

Rank: Guru

sure .. here is one ..


ike
1:
2:
3:
4:
5:
bool testBit( unsigned int bitField, int bitIndex )
{
    unsigned int mask = 1 << bitIndex;
    return bitField & mask;
}
Open in New Window
 
03.11.2008 at 11:52AM PDT, ID: 21098796
Hi Kent (good to see)
Just looking at that now, thanks.

Hi, Ikework.
I don't mean a specific bit, I mean any bit. I need to know if more than one bit is set.
 
03.11.2008 at 11:56AM PDT, ID: 21098832

Rank: Guru

ah i see .. interesting .. ;)
 
03.11.2008 at 12:02PM PDT, ID: 21098901

Rank: Genius

>>I don't mean a specific bit, I mean any bit

Can you live with an 'union' construct? I.e.
1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
11:
12:
13:
14:
15:
16:
17:
18:
19:
20:
21:
22:
23:
24:
#include <stdio.h>
 
union mybitfield
{
  struct 
  {
      unsigned short a : 4;
      unsigned short b : 5;
      unsigned short c : 7;
  } field;
 
  unsigned short value;
};
 
void main ()
{
 
  mybitfield bf;
 
  bf.field.a = 1;
 
  if (bf.value != 0) printf("Some bit is set\n");  
 
}
Open in New Window
 
03.11.2008 at 12:03PM PDT, ID: 21098905
>> interesting
Indeed... I spent all day thinking about it. The best I came up with was a switch/case for all the valid values but (a) it's not extensible and (b) it's not very elegant. There must be a simple way but I'm damed if I can think of one  :)

Kent, Are you sure that works? I tried it (see below) and it didn't give me the results I'd expect. Have I implemented your formula incorrectly?

Cheers guys,

-Rx.
1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
11:
12:
13:
14:
15:
16:
17:
18:
#include <cassert>
 
template <typename T>
bool test(T const & x)
{
	T y = x - 1;
	T z = ~y;
 
	return ((z & y) + 1) == x;
}
 
int main()
{
	assert(test(1)); // 1 bit
	assert(test(2)); // 1 bit
	assert(!test(3)); // 2 bits
	assert(test(4)); // 1 bit
}
Open in New Window
 
03.11.2008 at 12:06PM PDT, ID: 21098928
>> Can you live with an 'union' construct
Unfortunately, it'll need to be an extensible solution that works with any intrinsic type that doesn't rely on the structure of any other type (the type will be templated so unknown).
 
03.11.2008 at 12:07PM PDT, ID: 21098940

Rank: Wizard

word && !(word & (word-1))
Accepted Solution
 
03.11.2008 at 12:14PM PDT, ID: 21099005

Rank: Sage

Hi evilrix,

One line appears off.  :)   You want the complement of the original value.

  T z = ~x;


Good Luck,
Kent
 
03.11.2008 at 12:20PM PDT, ID: 21099079

Rank: Wizard

       T z = ~y;
should have been
        T z = ~x;
but it still fails on
        assert(!test(0)); // 0 bit
 
03.11.2008 at 12:23PM PDT, ID: 21099103
>> word && !(word & (word-1))
Seems to work, um would you mind explaining how please? :)
 
03.11.2008 at 12:23PM PDT, ID: 21099110

Rank: Wizard

bool test(T const & x)
{
        return x && !(x&(x-1));
}
 
03.11.2008 at 12:26PM PDT, ID: 21099129
ozo, yup that seems to work a treat... but I would like to understand it... for the purposes of an explanation please feel free to assume I am an idiot :)
1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
11:
12:
13:
14:
15:
16:
#include <cassert>
 
template <typename T>
bool test(T const & x)
{
	return x && !(x & (x-1));
}
 
int main()
{
	assert(!test(0)); // 0 bit
	assert(test(1)); // 1 bit
	assert(test(2)); // 1 bit
	assert(!test(3)); // 2 bits
	assert(test(4)); // 1 bit
}
Open in New Window
 
03.11.2008 at 12:26PM PDT, ID: 21099131

Rank: Genius

In that case, some "brute force" might help, e.g.

1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
11:
12:
13:
14:
template<typename T, int n>
struct mybitfield {
 
  T a : n;
  T b : n;
};
 
template<typename T,n>
bool test_any(const mybitfield<T,n>& bf) {
 
  T* pt = (T*) &bf;
 
  return *t != 0;
};
Open in New Window
 
03.11.2008 at 12:48PM PDT, ID: 21099374

Rank: Sage

Hi evilrix,

Both the algorithms do basicallly the same thing.  Mine didn't test for zero, as did jkr's.

  return x && !(x & (x - 1))
            ^  if zero, return false.

          !(x & (x - 1))

       x - 1            -- all bits to the right of the lowest order bit.  (If x contains only 1 bit, all bits to the right of that bit.)
     x & (x - 1)     -- if x contains only 1 bit, x and (x-1) will contain no bits in common.  If x contains multiple bits, x and (x-1) will contain common bits

   return x {test for zero} && !(x & (x - 1))  {complement of whether common bits were found comparing x and (x-1)}


Good Luck,
Kent
Assisted Solution
 
03.11.2008 at 01:01PM PDT, ID: 21099516
Ok, thanks all. I need to digest :)

I'll get back to this later with either more Qs (to aid understanding) or I'll close.

-Rx.
 
03.11.2008 at 02:17PM PDT, ID: 21100473
Right, I had to think about it for a bit but I got there in the end. Thanks ozo and Kent (and the others who offer a solution)... I knew there must be a simple (once you get it) way. Oh how I wish I'd been gifted with such numerical abilities :)
 
 
03.12.2008 at 01:52AM PDT, ID: 21103980
>> Oh how I wish I'd been gifted with such numerical abilities :)

me too rx .. i'm always blown away by the elegance of such numerical solutions.
i hope you dont mind, if i expand your question a bit ;)

guys, is that solution expandable to more than 2 bits? what about 3, 4, 5 etc.. or is that some kind of singular solution for 2 bits?


ike
 
 
03.12.2008 at 02:02AM PDT, ID: 21104021
>>  i'm always blown away by the elegance of such numerical solutions.
You and I both ike :)

>> i hope you dont mind, if i expand your question a bit ;)
No worries... go for it, it's all good info :)
 
 
03.12.2008 at 02:04AM PDT, ID: 21104036
ike, it's a solution that works just for 1 bit. Having one bit set in an integer means that it has a "special" feature : if you subtract 1 from the integer, then all bits to the right of the set bit will be set. For example :

        8   --->    00001000
        7   --->    00000111

which means that doing a binary AND of these two values will always yield 0 :

        8   --->    00001000
        7   --->    00000111
               &      -------------
                       00000000

This is not the case when more than 1 bit is set. For example :

        A   --->    00001010
        9   --->    00001001
               &      -------------
                       00001000

which is not 0.

The formula is based on this feature :

        if (x & (x - 1)) {
            /* more than one bit is set */
        }
        else {
            /* one or zero bits are set */
        }

Now, there's only one flaw : it still detects x = 0, so we need to add another check for that special value :

        if (x && !(x & (x - 1))) {
            /* exactly one bit is set */
        }
        else {
            /* more or less than 1 bit is set */
        }
 
 
03.12.2008 at 02:10AM PDT, ID: 21104063
Hey, that's exactly how I understood it but many thanks for taking the time to clarify it I8. As usual, your ability to explain things clearly and in simple terms is exemplary.

It's amazing just how simple it is when you know the algo... I can't believe I spent all day thinking about this and didn't come up with that :(

-Rx.
 
 
03.12.2008 at 02:42AM PDT, ID: 21104196
thanks from me too infinity, clear and simple .. beautiful .. :)
 
 
03.12.2008 at 02:56AM PDT, ID: 21104267
Note that for consecutive bits, you can do something similar : let's say we want to check if n consecutive bits are set, then we can use something like the following. The only problem I have with it is the MASK macro which is called twice in IS_N_BITS_SET. But there are ways to avoid that ;)

1:
2:
3:
4:
5:
6:
7:
8:
9:
#define MASK(n)             ((0x01 << (n)) - 1)
#define IS_1_BIT_SET(x)     ((x) && !((x) & ((x) - 1)))
#define IS_N_BITS_SET(x, n) (!((x) % MASK(n)) && IS_1_BIT_SET((x) / MASK(n)))
 
 
unsigned int value;              /* some value */
if (IS_N_BITS_SET(value, 3)) {
    /* 3 consecutive bits are set in value */
}
Open in New Window
 
 
03.12.2008 at 03:02AM PDT, ID: 21104301
/me is lost :(
 
 
03.12.2008 at 03:08AM PDT, ID: 21104328
great .. added to my KnowledgeBase questions .. :)
 
 
03.12.2008 at 03:24AM PDT, ID: 21104415
>> /me is lost :(

Sorry :)

Some explanation is in order I guess ...

MASK(n) will create a bitmap of n consecutive bits. So, if n is 3, then MASK(n) will be :

        00000111

The part !((x) % MASK(n)) will just check if the value x is divisible by that mask. We don't want to treat values that are not divisible by the mask (they won't have n consecutive bits set anyway).

Then we simply divide x by the mask to reduce the n consecutive bits to just 1 bit. For example, for 3 bits :

        00011100
    /   00000111
        -------------
        00000100

We can now use the same algorithm as before to see if exactly 1 bit is set or not by calling the IS_1_BIT_SET macro.

The reason this works, is because if no 3 consecutive bits are set (and it's still divisible by 7), then we get this :

        00010101         (21)
    /   00000111         (the 3-bit mask : 7)
        -------------
        00000011         (3)

and the IS_1_BIT_SET macro will return false.

If we have 3 consecutive bits set, plus one or more extra bits somewhere else (and it's still divisible by 7), then we get :

        10111101         (189)
    /   00000111         (the 3-bit mask : 7)
        -------------
        00011011         (27)

and the IS_1_BIT_SET macro will return false.
 
 
03.12.2008 at 03:27AM PDT, ID: 21104429
Be aware that this only works for consecutive bits :)
 
 
03.12.2008 at 03:34AM PDT, ID: 21104462
I think I need to read this a few times and digest! :-S

I get there in the end, it just takes time -- I'm like a computer, sometimes information just needs to be punched in :)

I'll read this again when I get home from work and have a little thinking session.

Ta very much for taking the time to go over this I8, it is very much appreciated.

-Rx.
 
 
03.12.2008 at 03:55AM PDT, ID: 21104575
No problem at all ... This is fun ;)

Let me think if there's an easy way to detect multiple non-consecutive bits. I don't have high hopes for it though as there are so many possible patterns ...
 
 
03.12.2008 at 04:08AM PDT, ID: 21104645
>> This is fun
Nutter :)

>> Let me think if there's an easy way to detect multiple non-consecutive bits
Please don't my brain hurtz enough as it is. I'm sure bit level maths isn't that hard really but numbers and I don't mix (I think I've said before I suffer with Dyscalculia) so it does take me a while to get there -- but I do get there :)
 
 
ozo
03.12.2008 at 04:32AM PDT, ID: 21104760
> multiple non-consecutive bits
//For 32 bit integers
count = (word&0x55555555)+((word>>1)&0x55555555);
count = (count&0x33333333)+((count>>2)&0x33333333);
count = (count+(count>>4))&0x0f0f0f0f);
count += count>>8;
return  ((count+(count>>16))&0x0000ff) == N;
 
 
ozo
03.12.2008 at 04:41AM PDT, ID: 21104807
If N is small
return x && (x&=x-1) && ... N-1 times ... && (x&=x-1) && !(x&=x-1)
 
 
 
20080236-EE-VQP-29 / EE_QW_EXPERT_20070906