Pages: 1 [2] 3   Go Down
Author Topic: How to check if a variable is a member of a set  (Read 696 times)
0 Members and 1 Guest are viewing this topic.
Queens, New York
Online Online
Faraday Member
**
Karma: 84
Posts: 3412
"Of all the things I've ever lost, I miss my mind the most" -Ozzy Osbourne
View Profile
 Bigger Bigger  Smaller Smaller  Reset Reset

Ok, now I understand. I added an attachment of my findings

* numbers.txt (1.83 KB - downloaded 11 times.)
Logged

Created Libraries:
NPV2 (NewPasswordV2),  TFT_Extension, OneWireKeypad, SerialServo.
Will provide libraries if asked in PM or forum.

Offline Offline
Jr. Member
**
Karma: 0
Posts: 55
View Profile
 Bigger Bigger  Smaller Smaller  Reset Reset

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. smiley

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

Logged

Offline Offline
Edison Member
*
Karma: 32
Posts: 1382
View Profile
 Bigger Bigger  Smaller Smaller  Reset Reset

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

Or APL.
Logged

Global Moderator
UK
Offline Offline
Brattain Member
*****
Karma: 290
Posts: 25730
I don't think you connected the grounds, Dave.
View Profile
 Bigger Bigger  Smaller Smaller  Reset Reset

Ah! yes, APL, the world's best write-only language.
Logged

"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.

Offline Offline
Jr. Member
**
Karma: 0
Posts: 55
View Profile
 Bigger Bigger  Smaller Smaller  Reset Reset

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:
  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:
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?

Logged

California
Offline Offline
Faraday Member
**
Karma: 88
Posts: 3357
View Profile
 Bigger Bigger  Smaller Smaller  Reset Reset

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:
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.
« Last Edit: May 31, 2013, 02:21:45 pm by Arrch » Logged

Queens, New York
Online Online
Faraday Member
**
Karma: 84
Posts: 3412
"Of all the things I've ever lost, I miss my mind the most" -Ozzy Osbourne
View Profile
 Bigger Bigger  Smaller Smaller  Reset Reset

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.
« Last Edit: May 31, 2013, 02:33:00 pm by HazardsMind » Logged

Created Libraries:
NPV2 (NewPasswordV2),  TFT_Extension, OneWireKeypad, SerialServo.
Will provide libraries if asked in PM or forum.

California
Offline Offline
Faraday Member
**
Karma: 88
Posts: 3357
View Profile
 Bigger Bigger  Smaller Smaller  Reset Reset

Has to be 256

256 in byte form is 0.
Logged

Offline Offline
Jr. Member
**
Karma: 0
Posts: 55
View Profile
 Bigger Bigger  Smaller Smaller  Reset Reset

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.
« Last Edit: May 31, 2013, 02:42:04 pm by FTPMonster » Logged

Queens, New York
Online Online
Faraday Member
**
Karma: 84
Posts: 3412
"Of all the things I've ever lost, I miss my mind the most" -Ozzy Osbourne
View Profile
 Bigger Bigger  Smaller Smaller  Reset Reset

@ 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.
« Last Edit: May 31, 2013, 02:40:44 pm by HazardsMind » Logged

Created Libraries:
NPV2 (NewPasswordV2),  TFT_Extension, OneWireKeypad, SerialServo.
Will provide libraries if asked in PM or forum.

California
Offline Offline
Faraday Member
**
Karma: 88
Posts: 3357
View Profile
 Bigger Bigger  Smaller Smaller  Reset Reset

@ 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.
Logged

Queens, New York
Online Online
Faraday Member
**
Karma: 84
Posts: 3412
"Of all the things I've ever lost, I miss my mind the most" -Ozzy Osbourne
View Profile
 Bigger Bigger  Smaller Smaller  Reset Reset

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
Logged

Created Libraries:
NPV2 (NewPasswordV2),  TFT_Extension, OneWireKeypad, SerialServo.
Will provide libraries if asked in PM or forum.

Offline Offline
Jr. Member
**
Karma: 0
Posts: 55
View Profile
 Bigger Bigger  Smaller Smaller  Reset Reset

@ 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. smiley
Logged

Global Moderator
Netherlands
Offline Offline
Shannon Member
*****
Karma: 211
Posts: 13479
In theory there is no difference between theory and practice, however in practice there are many...
View Profile
 Bigger Bigger  Smaller Smaller  Reset Reset

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



Logged

Rob Tillaart

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

Offline Offline
Sr. Member
****
Karma: 25
Posts: 499
View Profile
 Bigger Bigger  Smaller Smaller  Reset Reset

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:
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:
    if ((byte)((byte)((byte)i & (byte)15) == (byte)15))
No dice.  Still 16 bit math.

Code:
    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.
Logged

Pages: 1 [2] 3   Go Up
Jump to: