extract "set" bits including position from unsigned long

W

William Payne

Hello, I have a variable of type unsigned long. It has a number of bits set
(with set I mean they equal one). I need to determine those bits and their
position and create new numbers from them. For example, consider this
four-bit number:
1100
from this number I want to extract two numbers:
1000 and 100
had the four-bit number been 0101 I would want to extract 100 and 1.

How should I do this? I wish I had some code to post but I don't right now
=/

These new numbers I will use to look-up strings in a map.

/ WP
 
W

William Payne

William Payne said:
Hello, I have a variable of type unsigned long. It has a number of bits
set (with set I mean they equal one). I need to determine those bits and
their position and create new numbers from them. For example, consider
this four-bit number:
1100
from this number I want to extract two numbers:
1000 and 100
had the four-bit number been 0101 I would want to extract 100 and 1.

How should I do this? I wish I had some code to post but I don't right now
=/

These new numbers I will use to look-up strings in a map.

/ WP
Click to expand...

Will this work?
for(unsigned long i = 1; i <= sizeof(unsigned long) / 8; i+=i)
{
if(i & styles)
{
map<unsigned long, string>::const_iterator pos;

pos = styles_map.find(i);

if(pos != styles_map.end())
{
cout << pos->second << endl;
}
}
}

styles is of type unsigned long and styles_map is map<unsigned long, string>

/ WP
 
W

William Payne

William Payne said:
Will this work?
for(unsigned long i = 1; i <= sizeof(unsigned long) / 8; i+=i)
{
if(i & styles)
{
map<unsigned long, string>::const_iterator pos;

pos = styles_map.find(i);

if(pos != styles_map.end())
{
cout << pos->second << endl;
}
}
}

styles is of type unsigned long and styles_map is map<unsigned long,
string>

/ WP
Click to expand...

No, it won't. =) But is this correct:

unsigned long i = 1;

for(unsigned long n = 0; n < 32; ++n)
{
if(i & styles)
{
map<unsigned long, string>::const_iterator pos;

pos = styles_map.find(i);

if(pos != styles_map.end())
{
cout << pos->second << endl;
}
}

i += i;
}

styles is of type unsigned long and styles_map is map<unsigned long, string>

/ WP
 
G

Gianni Mariani

William said:
No, it won't. =) But is this correct:

unsigned long i = 1;

for(unsigned long n = 0; n < 32; ++n)
{
if(i & styles)
{
map<unsigned long, string>::const_iterator pos;

pos = styles_map.find(i);

if(pos != styles_map.end())
{
cout << pos->second << endl;
}
}

i += i;
}

styles is of type unsigned long and styles_map is map<unsigned long, string>
Click to expand...

Please post compilable code. It makes it easier to help you.

What you wrote will probably work, however, consider this.


#include <iostream>
#include <string>
#include <limits>
#include <map>

using namespace std;
typedef unsigned long styles_bitmask_t;
typedef map<styles_bitmask_t, string> styles_map_t;

void scan_styles( styles_bitmask_t styles, styles_map_t & styles_map )
{

for(int i = 0; i < numeric_limits<styles_bitmask_t>::digits ; ++ i)
{
styles_bitmask_t mask_val = ( 1 << i );

if ( styles & mask_val )
{
map<unsigned long, string>::const_iterator pos;

pos = styles_map.find( mask_val );

if(pos != styles_map.end() )
{
cout << pos->second << endl;
}
}
}

}


int main()
{

styles_map_t s_map;

s_map[ 1 << 1 ] = "s1";
s_map[ 1 << 2 ] = "s2";
s_map[ 1 << 3 ] = "s3";
s_map[ 1 << 4 ] = "s4";
s_map[ 1 << 5 ] = "s5";
s_map[ 1 << 6 ] = "s6";

scan_styles( 0xa, s_map );
}

This probably does what you want.

Note that unsigned long might not be 32 bits. Using
numeric_limits<T>::digits eliminates that.

There is also a faster way to do this. There is a trivial way of
finding the first set bit in an integer type. This would use far less
cyles on sparse bit masks.

#include <iostream>
#include <string>
#include <limits>
#include <map>

using namespace std;
typedef unsigned long styles_bitmask_t;
typedef map<styles_bitmask_t, string> styles_map_t;

