Count # of zeros in binary representation

[mpark4656]

I'm trying to solve a problem from a textbook.

"Write a recursive function that returns the number of 0s in the binary representation of N. Use the fact that this is equal to the number of 0s in the representation of N/2, plus 1, if N is even."

After scratching my head for a couple hours, I solved the problem my way. I have no idea how to use the fact, "this is equal to the number of 0s in the representation of N/2, plus 1, if N is even." My solution uses a recursive function as the problem required and it seems to output the correct answer. Does anyone know how to solve the problem the way the textbook author intended?

#include <iostream>

// Function to find the largest power of 2 less than n
// Example: For n = 60, return value is 32 or 2^5.
//          2^6 or 64 is larger than 60.
int findLargestPowerOfTwo( int n ) {

    if( n == 0 ) {
        return 0;
    }
    else {
        int i;

        for( i = 1 ; n % i != n ; i *= 2 ) {}

        return i / 2;
    }
}

// Recursive Function to return the # of zeros for the binary
// representation of n
// Precondition: factor is the largest power of 2 less than n
//               n is a positive integer
int returnNumZero( int factor , int n ) {

	if( factor == 1 && n == 1 ) {
		return 0;
	}
	else if( (factor == 1 || factor == 0) && n == 0 ) {
		return 1;
	}
	else if( (factor > 1 && n == 0) || n % factor == n ) {
		return 1 + returnNumZero( factor / 2 , n );
	}
	else {
		return returnNumZero( factor / 2 , n % factor );
	}
}

// Main Driver
int main() {

    int n; // Positive Integer

    std::cin >> n;

    std::cout << returnNumZero( findLargestPowerOfTwo( n ) , n );

    return 0;
}

[booradley60]

What do you expect the result to be for each of these cases?

How many zeroes are in the binary representation for:
0?
1?
2?
3?

This will help determine how wide your binary representations are. 0101 has the same numeric value as 101, but the wider representation has two zeroes. This shows that the result of the function will depend both on the value of the number and the bit width of the binary representation.

The width can be determined by type (think short vs. int) or you may have to do something like find the location of the most-significant-bit with a value of 1.

[mpark4656]

My textbook does NOT clarify this, so I am setting the specification. Only the significant zeros are counted and leading zeros are omitted. For example

00011101 = 11101, so the output should be 1


Binary representation of 0 is 0, so the output is 1


1 - 0
2 - 1
3 - 0

[booradley60]

#include <iostream>

int CountZeroes(unsigned int num)
{
    // We either started at 0 or we've reached our
    // most significant 1-bit. In either case, this
    // is the base case.
    //
    // The (1 - num) part will return 0 if the number
    // is 1 (because we don't want to count 1's)
    // -OR-
    // return 1 if the number is 0, since we want to
    // count the single zero.
    if(num == 0 || num == 1) return (1 - num);

    if(num % 2 == 0) //number is divisible by 2, i.e. it's even
    {
        //this is where the hint comes in handy
        //"...this is equal to the number of 0s in the representation of N/2, plus 1, if N is even."
        return 1 + CountZeroes(num/2);
    }
    else //else, number is odd
    {
        return CountZeroes(num/2);
    }
}

int main()
{
    int theNumber = 0; // binary: 0
    std::cout << theNumber << ": there are " << CountZeroes(theNumber) << " zeroes.\n";

    theNumber = 1; // binary: 1
    std::cout << theNumber << ": there are " << CountZeroes(theNumber) << " zeroes.\n";

    theNumber = 9; // binary: 1001
    std::cout << theNumber << ": there are " << CountZeroes(theNumber) << " zeroes.\n";
}

[mpark4656]

@booradley60

Thank you. I think that's probably how you are supposed to solve that textbook problem. I appreciate the commented explanation.