Counting Binary Bits

Hi,

I have a programme that returns 16bit binary numbers representing the on or off states of 16 vertically aligned photosensors. A sequence of 5 or 6 adjacent sensors are triggered at any one time by a passing object.

Does anyone see a way within the Arduino language to process each binary number to confirm that at least 5 sequentially adjacent sensors have been triggered and to identify the position of the most significant "high" bit?

For example:

for 1111100000000000 the programme would identify that there are 5 adjacent bits set high and return "16" as the highest set bit.
for 0001111110000000 the programme would identify that there are 6 adjacent bits set and return "13" as the highest set bit.
for 0110011100000000 the programme would identify that set bits are not adjacent allowing identification of a read error.

I have been trying to think of an efficient way to do it using the bitread() function, but have struggled to come up with something. Any ideas?

Thanks,

Ross

rossco_50:
Does anyone see a way within the Arduino language ...

Which is C++, if that helps.

How about bit shifting the number to the right until all the 0's are gone, then shifting to the right and counting the 1's and then checking the remainder.

void magicProcessor(unsigned int x) {
  byte bit = 0;
  byte consecutive = 0;
  byte err = 0;
  if (x > 0)
  { //we have a value, analyse the bits
      //shift the bits until we lose all the leading zero's
      while (!(x & 1))
      {
          x >>= 1;
          bit++;
      }
      //count the consecutive ones
      while ((x & 1))
      {
          x >>= 1;
          bit++;
          consecutive++;
      }
      //if x still have a value, then there were non-consecutive bits
      if (x != 0)
      {
          err = 1;
      }
  }
  //Bit contains the highest ON bit position
  //consecutive contains the number of consecutive ON bits
  //err contains 1 if there were any non-consecutive bits
  //Do something meaningful with it now.
}

Same code as above, but just shortened, if that is your goal:

void magicProcessor(unsigned int x) {
  byte highestBit = 0;
  byte consecutive = 0;
  byte err = 0;
  if (x)
  { //we have a value, analyse the bits
      for (; !(x & 1); x >>= 1) highestBit++;
      for (; (x & 1); x >>= 1) { highestBit++; consecutive++; }
      err = (x != 0);
  }
  //do something with values
}
const unsigned int a1 = 0xf800;    //1111100000000000
const unsigned int a2 = 0x1f80;    //0001111110000000
const unsigned int a3 = 0x6700;    //0110011100000000

void setup() {
    // put your setup code here, to run once:
    Serial.begin(9600);
}

void loop() {
    // put your main code here, to run repeatedly: 
    int x = findFive(a1);
    Serial.println(x);
    x = findFive(a2);
    Serial.println(x);
    x = findFive(a3);
    Serial.println(x);
    Serial.println();
    delay(5000);
}

int findFive( unsigned int number){

    for (int x=0; x<12; x++){
        if ((number & 0xf800) == 0xf800){
            return 16-x;
        }
        number = number << 1;
   }
    return 0;
}

as there must be minimal 5 bits set the value of number must at least be 31 which can be used as a quick failure test.

int findFive( unsigned int number)
{
  if (number < 31) return 0;

  for (int x=0; x<12; x++){
    if ((number & 0xf800) == 0xf800) return 16-x;
    number = number << 1;
  }
  return 0;
}

If you are just looking for 5 consecutive bits in 16 there are only 10 or 11 values that have meaning (1111100000000000, 0111110000000000, 0011111000000000, etc). It may be just as fast to have an array of these values and check for them in a loop.

marco_c:
If you are just looking for 5 consecutive bits in 16 there are only 10 or 11 values that have meaning (1111100000000000, 0111110000000000, 0011111000000000, etc). It may be just as fast to have an array of these values and check for them in a loop.

5 or 6 consecutive 1's - soon gets too many cases to test for equality, probably more reasonable to loop with a mask. You probably want to avoid triggering on all 1's so perhaps the loop test should be against the bit patterns 0111110 and 01111110.

In general we need a function to find a mask. As the mask can contain (leading) zeros e.g. mask==B0110, the length is needed as param.

something like this (not extensively tested)

int findMask(unsigned int number, unsigned int mask, int length)
{
  unsigned int ones = 0;  
  for (int i=0; i< length; i++) ones = (ones << 1) + 1;  // create a "select bits to test mask"

  for (int pos=length-1; pos < 16; pos++)
  {
    if ( ((number & ones)^mask) ==0)  // xor to test for both 0's and 1's; the "& ones" masks the bits under test.
    {
      return pos;
    }
    number >>=1;
  }
  return -1;  // as a single bit pattern can be on pos 0 we need a negative number for not found
}

-- update
Note that if you have 6 or more consequetive bits set than the answer depends if you search from left to right or vice versa.

Good idea, saves possible unnecessary work to start with, I had only looped for 11 bits anyway (16-5) to save wasted time at the end.

robtillaart:
as there must be minimal 5 bits set the value of number must at least be 31 which can be used as a quick failure test.

You guys are still missing a requirement: Are all bits adjacent or not.

My function will count the number of adjacent bits, whether it is 5, 6, 2, 10 or any other number, it reports the highest bit in the first adjacent run, regardless of its length, and it reports whether or not there are non-adjacent bits.

I've included the complete program here again:

void magicProcessor(unsigned int x) {
  byte highestBit = 0;
  byte consecutive = 0;
  byte err = 0;
  if (x)
  { //we have a value, analyse the bits
      for (; !(x & 1); x >>= 1) highestBit++;
      for (; (x & 1); x >>= 1) { highestBit++; consecutive++; }
      err = (x != 0);
  }
  Serial.print(F("Highest bit: "));
  Serial.println(highestBit);
  Serial.print(F("Number of consecutive bits: "));
  Serial.println(consecutive);
  Serial.print(F("Are all bits adjacent?: "));
  Serial.println(err ? "No!" : "Yes");
}

void setup() { 
  Serial.begin(19200);
  magicProcessor(0b1111100000000000); 
  magicProcessor(0b0001111110000000); 
  magicProcessor(0b0110011100000000); 
}

void loop() { }

Thank you all for your quick and helpful replies.

Nick, thanks, I admit I did not think to look for general c++ examples. I have since found some examples of C++ binary bit counting functions which are closer to the suggestions here than I was with bitread(). Bit Twiddling Hacks

TRex, I agree your code does exactly what I was looking and is flexible which will be useful if using different sized trigger objects and dealing with phantom trigger events (which are happening in practice). I have 4 arrays in the experiment settup which may also grow to 32 bit each. In the first and fourth array I would expect more significant bits to be set and for arrays 2 and 3 I would expect less significant bits to be set. Even more efficiency could gained by defining a second function shifting bits to the left to be called when checking the likely more significant bit arrays.

I think it would also be an idea to include quick error checks as proposed by Riva and robtillaart.

Really great, thanks.

Ross

TRex:
You guys are still missing a requirement: Are all bits adjacent or not.

The code I had posted will return the number of the first bit of a 5 or more sequence or zero if no 5+ sequence found. The 0xf800 mask is the clue.

int findFive( unsigned int number)
{
  if (number < 31) return 0;

  for (int x=0; x<12; x++){
    if ((number & 0xf800) == 0xf800) return 16-x;
    number = number << 1;
  }
  return 0;
}