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);
}

---

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.

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))

---

Quote:

---

Originally Posted by flp1969

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.

Thx guys

Quote:

---

Originally Posted by laserlight

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)... :)

Related worthy read on bit twiddlig is here.

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.