Thread: help me to understand this code

  1. #1
    Registered User
    Join Date
    Jul 2019
    Posts
    5

    help me to understand this code

    Can you explain the code below for me ? the three functions return values to the main program to :
    Count the longest string of 1’s
    ,Count the longest string of 0’s.
    ,Count the longest alternating 1’s and 0’s.
    Code:
    int ONES(int data)
    {
      int i, shift;
    
      for (i = 0; data != 0; i++) {
        shift = (data >> 1) & 0x7FFFFFFF; // shift right logical
        data = data & shift;
      }
      return (i);
    }
    
    int ZEROS(int data)
    {
      return (ONES(data ^ 0xFFFFFFFF));
    }
    
    int ALTERNATE(int data)
    {
      int ret_val1, ret_val0;
    
      data = data ^ 0x55555555;
      ret_val1 = ONES(data);
      ret_val0 = ZEROS(data);
    
      return (ret_val1 > ret_val0 ? ret_val1 : ret_val0);
    }
    Last edited by Salem; 07-09-2019 at 10:40 PM. Reason: Removed crayola

  2. #2
    Registered User
    Join Date
    May 2019
    Posts
    214
    The heart of this is ONES.

    Everything else works off of it.

    Imagine a fine tooth comb with perhaps some missing teeth. Where there are teeth are the 1's. Where they're missing are zeros.

    Now, imagine you can duplicate the comb exactly, and instantly. You have to identical combs with some missing teeth.

    Hold one comb still, and slide the other come toward the right the width of one tooth in distance (that's a shift right).

    Compare the two combs now. Notice that in some places there's a tooth of the second comb matching a tooth that is next to it in this new position, and in other places there's a tooth that is NOT matched by another comb, and others with both are missing. Wherever there are two that match, leave that one in place. Where there are two that don't match up, cut that tooth off of the stationary comb.

    Count is incremented to 1.

    Now, duplicate the stationary comb. Slide it one to the right and repeat.

    As you repeat this, if there are any teeth remaining on the stationary comb, keep sliding and counting.

    Repeat until the stationary comb is empty of all teeth.

    This process literally counts how many sequential "1's" are in place, because of this matching process in the sequence. If it takes 3 steps to cut all of the teeth off the stationary comb, there were 3 in sequence. If it takes 4 steps, there were 4 in sequence.

    This depends upon the nature of the "AND" logical test. For AND, where the two values are 1, the result will be 1 (the tooth is left in place). If the two values are zero, the result is zero. If either are 1 and the other 0, the result is zero (where the tooth is cut off). This is why the teeth are removed from the stationary comb at each step where any missing teeth match up. As the pattern walks the sliding comb to the right, this naturally leaves behind a non-zero result until a sufficient number of steps have completed to clear all the teeth, and that matches the number of the longest contiguous sequence of teeth.

    In Ones, the >> shifts data, the same as shifting the comb to the right one tooth.

    The & 0x7FFFFFFF is a way of keeping all bits except the highest one. The programmer probably was concerned about rolls, where the bit on the right rolls back into the left, but >> doesn't do that so it really doesn't matter on most CPU's.

    Now, the "data & shift" clause is what cuts the teeth of the stationary comb wherever there are not matching teeth.

    Returning i is the count of the contiguous sequence.

    The ZEROS function simply inverts all the buts using the XOR operator (all 0's become 1's, all 1's become zeros). So, when ONES is called, counting the ones in that flipped version, it is actually counting the zeros of the original value.

    In ALTERNATE, the incoming value is xored against a pattern. Hex 5 is binary 101, so this number 0x55555555 is an integer with every other bit alternating on or off.

    XOR flips bits in a peculiar pattern. Where both are 1, the result is 0. If either is 1 and the other 0, the result is 1. If both are zero the result is zero.

    So, for every other bit, where the patter 0x55555555 has a bit on, it will flip the incoming bit, but where the pattern has a bit off, it doesn't. Every other bit is flipped.

    So, if the incoming pattern is 101, this flips that to 000, and 010 is flipped to 111 - meaning that alternating sequences of the original are turned into contiguous sequences, which is then checked with both ONES and ZEROS, returning whichever is greater.

    That's about it.

  3. #3
    Registered User
    Join Date
    Feb 2019
    Posts
    1,078
    Quote Originally Posted by monther
    Code:
    int ONES(int data)
    {
      int i, shift;
    
      for (i = 0; data != 0; i++)
      {
        shift = (data >> 1) & 0x7FFFFFFF;    // shift right logical 
        data = data & shift;
      }
    
      return (i);
    }
    The line where you do the shift is "implementation dependent"... Right shifts can be arithmetic or logical. The AND with 0x7fffffff is smart, but there is an unanbiguous way to count the number of 1's:
    Code:
    int ONES(int data)
    {
      int count = 0;
    
      while ( data ) 
      { 
        // same as data & 0x80000000
        if ( data & (1U << ( sizeof(int)*8 - 1 ) ) ) 
          count++; 
        data <<= 1; 
      }
    
      return count;
    }
    Left shifts are always 'logical'...

    Of course, there is a faster and easier way (using GCC or CLANG):
    Code:
    #define ONES(x) __builtin_popcount((x))
    Last edited by flp1969; 07-09-2019 at 06:37 PM.

  4. #4
    C++ Witch laserlight's Avatar
    Join Date
    Oct 2003
    Location
    Singapore
    Posts
    28,413
    Quote Originally Posted by flp1969 View Post
    Of course, there is a faster and easier way (using GCC or CLANG):
    Code:
    #define ONES(x) __builtin_popcount((x))
    What's the reason behind the doubled parentheses? It doesn't look like there's a precedence pitfall to avoid.
    Quote Originally Posted by Bjarne Stroustrup (2000-10-14)
    I get maybe two dozen requests for help with some sort of programming or design problem every day. Most have more sense than to send me hundreds of lines of code. If they do, I ask them to find the smallest example that exhibits the problem and send me that. Mostly, they then find the error themselves. "Finding the smallest program that demonstrates the error" is a powerful debugging tool.
    Look up a C++ Reference and learn How To Ask Questions The Smart Way

  5. #5
    Registered User
    Join Date
    Jul 2019
    Posts
    5
    Thx guys

  6. #6
    Registered User
    Join Date
    Feb 2019
    Posts
    1,078
    Quote Originally Posted by laserlight View Post
    What's the reason behind the doubled parentheses? It doesn't look like there's a precedence pitfall to avoid.
    I got used to this. Everytime I write a macro, I use parentheses to avoid potential problems (even if there is none)...

  7. #7
    Registered User
    Join Date
    Apr 2017
    Location
    Iran
    Posts
    138
    Related worthy read on bit twiddlig is here.

  8. #8
    Registered User
    Join Date
    Feb 2019
    Posts
    1,078
    Ahh. I forgot to mention:
    Code:
    int ONES(unsigned int value)
    {
      int counter = 0;
    
      while ( value )
      {
        value &= value - 1;
        counter++;
      }
    
      return counter;
    }
    This is the probable implementation of __builtin_popcount() on Intel/AMD processors that don't support the popcnt instruction.

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Help me understand what the code does
    By Hawksed in forum C Programming
    Replies: 0
    Last Post: 03-27-2017, 09:32 AM
  2. Help to understand this code !
    By redred in forum C Programming
    Replies: 5
    Last Post: 03-14-2013, 10:31 AM
  3. I don't understand this code
    By Nazgulled in forum C Programming
    Replies: 2
    Last Post: 12-18-2007, 01:52 PM
  4. Need help to understand this STL code.
    By Hulag in forum C++ Programming
    Replies: 3
    Last Post: 04-26-2005, 01:59 PM
  5. I want to understand this code
    By BadProgrammer in forum C++ Programming
    Replies: 9
    Last Post: 12-18-2003, 02:39 PM

Tags for this Thread