Using recursion how can I count number of bits in an unsigned integer?

Question

Why this code terminated and crashed to evaluate the number of bits?

int main(void)
{
    int y = 94;
    int m  = bitCount(y);


    printf("%d",m);
    return 0;
}

int bitCount(int val)
{
    int i = 0;
    if(!bitCount(val/2))
        i++;
    return i;
}

You might like to read this: [How to debug small programs](https://ericlippert.com/2014/03/05/how-to-debug-small-programs/) — alk, Jun 30 '18 at 11:18
Try checking the stop condition first, in which the function should return zero. If it's not the case, if the [LSB](https://en.wikipedia.org/wiki/Bit_numbering#Least_significant_bit) is set, you should return 1 plus the number of set bits in the [bit-shifted](https://en.wikipedia.org/wiki/Bitwise_operation#Bit_shifts) `val` (recursive call). If the LSB is not set, you should return 0 plus number of set bits in the bit-shifted `val`. Note that it's always the value of the LSB plus the remaining bits. You should also use `unsigned int` according to your question. — Mance Rayder, Jun 30 '18 at 12:09
I see your actual question is not yet answered. The program crashes because every call to `bitCount` results in yet another call to `bitCount`. You are filling up the memory of your computer with calls to `bitCount`, and when you run out of memory space, it crashes. — Jongware, Jun 30 '18 at 13:52

Steve Summit · Accepted Answer · 2018-06-30T13:32:02.007

Recursive functions work by breaking the problem into smaller parts. It looks like you're trying to break the problem into smaller parts by dividing it by 2. That can work, but you have to keep two things in mind:

You have to count the bits in both parts. For example, if you call bitCount(val/2), that's fine: you've just called bitCount() on a smaller problem, on all but the last bit of val. But what about the last bit that you just threw away? You have to count it if it's 1. (Hint: val%2).
You can't make recursive calls forever. In this case: if val is less than 2, then val/2 will be 0, so there are no 1 bits in it, so there's no need to call bitCount(val/2) to discover that. So you need to "break the recursion" by not calling bitCount in that case.

As I said, this can work, but it's not a particularly good example of a recursive function, because the "breaking it into smaller parts" piece is pretty lopsided. This algorithm will make as many recursive calls as there are bits in the number; it ends up having roughly the same time complexity ("big O") as a straightforward, linear algorithm. Ideally you'd break the number into two halves based on the number of bits, not based on the number.

In other words, in your example, 94 in binary is 1011110, and you're breaking it into the two subproblems 101111 and 0. It'd be better to break it into, say, 1011 and 110.

I don't know of an easy way to do that; splitting a number in half that way is probably about as hard as counting bits in the first place, so there's little advantage. Another possibility is to break off, say, the bottom 4 bits each time, by calling bitCount(val/16) (equivalently, bitCount(val>>4)).

"This algorithm will make as many recursive calls as there are bits in the number", true, but not matter how you divide the bits, this will *always* be true. (Because each call will always process exactly one bit.) Anyway, tail recursion is an example of what you call 'lopsided' but nevertheless often a good solution. — Jongware, Jun 30 '18 at 13:25
@usr2564301 Yeah, I guess I meant it was linear in stack usage, too, unlike a more balanced recurrence. — Steve Summit, Jun 30 '18 at 13:34

score 1 · Answer 2 · answered Jun 30 '18 at 12:35

1

I did a simple program where you can count a number of bits, I will assume you were talking about the 1s and 0s. If not, well I'm dumb :P

bitCount function using recursion:

int bitCount(unsigned int x, int count) {       
    if (n==0) return count;
    if (n%2==1) bitCount(n/2,count+1);
    else bitCount(n/2,count);
}

Calling the fuction on main:

int main() {
   unsigned int x=94;
   int counting = 0;
   printf ("Result of bits: %d \n", bitCount(x,counting));

return 1;
}

With the unsigned int = 94, it will return 5. I hope it was that you wanted :)

answered Jun 30 '18 at 12:35

CellScript

41
5

I know you were anxious to help, but we try not to do people's homework for them. Also, you're missing some `return` statements in your `bitCount` implementation, – Steve Summit Jun 30 '18 at 13:08
Yes, you're right @SteveSummit , but it worked with me with and without ;) – CellScript Jun 30 '18 at 13:17
1

I understand, but programs that work accidentally or for the wrong reasons are in a sense even more dangerous than programs that don't work at all, because they can just as easily stop working tomorrow, "for no reason". See [this question](https://stackoverflow.com/questions/4644860), also [these](https://stackoverflow.com/questions/1610030) [several](https://stackoverflow.com/questions/18018454) [questions](https://stackoverflow.com/questions/28060029). – Steve Summit Jun 30 '18 at 13:29

Using recursion how can I count number of bits in an unsigned integer?

2 Answers2