445,750 Members | 1,199 Online Need help? Post your question and get tips & solutions from a community of 445,750 IT Pros & Developers. It's quick & easy.

# extract "set" bits including position from unsigned long

 P: n/a 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 Jul 22 '05 #1
7 Replies

 P: n/a "William Payne" wrote in message news:cg**********@news.island.liu.se... 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 Will this work? for(unsigned long i = 1; i <= sizeof(unsigned long) / 8; i+=i) { if(i & styles) { map::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 / WP Jul 22 '05 #2

 P: n/a "William Payne" wrote in message news:cg**********@news.island.liu.se... "William Payne" wrote in message news:cg**********@news.island.liu.se... 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 Will this work? for(unsigned long i = 1; i <= sizeof(unsigned long) / 8; i+=i) { if(i & styles) { map::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 / WP No, it won't. =) But is this correct: unsigned long i = 1; for(unsigned long n = 0; n < 32; ++n) { if(i & styles) { map::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 / WP Jul 22 '05 #3

 P: n/a "William Payne" wrote in message news:cg**********@news.island.liu.se... 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 #include #include #include #include #include #include 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& results) { results.clear(); unsigned int bit(std::numeric_limits::digits - 1); unsigned long component(pwr(2, std::numeric_limits::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::digits + 1); std::streamsize d_wid(std::numeric_limits::digits10 + 2); double lim(std::numeric_limits::max()); double val(0); unsigned long test(0); std::vector 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::const_iterator it(values.begin()); std::vector::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 Jul 22 '05 #5

 P: n/a "Mike Wahler" wrote in message news:iK******************@newsread1.news.pas.earth link.net... "William Payne" wrote in message news:cg**********@news.island.liu.se... 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 #include #include #include #include #include #include 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& results) { results.clear(); unsigned int bit(std::numeric_limits::digits - 1); unsigned long component(pwr(2, std::numeric_limits::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::digits + 1); std::streamsize d_wid(std::numeric_limits::digits10 + 2); double lim(std::numeric_limits::max()); double val(0); unsigned long test(0); std::vector 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::const_iterator it(values.begin()); std::vector::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 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 Jul 22 '05 #6

 P: n/a "William Payne" wrote: 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. while (x) { unsigned long next = x - (x & (x-1)); foo(next); x &= ~next; } Jul 22 '05 #7

 P: n/a William Payne wrote: 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 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 Jul 22 '05 #8

### This discussion thread is closed

Replies have been disabled for this discussion. 