void scan_styles( styles_bitmask_t styles, styles_map_t & styles_map )
{

while ( styles )
{
styles_bitmask_t drop_first = styles & ( styles - 1 );

styles_bitmask_t first_set = styles ^ drop_first;

styles = drop_first;

map<unsigned long, string>::const_iterator pos;

pos = styles_map.find( first_set );

if(pos != styles_map.end() )
{
cout << pos->second << endl;
}
}

}


int main()
{

styles_map_t s_map;

s_map[ 1 << 1 ] = "s1";
s_map[ 1 << 2 ] = "s2";
s_map[ 1 << 3 ] = "s3";
s_map[ 1 << 4 ] = "s4";
s_map[ 1 << 5 ] = "s5";
s_map[ 1 << 6 ] = "s6";

scan_styles( 0xa, s_map );
}
 
M

Mike Wahler

William Payne said:
Hello, I have a variable of type unsigned long. It has a number of bits set
(with set I mean they equal one). I need to determine those bits and their
position and create new numbers from them. For example, consider this
four-bit number:
1100
from this number I want to extract two numbers:
1000 and 100
had the four-bit number been 0101 I would want to extract 100 and 1.

How should I do this? I wish I had some code to post but I don't right now
=/

These new numbers I will use to look-up strings in a map.

/ WP
Click to expand...

#include <iomanip>
#include <ios>
#include <iostream>
#include <limits>
#include <string>
#include <vector>

unsigned long pwr(unsigned long value, unsigned int exp)
{
unsigned long result(1);

while(exp--)
result *= value;

return result;
}

std::string bin(unsigned long value)
{
std::string result;
while(value)
{
result.insert(result.begin(), 1, char(value % 2 + '0'));
value /= 2;
}

return result;

}

void extract(unsigned long value, std::vector<unsigned long>& results)
{
results.clear();

unsigned int bit(std::numeric_limits<unsigned long>::digits - 1);

unsigned long
component(pwr(2, std::numeric_limits<unsigned long>::digits - 1));

do
{
std::cout << "Bit " << std::setw(2) << bit << " is";

if(value & component)
results.push_back(component);
else
std::cout << " not";

std::cout << " set\n";

--bit;

} while(component /= 2);

std::cout << '\n';
}

unsigned int which_pwr(unsigned long value)
{
unsigned int result(0);

while(value /= 2)
++result;

return result;
}

int main()
{
std::streamsize b_wid(std::numeric_limits<unsigned long>::digits + 1);
std::streamsize d_wid(std::numeric_limits<unsigned long>::digits10 + 2);
double lim(std::numeric_limits<unsigned long>::max());
double val(0);

unsigned long test(0);
std::vector<unsigned long> values;

for(val = 0; val <= lim; ++val)
{
test = unsigned long(val);

std::cout << "Input:\n"
<< std::setw(d_wid) << "decimal"
<< std::setw(b_wid) << "binary" << '\n'
<< std::setw(d_wid) << test
<< std::setw(b_wid) << bin(test)
<< "\n\n";

extract(test, values);

std::vector<unsigned long>::const_iterator it(values.begin());
std::vector<unsigned long>::const_iterator en(values.end());

std::cout << "Output:\n"
<< std::setw(d_wid) << "decimal"
<< std::setw(b_wid) << "binary" << '\n';

while(it != en)
{
std::cout << std::setw(d_wid) << *it
<< std::setw(b_wid) << bin(*it)
<< " (2 ^ " << which_pwr(*it) << ')'
<< '\n';

++it;
}

std::cout << "\n\n";

}

return 0;
}

Excerpt from output:
========================================================
Input:
decimal binary
330382094 10011101100010011101100001110

Bit 31 is not set
Bit 30 is not set
Bit 29 is not set
Bit 28 is set
Bit 27 is not set
Bit 26 is not set
Bit 25 is set
Bit 24 is set
Bit 23 is set
Bit 22 is not set
Bit 21 is set
Bit 20 is set
Bit 19 is not set
Bit 18 is not set
Bit 17 is not set
Bit 16 is set
Bit 15 is not set
Bit 14 is not set
Bit 13 is set
Bit 12 is set
Bit 11 is set
Bit 10 is not set
Bit 9 is set
Bit 8 is set
Bit 7 is not set
Bit 6 is not set
Bit 5 is not set
Bit 4 is not set
Bit 3 is set
Bit 2 is set
Bit 1 is set
Bit 0 is not set

