extract "set" bits including position from unsigned long

Discussion in 'C++' started by William Payne, Aug 22, 2004.

  1. 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
     
    William Payne, Aug 22, 2004
    #1
    1. Advertising

  2. "William Payne" <> wrote in message
    news:cga4eq$8bp$...
    > 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<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
     
    William Payne, Aug 22, 2004
    #2
    1. Advertising

  3. "William Payne" <> wrote in message
    news:cga5de$8g1$...
    >
    > "William Payne" <> wrote in message
    > news:cga4eq$8bp$...
    >> 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<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
    >


    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
     
    William Payne, Aug 22, 2004
    #3
  4. William Payne wrote:

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


    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 );
    }
     
    Gianni Mariani, Aug 22, 2004
    #4
  5. William Payne

    Mike Wahler Guest

    "William Payne" <> wrote in message
    news:cga4eq$8bp$...
    > 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 <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
     
    Mike Wahler, Aug 22, 2004
    #5
  6. "Mike Wahler" <> wrote in message
    news:iK4Wc.30428$...
    > "William Payne" <> wrote in message
    > news:cga4eq$8bp$...
    >> 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 <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
    >
    >


    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
     
    William Payne, Aug 22, 2004
    #6
  7. William Payne

    Old Wolf Guest

    "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;
    }
     
    Old Wolf, Aug 22, 2004
    #7
  8. William Payne

    Peter Ammon Guest

    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
     
    Peter Ammon, Aug 23, 2004
    #8
    1. Advertising

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

It takes just 2 minutes to sign up (and it's free!). Just click the sign up button to choose a username and then you can ask your own questions on the forum.
Similar Threads
  1. George Marsaglia

    Assigning unsigned long to unsigned long long

    George Marsaglia, Jul 8, 2003, in forum: C Programming
    Replies:
    1
    Views:
    728
    Eric Sosman
    Jul 8, 2003
  2. sarmin kho
    Replies:
    2
    Views:
    847
    A. Lloyd Flanagan
    Jun 15, 2004
  3. Daniel Rudy

    unsigned long long int to long double

    Daniel Rudy, Sep 19, 2005, in forum: C Programming
    Replies:
    5
    Views:
    1,236
    Peter Shaggy Haywood
    Sep 20, 2005
  4. Digital Puer

    extracting front bits from an unsigned long long?

    Digital Puer, Nov 11, 2005, in forum: C Programming
    Replies:
    36
    Views:
    1,367
    Mark McIntyre
    Nov 13, 2005
  5. krunalb
    Replies:
    10
    Views:
    929
    Kenneth Brody
    Jan 23, 2007
Loading...

Share This Page