count bit loop

This is a discussion on count bit loop within the C Programming forums, part of the General Programming Boards category; Good morning, I am given the hamming distance algorithm in C which is Code: int returnDistance(int x, int y) { ...

  1. #1
    Registered User
    Join Date
    Oct 2010
    Posts
    33

    count bit loop

    Good morning,

    I am given the hamming distance algorithm in C which is

    Code:
    int returnDistance(int x, int y)
    {
             unsigned dist = 0;
             unsigned val = x ^ y;
    
             while(val)
             {
                    ++dist;
                    val &= val - 1;
              }
    
               return dist;
    }
    I see that this loop counts all the 1's that are found when we xor y and x, but what I'm puzzled with is how does the while loop break out? How does it know when a value is complete?

    Thanks.

  2. #2
    C++ Witch laserlight's Avatar
    Join Date
    Oct 2003
    Location
    Singapore
    Posts
    21,712
    Print out the value of val in the loop and observe what happens for various input. Alternatively, just observe by using a debugger.
    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

  3. #3
    Registered User
    Join Date
    Aug 2010
    Location
    Poland
    Posts
    682
    Quote Originally Posted by aromash View Post
    I see that this loop counts all the 1's that are found when we xor y and x, but what I'm puzzled with is how does the while loop break out? How does it know when a value is complete?
    Thanks.
    As I can see, the expression:
    Code:
    val &= val - 1;
    Removes one bit from val (sets one of them, which is 1, to 0). After a few iterations all bits will be set to 0. The loop breaks when val == 0 (all bits are 0).
    I never put signature, but I decided to make an exception.

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Replies: 1
    Last Post: 12-07-2010, 05:53 AM
  2. While loop to count the charecters of a string
    By simpatico_qa in forum C Programming
    Replies: 11
    Last Post: 04-24-2009, 03:51 AM
  3. Replies: 16
    Last Post: 11-23-2007, 12:48 PM
  4. Porting from 32 bit machine to 64 bit machine!
    By anoopks in forum C Programming
    Replies: 10
    Last Post: 02-25-2005, 07:02 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