Output:
decimal binary
268435456 10000000000000000000000000000 (2 ^ 28)
33554432 10000000000000000000000000 (2 ^ 25)
16777216 1000000000000000000000000 (2 ^ 24)
8388608 100000000000000000000000 (2 ^ 23)
2097152 1000000000000000000000 (2 ^ 21)
1048576 100000000000000000000 (2 ^ 20)
65536 10000000000000000 (2 ^ 16)
8192 10000000000000 (2 ^ 13)
4096 1000000000000 (2 ^ 12)
2048 100000000000 (2 ^ 11)
512 1000000000 (2 ^ 9)
256 100000000 (2 ^ 8)
8 1000 (2 ^ 3)
4 100 (2 ^ 2)
2 10 (2 ^ 1)


Input:
decimal binary
330382095 10011101100010011101100001111

Bit 31 is not set
Bit 30 is not set
Bit 29 is not set
Bit 28 is set
Bit 27 is not set
Bit 26 is not set
Bit 25 is set
Bit 24 is set
Bit 23 is set
Bit 22 is not set
Bit 21 is set
Bit 20 is set
Bit 19 is not set
Bit 18 is not set
Bit 17 is not set
Bit 16 is set
Bit 15 is not set
Bit 14 is not set
Bit 13 is set
Bit 12 is set
Bit 11 is set
Bit 10 is not set
Bit 9 is set
Bit 8 is set
Bit 7 is not set
Bit 6 is not set
Bit 5 is not set
Bit 4 is not set
Bit 3 is set
Bit 2 is set
Bit 1 is set
Bit 0 is set

Output:
decimal binary
268435456 10000000000000000000000000000 (2 ^ 28)
33554432 10000000000000000000000000 (2 ^ 25)
16777216 1000000000000000000000000 (2 ^ 24)
8388608 100000000000000000000000 (2 ^ 23)
2097152 1000000000000000000000 (2 ^ 21)
1048576 100000000000000000000 (2 ^ 20)
65536 10000000000000000 (2 ^ 16)
8192 10000000000000 (2 ^ 13)
4096 1000000000000 (2 ^ 12)
2048 100000000000 (2 ^ 11)
512 1000000000 (2 ^ 9)
256 100000000 (2 ^ 8)
8 1000 (2 ^ 3)
4 100 (2 ^ 2)
2 10 (2 ^ 1)
1 1 (2 ^ 0)


Input:
decimal binary
330382096 10011101100010011101100010000

Bit 31 is not set
Bit 30 is not set
Bit 29 is not set
Bit 28 is set
Bit 27 is not set
Bit 26 is not set
Bit 25 is set
Bit 24 is set
Bit 23 is set
Bit 22 is not set
Bit 21 is set
Bit 20 is set
Bit 19 is not set
Bit 18 is not set
Bit 17 is not set
Bit 16 is set
Bit 15 is not set
Bit 14 is not set
Bit 13 is set
Bit 12 is set
Bit 11 is set
Bit 10 is not set
Bit 9 is set
Bit 8 is set
Bit 7 is not set
Bit 6 is not set
Bit 5 is not set
Bit 4 is set
Bit 3 is not set
Bit 2 is not set
Bit 1 is not set
Bit 0 is not set

Output:
decimal binary
268435456 10000000000000000000000000000 (2 ^ 28)
33554432 10000000000000000000000000 (2 ^ 25)
16777216 1000000000000000000000000 (2 ^ 24)
8388608 100000000000000000000000 (2 ^ 23)
2097152 1000000000000000000000 (2 ^ 21)
1048576 100000000000000000000 (2 ^ 20)
65536 10000000000000000 (2 ^ 16)
8192 10000000000000 (2 ^ 13)
4096 1000000000000 (2 ^ 12)
2048 100000000000 (2 ^ 11)
512 1000000000 (2 ^ 9)
256 100000000 (2 ^ 8)
16 10000 (2 ^ 4)
========================================================

HTH,
-Mike
 
W

William Payne

Mike Wahler said:
#include <iomanip>
#include <ios>
#include <iostream>
#include <limits>
#include <string>
#include <vector>

unsigned long pwr(unsigned long value, unsigned int exp)
{
unsigned long result(1);

while(exp--)
result *= value;

return result;
}

std::string bin(unsigned long value)
{
std::string result;
while(value)
{
result.insert(result.begin(), 1, char(value % 2 + '0'));
value /= 2;
}

return result;

}

