Thread: Help with programming with bits

THe problem statement asks "Given that the expression ~0 produces an integer that contains all 1s, write a functioncalled int_size that returns the number of bits contained in an int on your
particular machine."

The solution is:

Code:

int  int_size (void)
{
    unsigned int  bits;
    int           size = 0;

    bits = ~0;

    while ( bits ) {
       ++size;
       bits >>= 1;
    }

    return size;
}

Is the while loop saying while (bits=1)?
If so, I don't understand why bits has to equal one for the size to increase.

while ( bits )
could be written
while ( bits > 0 )

bits >>= 1;
You can unfold that into this:
bits = bits >> 1;
Shifting right once will drop a bit so you count it. Eventually you get a size etc.

Yes, I think I understand that, but why does bits have to be >0?
A bit can be 0 or 1. So why is it exclusively 1 in this case?
Is it because before the while loop bits is set equal to ~0?

#include <limits.h>
...
#define INT_BITS (CHAR_BIT * sizeof (int))

That seems to be a mistake - what should have been stated was "while ( bits != 0 )" because in 'C,' non-zero is considered true and zero is considered false.

It's not really a mistake since it's an unsigned int.

Well the reason you say bits > 0 in the loop condition is so that you count all of the bits. Eventually all of the bits will be turned off, you get zero, which means you are done counting.

The reason that bit >>= 1 is used is because the loop is supposed to go like this:
1111
0111
0011
0001
0000

IOW, you only need to shift one bit at a time.

Originally Posted by Barney McGrew

It's not really a mistake since it's an unsigned int.

You're right, I stand corrected.

Originally Posted by whiteflags

Well the reason you say bits > 0 in the loop condition is so that you count all of the bits. Eventually all of the bits will be turned off, you get zero, which means you are done counting.

Does this have anything to do with bits=~0?

What if you had bits=101. Wouldn't this yield size=1, since the while loops well terminate once it hits the "0" in "101."

If the binary representation of an integer is 10, what is its decimal value?

Originally Posted by Barney McGrew

If the binary representation of an integer is 10, what is its decimal value?

0*2^0+1*2^1=2

10 in binary is still more than 0.

Bitwise operations happen on a bit-by-bit level. A '~' is just an inverse.

Code:

 Bits: 101
~Bits: 010

This speaks nothing of size.

In your example, to count the bits, you'd set them all to one and count the ones. What's a quick way to set all bits to one? Set them all to zero and invert them all (to one).

Originally Posted by Barney McGrew

Right. So, until the value of bits reaches 0, the value stored by size will continue to be incremented.

edit: Think of it this way:

101 (5) > 0? Yes.
10 (2) > 0? Yes.
1 (1) > 0? Yes.
0 (0) > 0 ? No.

Which would terminate with 3 stored in size.

Thank you guys. THis explanation really helped.
I forgot in the while argument that #>0, where # is represented in decimal and not binary.