Thread: Counter the number of 1 bits?

  1. #1
    Registered User
    Join Date
    Apr 2003
    Posts
    82

    Counter the number of 1 bits?

    I'm having a trouble of thinking of way to count the number of 1 bits in a binary number with out using any condition tests or branches. Only ones i know have condition tests or branches like

    Code:
    while (n!=0)
    {
    count++;
    n=n&(n-1)
    }
    This is for my assembly language class and I'm supposed to use any kind of shifting or and/or. But if I saw it in C++ i probably be able to convert it.

  2. #2
    Just Lurking Dave_Sinkula's Avatar
    Join Date
    Oct 2002
    Posts
    5,005
    Oooh! Pick me!
    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.*

  3. #3
    Registered User
    Join Date
    Apr 2003
    Posts
    82
    Quote Originally Posted by Dave_Sinkula
    Oooh! Pick me!
    Sorry but I dont think it will work, I forgot to mention I need to count 8-bits

  4. #4
    Carnivore ('-'v) Hunter2's Avatar
    Join Date
    May 2002
    Posts
    2,879
    (1 << n) is a mask for bit #n.

    (number & mask) == 0 when the bit is 0.
    (number & mask) != 0 when the bit is 1.

    Now loop for each bit from 0 to 7, checking if each is 1.
    Just Google It. √

    (\ /)
    ( . .)
    c(")(") This is bunny. Copy and paste bunny into your signature to help him gain world domination.

  5. #5
    Registered User samGwilliam's Avatar
    Join Date
    Feb 2002
    Location
    Newport
    Posts
    382
    Code:
    	int num = 46;
    	int bit = 1;
    	int count = 0;
    
    	while (bit <= 128)
    	{
    		count += ((num & bit) > 0);
    		bit <<= 1;
    	}
    
    	cout << "Has " << count << " bits." << endl;

  6. #6
    ATH0 quzah's Avatar
    Join Date
    Oct 2001
    Posts
    14,826
    Code:
    unsigned char count foo( unsigned char b )
    {
        return (!!(b&  1))+(!!(b&  2))+(!!(b&  4))+(!!(b&  8))+
               (!!(b& 16))+(!!(b& 32))+(!!(b& 64)0+(!!(b&128));
    }
    Me too, me too!
    Hope is the first step on the road to disappointment.

  7. #7
    Registered User
    Join Date
    Apr 2003
    Posts
    82
    Quote Originally Posted by quzah
    Code:
    unsigned char count foo( unsigned char b )
    {
        return (!!(b&  1))+(!!(b&  2))+(!!(b&  4))+(!!(b&  8))+
               (!!(b& 16))+(!!(b& 32))+(!!(b& 64)0+(!!(b&128));
    }
    Me too, me too!
    What does the !! mean? And is this for 128 bits? and if i wanted 8 bits I would use
    return (!!(b& 1))+(!!(b& 2))+(!!(b& 4))+(!!(b& 8)))

  8. #8
    ATH0 quzah's Avatar
    Join Date
    Oct 2001
    Posts
    14,826
    No. It's for eight bits. Just like you wanted. ! is the the "not" operator. That means, if something is non-zero, it becomes zero. Otherwise, it becomes 1. We apply it twice, to make it "change non-zero to zero and then to one".

    Otherwise, without it, you just end up with whatever value you origionally pass to the function.

    Quzah.
    Hope is the first step on the road to disappointment.

  9. #9
    Registered User
    Join Date
    Aug 2004
    Location
    San Diego, CA
    Posts
    313
    Quote Originally Posted by gqchynaboy
    What does the !! mean? And is this for 128 bits? and if i wanted 8 bits I would use
    return (!!(b& 1))+(!!(b& 2))+(!!(b& 4))+(!!(b& 8)))
    Here's a hint: Powers of 2.

    2^0 = 1
    2^1 = 2
    2^2 = 4
    2^3 = 8
    2^4 = 16
    2^5 = 32
    2^6 = 64
    2^7 = 128

    Range from 0-7: 8. Therfore, Quzah is correct in his statement - he is covering all 8 bits in a byte.

  10. #10
    Registered User samGwilliam's Avatar
    Join Date
    Feb 2002
    Location
    Newport
    Posts
    382
    Let's face it though - my solution is more elegant.

  11. #11
    ATH0 quzah's Avatar
    Join Date
    Oct 2001
    Posts
    14,826
    Is this a contest? Should I do the standard "yeah, but mine's faster" reply now, or what?

    Quzah
    Hope is the first step on the road to disappointment.

  12. #12
    Registered User samGwilliam's Avatar
    Join Date
    Feb 2002
    Location
    Newport
    Posts
    382
    Quote Originally Posted by quzah
    Is this a contest? Should I do the standard "yeah, but mine's faster" reply now, or what?

    Quzah
    I'm always finding myself torn between efficiency and elegance, but for such a trivial problem you may as well just plump for elegance.

  13. #13
    Registered User
    Join Date
    Apr 2003
    Posts
    82
    I want simplicity =]

  14. #14
    Code Goddess Prelude's Avatar
    Join Date
    Sep 2001
    Posts
    9,897
    Simple, elegant, and about as fast as it gets. Next?
    Code:
    int bits[] = {
      0, 1, 1, 2, 1, 2, 2, 3, 1, 2, 2, 3, 2, 3,
      3, 4, 1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4,
      3, 4, 4, 5, 1, 2, 2, 3, 2, 3, 3, 4, 2, 3,
      3, 4, 3, 4, 4, 5, 2, 3, 3, 4, 3, 4, 4, 5,
      3, 4, 4, 5, 4, 5, 5, 6, 1, 2, 2, 3, 2, 3,
      3, 4, 2, 3, 3, 4, 3, 4, 4, 5, 2, 3, 3, 4,
      3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6, 2, 3,
      3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,
      3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6,
      6, 7, 1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4,
      3, 4, 4, 5, 2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 
      4, 5, 4, 5, 5, 6, 2, 3, 3, 4, 3, 4, 4, 5, 
      3, 4, 4, 5, 4, 5, 5, 6, 3, 4, 4, 5, 4, 5, 
      5, 6, 4, 5, 5, 6, 5, 6, 6, 7, 2, 3, 3, 4, 
      3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6, 3, 4, 
      4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7, 
      3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 
      6, 7, 4, 5, 5, 6, 5, 6, 6, 7, 5, 6, 6, 7, 
      6, 7, 7, 8
    };
    
    int count ( unsigned char x )
    {
      return bits[x];
    }
    My best code is written with the delete key.

  15. #15
    Registered User samGwilliam's Avatar
    Join Date
    Feb 2002
    Location
    Newport
    Posts
    382
    Quote Originally Posted by Prelude
    Simple, elegant, and about as fast as it gets. Next?
    Code:
    int bits[] = {
      0, 1, 1, 2, 1, 2, 2, 3, 1, 2, 2, 3, 2, 3,
      3, 4, 1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4,
      3, 4, 4, 5, 1, 2, 2, 3, 2, 3, 3, 4, 2, 3,
      3, 4, 3, 4, 4, 5, 2, 3, 3, 4, 3, 4, 4, 5,
      3, 4, 4, 5, 4, 5, 5, 6, 1, 2, 2, 3, 2, 3,
      3, 4, 2, 3, 3, 4, 3, 4, 4, 5, 2, 3, 3, 4,
      3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6, 2, 3,
      3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,
      3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6,
      6, 7, 1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4,
      3, 4, 4, 5, 2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 
      4, 5, 4, 5, 5, 6, 2, 3, 3, 4, 3, 4, 4, 5, 
      3, 4, 4, 5, 4, 5, 5, 6, 3, 4, 4, 5, 4, 5, 
      5, 6, 4, 5, 5, 6, 5, 6, 6, 7, 2, 3, 3, 4, 
      3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6, 3, 4, 
      4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7, 
      3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 
      6, 7, 4, 5, 5, 6, 5, 6, 6, 7, 5, 6, 6, 7, 
      6, 7, 7, 8
    };
    
    int count ( unsigned char x )
    {
      return bits[x];
    }


    For extra brownie points you could compute the look-up table beforehand instead of manually bashing it out. For any more bits than this, you'd need to!!!

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Please Explain Count the number of bits in an int code
    By dnysveen in forum C++ Programming
    Replies: 36
    Last Post: 12-23-2006, 10:39 PM
  2. Help counting number of bits set in an integer
    By JayDiddums10 in forum C Programming
    Replies: 5
    Last Post: 12-07-2006, 03:21 PM
  3. Number of bits in types
    By TriKri in forum C Programming
    Replies: 7
    Last Post: 12-02-2006, 12:56 PM
  4. Replies: 16
    Last Post: 10-29-2006, 05:04 AM
  5. copy some bits into a 8 bits binary number
    By Unregistered in forum C Programming
    Replies: 6
    Last Post: 05-29-2002, 10:54 AM