void extract(unsigned long value, std::vector<unsigned long>& results)
{
results.clear();

unsigned int bit(std::numeric_limits<unsigned long>::digits - 1);

unsigned long
component(pwr(2, std::numeric_limits<unsigned long>::digits - 1));

do
{
std::cout << "Bit " << std::setw(2) << bit << " is";

if(value & component)
results.push_back(component);
else
std::cout << " not";

std::cout << " set\n";

--bit;

} while(component /= 2);

std::cout << '\n';
}

unsigned int which_pwr(unsigned long value)
{
unsigned int result(0);

while(value /= 2)
++result;

return result;
}

int main()
{
std::streamsize b_wid(std::numeric_limits<unsigned long>::digits + 1);
std::streamsize d_wid(std::numeric_limits<unsigned long>::digits10 +
2);
double lim(std::numeric_limits<unsigned long>::max());
double val(0);

unsigned long test(0);
std::vector<unsigned long> values;

for(val = 0; val <= lim; ++val)
{
test = unsigned long(val);

std::cout << "Input:\n"
<< std::setw(d_wid) << "decimal"
<< std::setw(b_wid) << "binary" << '\n'
<< std::setw(d_wid) << test
<< std::setw(b_wid) << bin(test)
<< "\n\n";

extract(test, values);

std::vector<unsigned long>::const_iterator it(values.begin());
std::vector<unsigned long>::const_iterator en(values.end());

std::cout << "Output:\n"
<< std::setw(d_wid) << "decimal"
<< std::setw(b_wid) << "binary" << '\n';

while(it != en)
{
std::cout << std::setw(d_wid) << *it
<< std::setw(b_wid) << bin(*it)
<< " (2 ^ " << which_pwr(*it) << ')'
<< '\n';

++it;
}

std::cout << "\n\n";

}

return 0;
}

Excerpt from output:
========================================================
Input:
decimal binary
330382094 10011101100010011101100001110

Bit 31 is not set
Bit 30 is not set
Bit 29 is not set
Bit 28 is set
Bit 27 is not set
Bit 26 is not set
Bit 25 is set
Bit 24 is set
Bit 23 is set
Bit 22 is not set
Bit 21 is set
Bit 20 is set
Bit 19 is not set
Bit 18 is not set
Bit 17 is not set
Bit 16 is set
Bit 15 is not set
Bit 14 is not set
Bit 13 is set
Bit 12 is set
Bit 11 is set
Bit 10 is not set
Bit 9 is set
Bit 8 is set
Bit 7 is not set
Bit 6 is not set
Bit 5 is not set
Bit 4 is not set
Bit 3 is set
Bit 2 is set
Bit 1 is set
Bit 0 is not set

Output:
decimal binary
268435456 10000000000000000000000000000 (2 ^ 28)
33554432 10000000000000000000000000 (2 ^ 25)
16777216 1000000000000000000000000 (2 ^ 24)
8388608 100000000000000000000000 (2 ^ 23)
2097152 1000000000000000000000 (2 ^ 21)
1048576 100000000000000000000 (2 ^ 20)
65536 10000000000000000 (2 ^ 16)
8192 10000000000000 (2 ^ 13)
4096 1000000000000 (2 ^ 12)
2048 100000000000 (2 ^ 11)
512 1000000000 (2 ^ 9)
256 100000000 (2 ^ 8)
8 1000 (2 ^ 3)
4 100 (2 ^ 2)
2 10 (2 ^ 1)


Input:
decimal binary
330382095 10011101100010011101100001111

Bit 31 is not set
Bit 30 is not set
Bit 29 is not set
Bit 28 is set
Bit 27 is not set
Bit 26 is not set
Bit 25 is set
Bit 24 is set
Bit 23 is set
Bit 22 is not set
Bit 21 is set
Bit 20 is set
Bit 19 is not set
Bit 18 is not set
Bit 17 is not set
Bit 16 is set
Bit 15 is not set
Bit 14 is not set
Bit 13 is set
Bit 12 is set
Bit 11 is set
Bit 10 is not set
Bit 9 is set
Bit 8 is set
Bit 7 is not set
Bit 6 is not set
Bit 5 is not set
Bit 4 is not set
Bit 3 is set
Bit 2 is set
Bit 1 is set
Bit 0 is set

Output:
decimal binary
268435456 10000000000000000000000000000 (2 ^ 28)
33554432 10000000000000000000000000 (2 ^ 25)
16777216 1000000000000000000000000 (2 ^ 24)
8388608 100000000000000000000000 (2 ^ 23)
2097152 1000000000000000000000 (2 ^ 21)
1048576 100000000000000000000 (2 ^ 20)
65536 10000000000000000 (2 ^ 16)
8192 10000000000000 (2 ^ 13)
4096 1000000000000 (2 ^ 12)
2048 100000000000 (2 ^ 11)
512 1000000000 (2 ^ 9)
256 100000000 (2 ^ 8)
8 1000 (2 ^ 3)
4 100 (2 ^ 2)
2 10 (2 ^ 1)
1 1 (2 ^ 0)


