locked
More Than 64 bit of memory! RRS feed

  • Question

  • Greetings,

    I tried to use bits as bool flags, however, when I need more than 64 bit I can't use them.
    I read something about "bitset"
    but I was unable to implement it. In fact, I am not sure whether will it work for this case or not.

    Here is my code while trying implementing the bitset into a vector.

    	double averageNames(int n, vector<int> pA, vector<int> pB)
    	{
    		vector< bitset <100> >   nNames;
    		nNames.resize(n, 0);
    		double avg = 0;
    		for(int i = 0; i < pA.size(); i++)
    		{
    			nNames[pA[i]] |= (long long) pow(2.0, pB[i]) | nNames[pB[i]];
    			nNames[pB[i]] |= (long long) pow(2.0, pA[i]) | nNames[pA[i]];
    			nNames[pA[i]] &= ~ (long long) pow(2.0, pA[i]);
    			nNames[pB[i]] &= ~ (long long) pow(2.0, pB[i]);
    		}
    
    		while (nNames.size())
    		{
    			while(nNames.back())
    			{
    				nNames.back() -= nNames.back() & -nNames.back();
    				avg++;
    			}
    			nNames.pop_back();
    		}
    		avg /= n;
    		return avg;
    	}

    It gives errors at "|"s and "-". "no operator matches these operands" (Is there a walk around?)
    Moreover, in "while(nNames.back())" I get error "expression must have bool type"

    Finally, is there a way to make "bitset<n>" where n is a variable?

    Thanks.

    Wednesday, November 28, 2012 5:19 PM

Answers

  • I hate recommending boost because it's a ridiculously large amount of code to do the simplest things, but it happens to be exactly what you want.  Boost offers dynamic_bitset.

    A bitset<x> for large values of x is basically just a vector<long long> under the hood that supports the logical operations in 64-bit chunks through iterators.

    But finally, I don't understand what your "averageNames" function is intended to do.  The code you wrote looks quite illogical.  It's full of redundant and/or bogus operations.

    Can you give me a synopsis in plain English of what the function is supposed to do?

    It takes two vectors of integers, presumably intended to be of length at least N, and returns the average number of ...  (what?)



    • Proposed as answer by Elegentin Xie Wednesday, December 5, 2012 5:44 AM
    • Marked as answer by Elegentin Xie Friday, December 7, 2012 6:06 AM
    Wednesday, November 28, 2012 6:40 PM
  • In order to manipulate bits of bitset, use set, reset and flip. For example: nNames[pA[i]].reset(pA[i]). If you need variable-size bitsets, then try vector<bool> instead of bitset<100>.

    • Proposed as answer by Elegentin Xie Wednesday, December 5, 2012 5:44 AM
    • Marked as answer by Elegentin Xie Friday, December 7, 2012 6:06 AM
    Wednesday, November 28, 2012 8:17 PM

All replies

  • I hate recommending boost because it's a ridiculously large amount of code to do the simplest things, but it happens to be exactly what you want.  Boost offers dynamic_bitset.

    A bitset<x> for large values of x is basically just a vector<long long> under the hood that supports the logical operations in 64-bit chunks through iterators.

    But finally, I don't understand what your "averageNames" function is intended to do.  The code you wrote looks quite illogical.  It's full of redundant and/or bogus operations.

    Can you give me a synopsis in plain English of what the function is supposed to do?

    It takes two vectors of integers, presumably intended to be of length at least N, and returns the average number of ...  (what?)



    • Proposed as answer by Elegentin Xie Wednesday, December 5, 2012 5:44 AM
    • Marked as answer by Elegentin Xie Friday, December 7, 2012 6:06 AM
    Wednesday, November 28, 2012 6:40 PM
  • Basically it takes number of persons in a party (n). the two vectors and basically the series of handshaking that happened in the party.
    person A (pA) with person B (pB)
    Every time the exchange the names they know until now.
    The function is to get the average number of names known per person.
    The code used to work just fine with:

    "vector< long long> nNames;"

    but it turned out that number of people can be greater than 64.

    Note: It's a problem in Top Coder I was practicing on.

    Anyway, it looks like I have to give up the idea of doing it with bitwise operations. I am not that good to understand "boost".

    Wednesday, November 28, 2012 7:02 PM
  • In order to manipulate bits of bitset, use set, reset and flip. For example: nNames[pA[i]].reset(pA[i]). If you need variable-size bitsets, then try vector<bool> instead of bitset<100>.

    • Proposed as answer by Elegentin Xie Wednesday, December 5, 2012 5:44 AM
    • Marked as answer by Elegentin Xie Friday, December 7, 2012 6:06 AM
    Wednesday, November 28, 2012 8:17 PM