Go Down

Topic: How to check if a variable is a member of a set (Read 887 times) previous topic - next topic

HazardsMind

Ok, now I understand. I added an attachment of my findings
My GitHub:
https://github.com/AndrewMascolo?tab=repositories

FTPMonster

You folks are all amazing. To answer a question that wasn't ever asked, yes the numbers I picked all started with all 1's in binary. It's for a subnet mask for IP addresses. I'm debating whether or not to swap the 3 line solution with the existing 20+ line solution right now. :)

Oh, and I removed the Serial.print lines from my switch & case statements. I only left them in there to test. :)


KeithRB

Quote
That's the first time in a long time I wished we could be transported (and translated) to PASCAL land...


Or APL.

AWOL

Ah! yes, APL, the world's best write-only language.
"Pete, it's a fool looks for logic in the chambers of the human heart." Ulysses Everett McGill.
Do not send technical questions via personal messaging - they will be ignored.

FTPMonster


Of course you are not trying to see if a number is a member of a list really, you are trying
to if a byte is of the form  0b111...000  (ones followed by zeroes - or all ones, all zeroes)

There are usually clever bit-bashing methods for such a test.  Here that clever test is
Code: [Select]

  if (testNumber >= 0 && testNumber < 0x100)  // optionally check in 8 bit unsigned range
  {
    byte n = (byte) testNumber ;
    if (((n & -n) + n) == 0)   // clever part
    {
      ...



Well, we ran into a problem. While yes, it's incredibly clever, it doesn't work for zero. According to this code:
Code: [Select]

int subnetchecker(int testNumber)
// 0 if OK, 1 if failed
{
if (testNumber >= 0 && testNumber < 0x100)  // optionally check in 8 bit unsigned range
  {
    byte n = (byte) testNumber ;
    if (((n & -n) + n) == 256)   // clever part EDIT tweaked it
    {
      return 0;
    }
   else return 1;
}
}

it will resolve all but zero properly. Using 255 as an example, this function returns 0. But a zero returns 1. If I use your first example, where it's == 0 instead of == 256, it's reversed.

How do we get it to acknowledge zero as a valid subnet octet, without going back to the old case statements?


Arrch

#20
May 31, 2013, 09:19 pm Last Edit: May 31, 2013, 09:21 pm by Arrch Reason: 1

How do we get it to acknowledge zero as a valid subnet octet, without going back to the old case statements?


The quick and dirty way would be to add a secondary check:

Code: [Select]
if ( (((n & -n) + n) == 0) || n == 255)

I think the issue with it not working for 255 has to do with negation of unsigned variables and sign extension. Making n signed might help.

HazardsMind

#21
May 31, 2013, 09:30 pm Last Edit: May 31, 2013, 09:33 pm by HazardsMind Reason: 1
Has to be 256. If you print "(n & -n) + n" with a for loop of 0 => 255, the ones he is looking for will all say "256" as an output.
My GitHub:
https://github.com/AndrewMascolo?tab=repositories

Arrch


FTPMonster

#23
May 31, 2013, 09:36 pm Last Edit: May 31, 2013, 09:42 pm by FTPMonster Reason: 1

I think the issue with it not working for 255 has to do with negation of unsigned variables and sign extension. Making n signed might help.


255 works fine, as well as all the other numbers. It's just zero that has the problem.

HazardsMind

#24
May 31, 2013, 09:38 pm Last Edit: May 31, 2013, 09:40 pm by HazardsMind Reason: 1
@ Arrch
I understand, but when you set it equal to zero, it does not show anything. Maybe it needs to be "if( (byte)((n & -n) + n) == 0)"
I cant test this now.
My GitHub:
https://github.com/AndrewMascolo?tab=repositories

Arrch


@ Arrch
I understand, but when you set it equal to zero, it does not show anything. Maybe it needs to be "if( (byte)((n & -n) + n) == 0)"


Yeah that, or mask away the higher order byte.

HazardsMind

Either way will work, I just don't understand why were telling it to be casted as a byte and the compiler doesn't understand that if it does equal 256 to make it 0.

The compiler is skrewy
My GitHub:
https://github.com/AndrewMascolo?tab=repositories

FTPMonster


@ Arrch
I understand, but when you set it equal to zero, it does not show anything. Maybe it needs to be "if( (byte)((n & -n) + n) == 0)"
I cant test this now.


Just did, works perfectly. :)

robtillaart

See book Hackers delight or - http://graphics.stanford.edu/~seander/bithacks.html - for many clever tricks



Rob Tillaart

Nederlandse sectie - http://arduino.cc/forum/index.php/board,77.0.html -
(Please do not PM for private consultancy)

TanHadron

Quote
Either way will work, I just don't understand why were telling it to be casted as a byte and the compiler doesn't understand that if it does equal 256 to make it 0.

The compiler is skrewy


It's worse than that.  If you don't put the type cast in there, the compiler does 16 bit computations.  Somehow that particular typecast makes it use 8 bit math on that formula.  I tried typecasting in different places and I don't understand how it works.

So I tried this:
Code: [Select]

void loop()
{
  byte i;
  byte n;

  for (i = 0; i < 255; ++i)
  {
    n = (i & -i) + i;
    Serial.print(n);
    Serial.print("\t");
    if ((i & 15) == 15)
      Serial.println();
  }
  for(;;);
}


The i in the loop is done with 16 bit math.  What's up with that?!?  I commented out the line if((i & 15) == 15) and it did the 8 bit math.  Maybe if I type casted the i?

Code: [Select]
    if ((byte)((byte)((byte)i & (byte)15) == (byte)15))

No dice.  Still 16 bit math.

Code: [Select]
    n = i & 15;
    if (n == 15)

OK.  That works.

So doing a formula in an if block flags the calculation as a 16 bit calculation?  And doing a 16 bit calculation on a loop variable flags the loop calculations as 16 bit?  Weird.

Go Up