Input:
decimal binary
330382096 10011101100010011101100010000

Bit 31 is not set
Bit 30 is not set
Bit 29 is not set
Bit 28 is set
Bit 27 is not set
Bit 26 is not set
Bit 25 is set
Bit 24 is set
Bit 23 is set
Bit 22 is not set
Bit 21 is set
Bit 20 is set
Bit 19 is not set
Bit 18 is not set
Bit 17 is not set
Bit 16 is set
Bit 15 is not set
Bit 14 is not set
Bit 13 is set
Bit 12 is set
Bit 11 is set
Bit 10 is not set
Bit 9 is set
Bit 8 is set
Bit 7 is not set
Bit 6 is not set
Bit 5 is not set
Bit 4 is set
Bit 3 is not set
Bit 2 is not set
Bit 1 is not set
Bit 0 is not set

Output:
decimal binary
268435456 10000000000000000000000000000 (2 ^ 28)
33554432 10000000000000000000000000 (2 ^ 25)
16777216 1000000000000000000000000 (2 ^ 24)
8388608 100000000000000000000000 (2 ^ 23)
2097152 1000000000000000000000 (2 ^ 21)
1048576 100000000000000000000 (2 ^ 20)
65536 10000000000000000 (2 ^ 16)
8192 10000000000000 (2 ^ 13)
4096 1000000000000 (2 ^ 12)
2048 100000000000 (2 ^ 11)
512 1000000000 (2 ^ 9)
256 100000000 (2 ^ 8)
16 10000 (2 ^ 4)
========================================================

HTH,
-Mike
Click to expand...

Hehe, yeah, that helps! I already had a crude but working version but it's
nice to see someone putting alot of effort into helping a complete stranger!

/ WP
 
O

Old Wolf

William Payne said:
Hello, I have a variable of type unsigned long. It has a number of bits set
(with set I mean they equal one). I need to determine those bits and their
position and create new numbers from them. For example, consider this
four-bit number:
1100
from this number I want to extract two numbers:
1000 and 100
had the four-bit number been 0101 I would want to extract 100 and 1.
Click to expand...

while (x)
{
unsigned long next = x - (x & (x-1));
foo(next);
x &= ~next;
}
 
P

Peter Ammon

William said:
Hello, I have a variable of type unsigned long. It has a number of bits set
(with set I mean they equal one). I need to determine those bits and their
position and create new numbers from them. For example, consider this
four-bit number:
1100
from this number I want to extract two numbers:
1000 and 100
had the four-bit number been 0101 I would want to extract 100 and 1.

How should I do this? I wish I had some code to post but I don't right now
=/

These new numbers I will use to look-up strings in a map.

/ WP
Click to expand...

The solutions that I've seen posted so far are all O(N) in the number of
bits in an unsigned long. That stinks.

Here's a pair of skeleton solutions that's linear in the number of SET
bits instead of the total number of bits. Use whichever you prefer.

void generate_set_bits_1(unsigned long val) {
while (val) {
unsigned mask = val & (val - 1);
unsigned result = mask ^ val;
cout << result << endl;
val = mask;
}
}

void generate_set_bits_2(unsigned long val) {
while (val) {
cout << ((1 + (val ^ (val - 1))) >> 1) << endl;
val = val & (val - 1);
}
}

-Peter
 

Ask a Question

Want to reply to this thread or ask your own question?

You'll need to choose a username for the site, which only take a couple of moments. After that, you can post your question and our members will help you out.

Ask a Question

Similar Threads

Any integer number is always 32 bits 2
Data saving in condition of changing reality 0
How to extract certain set of lines from PDF 3
streampos difficulties, tellg() > numeric_limits<unsigned long int>::max() 1
printing bits ... the right way 2
C macro to declare unsigned long from "ABCD" 16
Question about bits (debugging> 11
Extract 5 bits at a time from a stl string 4

Members online

No members online now.
Total: 28 (members: 0, guests: 28)
Robots: 460

Forum statistics

Threads
473,768
Messages
2,569,574
Members
45,051
Latest member
CarleyMcCr

Latest Threads

Top