Thread: bitwise operations in C

  1. #1
    Registered User
    Join Date
    Oct 2002
    Posts
    27

    bitwise operations in C

    I'm trying to write a program called bitCount -
    It returns the of number of 1's in word (32 bit word size)
    Examples: bitCount(5) = 2, bitCount(7) = 3
    Legal ops: ! ~ & ^ | + << >>
    Max ops: 40

    does anyone have any hints on this, it doesn't really make sense to me.

  2. #2
    Code Goddess Prelude's Avatar
    Join Date
    Sep 2001
    Posts
    9,897
    Here's one way that tests the low order bit and then shifts all bits right until the value is 0:
    Code:
    int bit_count1 ( unsigned int val )
    {
      int count = 0;
    
      while ( val != 0 ) {
        if ( val & 1 )
          count++;
    
        val >>= 1;
      }
    
      return count;
    }
    And another method that loops until the value is 0, but instead of shifting it clears the lowest order bit set to 1:
    Code:
    int bit_count2 ( unsigned int val )
    {
      int count = 0;
    
      while ( val != 0 ) {
        count++;
    
        val &= val - 1;
      }
    
      return count;
    }
    -Prelude
    My best code is written with the delete key.

  3. #3
    Registered User
    Join Date
    Oct 2002
    Posts
    27
    what's really tough is that I need to do this without using any operations like "if" or "while" or "for"

    just bitwise operators

  4. #4
    Code Goddess Prelude's Avatar
    Join Date
    Sep 2001
    Posts
    9,897
    No problem, but it's not nearly as clear as the previous functions and it assumes a 32 bit value:
    Code:
    int bit_count3 ( unsigned int val )
    {
      val = ( val & 0x55555555 ) + ( ( val >> 1 ) & 0x55555555 );
      val = ( val & 0x33333333 ) + ( ( val >> 2 ) & 0x33333333 );
      val = ( val & 0x0F0F0F0F ) + ( ( val >> 4 ) & 0x0F0F0F0F );
      val = ( val & 0x00FF00FF ) + ( ( val >> 8 ) & 0x00FF00FF );
      val = ( val & 0x0000FFFF ) + ( ( val >> 16 ) & 0x0000FFFF );
    
      return (int)val;
    }
    -Prelude
    My best code is written with the delete key.

  5. #5
    Green Member Cshot's Avatar
    Join Date
    Jun 2002
    Posts
    892
    Code:
    int BitCount(unsigned int x) 
    { 
       x = (x >> 1 & 0x55555555) + (x & 0x55555555); 
       x = (x >> 2 & 0x33333333) + (x & 0x33333333); 
       x = (x >> 4 & 0x0f0f0f0f) + (x & 0x0f0f0f0f); 
       x = (x >> 8 & 0x00ff00ff) + (x & 0x00ff00ff); 
       return(x >> 16) + (x & 0x0000ffff); 
    }
    EDIT - dammit, you beat me this time
    Try not.
    Do or do not.
    There is no try.

    - Master Yoda

  6. #6
    Registered User
    Join Date
    Oct 2002
    Posts
    27
    thanks, I wasn't really expected some one to just give me the code. I don't completly understand how the masking is working, but I'll have to break it down at it and figure it out.

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Bitwise Operations to Read ON/OFF Bits
    By pseudonoma in forum C Programming
    Replies: 4
    Last Post: 02-25-2008, 03:15 PM
  2. bitwise operations with double
    By henry_kay in forum C Programming
    Replies: 2
    Last Post: 10-03-2007, 04:57 AM
  3. Bitwise operations
    By sh3rpa in forum C++ Programming
    Replies: 16
    Last Post: 09-25-2007, 06:32 PM
  4. bitwise operations
    By black_watch in forum C++ Programming
    Replies: 9
    Last Post: 03-24-2007, 04:48 AM
  5. bitwise operations
    By andrew_tucker in forum C Programming
    Replies: 2
    Last Post: 11-28-2002, 12:46 AM