Thread: Bit flipping while tracking the sum of bits (and other questions)

  1. #1
    Registered User
    Join Date
    May 2008
    Posts
    115

    Question Bit flipping while tracking the sum of bits (and other questions)

    Hello All!

    I am fairly new to c. In parts of my program I need to converts a very large number of consecutive integers to a binary, flip each bit while keeping track of the sum of bits and compute a weighted sum of the elements in a given array weighted by the bits.

    Below is my solution. I what to improve the algorithm performance. Here are some ideas that I have. Maybe you can tell me which ones are good and how to implement them:

    1. How can I find the value of the flipped bit so that I do not have to sum all the bits every time but increment an initial sum instead;
    2. I heard of very efficient bit manipulation using masks (?) Does anyone have code that could be used in my program. Especially to sum the elements of the array (w)
    3. The structure of my program allows splitting the outer loop in 2 or more threads. Would this help? If yes, how to do this.

    Thank you very much for help!

    Serge

    Code:
    #include <bitset>
    #include <iostream>
    
    int main()
    {
    static const unsigned n = 27;
    static unsigned int w[ n ] = {10,12,10,4,12,29,7,27,4,7,29,29,12,12,7,29,7,4,4,3,13,27,12,14,7,4,10};
    
    static const unsigned nc = 1 << n; /* 2^27 */
    
    unsigned int sumv = 0;
    unsigned int sumw = 0;
    
    unsigned int i;
    for ( i = nc; i--; ) /* loop through numbers from 2^27 to 0 */
    {
    	std::bitset < n > v = i; /* binary representation of i */
    
    	unsigned int j;
    	for ( j = n ; j--; ) /* loop through bits */
    	{
    		v.flip( j );  /* flip the bit */
    		sumv = v.count(); /* compute the new sum of bits */
    
    		/* do other things */
    
    		/* compute weighted sum using flipped */
    		sumw = 0;
    		k = 0;
    		for ( k = n; k--; ) { if ( v[ n - k - 1 ] ) { sumw += w[ k ]; } }
    		printf( "%u\n" , sumw );
    
    		v.flip( j ); /* flip back */
    	}
    }
    
    return 0;
    }

  2. #2
    and the Hat of Guessing tabstop's Avatar
    Join Date
    Nov 2007
    Posts
    14,336
    Maybe I've not got a hold of what you're trying to do, as I'm not sure exactly what questions you're asking. Are you asking how to know the value of the j'th bit? Isn't the value of the j'th bit 1<<j? If count is really counting the number of bits that are on, then you don't have to recount each time; if the new bit is on, the count went up by 1, if the new bit is off it went down.

    As to the bit mask thing, I guess that would be in place of your bitset stuff. You can flip a bit using an xor operation, although to sum the array would still require a loop, so far as I can tell.

Popular pages Recent additions subscribe to a feed

Tags for this Thread