Please Explain Count the number of bits in an int code

This is a discussion on Please Explain Count the number of bits in an int code within the C++ Programming forums, part of the General Programming Boards category; I am studying for an interview and I came across an interview that asks to count the number of bits ...

  1. #1
    Registered User
    Join Date
    Apr 2006
    Posts
    38

    Please Explain Count the number of bits in an int code

    I am studying for an interview and I came across an interview that asks to count the number of bits in an int. I have the solution but I do not uderstand either solution. Woul somebody please explain it to me? Thanks

    Code:
    int bitcount(int v)
    {
            for(int count=0; v; count++, v &= ~(v-1));
            return count;
    
     
    
    }
    
    
    int table[] = {0,1,1,2,1,2,2,3, 1,2,2,3,2,3,3,4 };
    #define bc(x) table[(x)&0xf ]   // maps nibbles to number of bits
    
    int bitcount(int v)
    {
            // assume 16 bit int
            return  bc(x) + bc(x>>4) + bc(x>>8) + bc(x>>12);
    
     
    
    }

  2. #2
    Registered User
    Join Date
    Jan 2005
    Location
    Estonia
    Posts
    131
    shouldn't the 'x' be defined somewhere?

  3. #3
    CSharpener vart's Avatar
    Join Date
    Oct 2006
    Location
    Rishon LeZion, Israel
    Posts
    6,484
    The second one is easy - it just determines number of bits in every 4-bit pattern
    from 0 to 0xf (using table array)
    Then calculate sum for each 4 bit pattern in the number (there are 4 in the 16-bit int)

    the first one I cannot undertand

    if v = 1

    v &= ~(v-1)
    is also 1
    so it seems to me there is and endless loop there

    PS. if that statement will be changed to
    v &= (v-1)

    it will remove one 1-bit from the number
    so the loop counts number of bits in the number...
    (havn't check it for negative numbers...
    Last edited by vart; 12-18-2006 at 08:13 AM.
    The first 90% of a project takes 90% of the time,
    the last 10% takes the other 90% of the time.

  4. #4
    and the hat of wrongness Salem's Avatar
    Join Date
    Aug 2001
    Location
    The edge of the known universe
    Posts
    32,546
    > I have the solution but I do not uderstand either solution
    You have "a" solution.
    One which requires a fair amount of knowledge about bits.

    Could you write the code using the obvious for loop and bit test approach or not?

    > I am studying for an interview
    Unlike exams, which you can study for and largely forget, interviews for jobs are just the tip of the iceberg of what you're supposed to know, and expected to deliver on if and when you get the job.
    If you dance barefoot on the broken glass of undefined behaviour, you've got to expect the occasional cut.
    If at first you don't succeed, try writing your phone number on the exam paper.
    I support http://www.ukip.org/ as the first necessary step to a free Europe.

  5. #5
    Registered User
    Join Date
    Apr 2006
    Posts
    38
    Thanks but nobody really explained to me whats going on. I don't understand the code or what the &0xf and >> are doing. Thanks

  6. #6
    Ethernal Noob
    Join Date
    Nov 2001
    Posts
    1,901
    Is this a job interview, to you?

  7. #7
    Just Lurking Dave_Sinkula's Avatar
    Join Date
    Oct 2002
    Posts
    5,006
    Quote Originally Posted by dnysveen
    Thanks but nobody really explained to me whats going on. I don't understand the code or what the &0xf and >> are doing. Thanks
    FAQ > Explanations of... > Bit shifting and bitwise operations
    FAQ > Prelude's Corner > Bit manipulation
    7. It is easier to write an incorrect program than understand a correct one.
    40. There are two ways to write error-free programs; only the third one works.*

  8. #8
    C++ Witch laserlight's Avatar
    Join Date
    Oct 2003
    Location
    Singapore
    Posts
    21,734
    The (x)&0xf is to get the lowest 4 bits, and thus a number from 0 to 15 inclusive. That gives the index of the lookup table for the number of bits in that nibble.

    The >> is needed to right shift by 4 bits so that each nibble can be checked.

    This might be a clearer example:
    Code:
    int countBitsInLowestNibble(int nibble)
    {
        static int table[] = {0,1,1,2,1,2,2,3, 1,2,2,3,2,3,3,4 };
        return table[nibble & 0xf]; // lookup number of bits in lowest nibble
    }
    
    int countBitsInInt(int x)
    {
        int count = 0;
        int numNibbles = sizeof(int) + sizeof(int);
        // cycle through each nibble starting with lowest nibble
        for (int i = 0; i < numNibbles; ++i)
        {
            count += countBitsInLowestNibble(x);
            x >>= 4; // place next 4 bits in lowest nibble position
        }
        return count;
    }
    C + C++ Compiler: MinGW port of GCC
    Version Control System: Bazaar

    Look up a C++ Reference and learn How To Ask Questions The Smart Way

  9. #9
    and the hat of wrongness Salem's Avatar
    Join Date
    Aug 2001
    Location
    The edge of the known universe
    Posts
    32,546
    Sorry, but if you can't figure out what 0xf is doing, you ain't fit for any C or C++ job.
    If you dance barefoot on the broken glass of undefined behaviour, you've got to expect the occasional cut.
    If at first you don't succeed, try writing your phone number on the exam paper.
    I support http://www.ukip.org/ as the first necessary step to a free Europe.

  10. #10
    Registered User
    Join Date
    Apr 2006
    Posts
    38
    I get the shiffting and nibble part now but I don't understand the table. Why does the table have these values.

    Edit
    Never mind got it. So when the say count the number of bit it means count the bits that are set to 1?
    Last edited by dnysveen; 12-19-2006 at 08:19 AM.

  11. #11
    Registered User hk_mp5kpdw's Avatar
    Join Date
    Jan 2002
    Location
    Northern Virginia/Washington DC Metropolitan Area
    Posts
    3,801
    Well, now that you say you've got it all figured out, keep that bit of knowledge safe and if the question ever comes up again in the future you might just consider using something easier:
    Code:
    #include <limits>
    #include <bitset>
    #include <iostream>
    
    std::cout << std::bitset<std::numeric_limits<int>::digits>(your_int_value_here).count() << std::endl;
    Replace your_int_value_here with whatever integer value or variable to get a count of the number of enabled bits for that value/variable.

    Quote Originally Posted by dnysveen
    So when the say count the number of bit it means count the bits that are set to 1?
    Yes, the point seems to be to count the bits in an integer that are set to 1... which is what the above bitset example does for you.
    Last edited by hk_mp5kpdw; 12-19-2006 at 12:52 PM. Reason: Corrected numerical_limits as pointed out by indigo0086
    "Owners of dogs will have noticed that, if you provide them with food and water and shelter and affection, they will think you are god. Whereas owners of cats are compelled to realize that, if you provide them with food and water and shelter and affection, they draw the conclusion that they are gods."
    -Christopher Hitchens

  12. #12
    Ethernal Noob
    Join Date
    Nov 2001
    Posts
    1,901
    What does the limits class do btw, can't find that in the reference (I think you mean to put numeric_limits as well)

    also if you want to illustrate it you can do something like
    Code:
    int bit_counter(int x)
    {
    
        int count = 0;
        
        while(x != 0)
        {
            count += x & 0x1;
            x >>= 1;
        }
        return count;
    }
    
    
    int main()
    {
    	std::cout << bit_counter(15) << std::endl;
    
    	return 0;
    }
    der!

    Totally missed the count portion of the bitset class, kind of makes this useless.
    Last edited by indigo0086; 12-19-2006 at 12:39 PM.

  13. #13
    Registered User hk_mp5kpdw's Avatar
    Join Date
    Jan 2002
    Location
    Northern Virginia/Washington DC Metropolitan Area
    Posts
    3,801
    What does the limits class do btw, can't find that in the reference (I think you mean to put numeric_limits as well)
    Yes, I've changed the numeric_limits thing, thanks for pointing that out. When you create a bitset, you must specify how many bits you want it to handle. I just put in the numeric_limits part to automatically get that for you so you don't have to guess how many bits are contained in an int.
    "Owners of dogs will have noticed that, if you provide them with food and water and shelter and affection, they will think you are god. Whereas owners of cats are compelled to realize that, if you provide them with food and water and shelter and affection, they draw the conclusion that they are gods."
    -Christopher Hitchens

  14. #14
    Ethernal Noob
    Join Date
    Nov 2001
    Posts
    1,901
    I see, since not all computers have the same size for the types.

  15. #15
    Registered User
    Join Date
    Jan 2005
    Posts
    7,318
    >> std::numeric_limits<int>::digits
    That will return the number of digits that an int can have, not the number of bits. You want:
    Code:
    std::cout << std::bitset<sizeof(int)*CHAR_BIT>(your_int_value_here).count() << std::endl;
    I don't remember offhand where CHAR_BIT is defined.

Page 1 of 3 123 LastLast
Popular pages Recent additions subscribe to a feed

Similar Threads

  1. how to combine these working parts??
    By transgalactic2 in forum C Programming
    Replies: 0
    Last Post: 02-01-2009, 07:19 AM
  2. xor linked list
    By adramalech in forum C Programming
    Replies: 23
    Last Post: 10-14-2008, 10:13 AM
  3. Replies: 3
    Last Post: 05-13-2007, 08:55 AM
  4. Debug Error Really Quick Question
    By GCNDoug in forum C Programming
    Replies: 1
    Last Post: 04-23-2007, 12:05 PM
  5. Replies: 4
    Last Post: 11-23-2003, 06:15 AM

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21