Go Down

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

#### HazardsMind

#15
##### May 31, 2013, 01:20 am
Ok, now I understand. I added an attachment of my findings
My GitHub:
https://github.com/AndrewMascolo?tab=repositories

#### FTPMonster

#16
##### May 31, 2013, 02:49 pm
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

#17
##### May 31, 2013, 04:04 pm
Quote
That's the first time in a long time I wished we could be transported (and translated) to PASCAL land...

Or APL.

#### AWOL

#18
##### May 31, 2013, 04:13 pm
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.
I speak for myself, not Arduino.

#### FTPMonster

#19
##### May 31, 2013, 09:09 pm

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

#22
##### May 31, 2013, 09:32 pm

Has to be 256

256 in byte form is 0.

#### FTPMonster

#23
##### May 31, 2013, 09:36 pmLast 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 pmLast 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

#25
##### May 31, 2013, 09:41 pm

@ 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

#26
##### May 31, 2013, 09:44 pm
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

#27
##### May 31, 2013, 09:50 pm

@ 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

#28
##### May 31, 2013, 10:28 pm
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)

#29
##### Jun 01, 2013, 04:20 am
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