bit operation challenge

PHP programming forum. Ask questions or help people concerning PHP code. Don't understand a function? Need help implementing a class? Don't understand a class? Here is where to ask. Remember to do your homework!

Moderator: General Moderators

Post Reply
alex.barylski
DevNet Evangelist
Posts: 6267
Joined: Tue Dec 21, 2004 5:00 pm
Location: Winnipeg

bit operation challenge

Post by alex.barylski »

1) I have a variable which is three bits long.
2) I need a quick bitwise operation (single statement) that returns FALSE if anymore than one bit is set (no ternary operator).

The user should only ever specify one field, but they might do otherwise which would yield inaccurate results.

So say: 011 is passed, I need a quick check to confirm it's more than a single bit set and thus returning false, so the function can be unit tested :)

I can't think of any combination of bitwise operators which would yield such a result - is it possible?

Cheers :)
User avatar
feyd
Neighborhood Spidermoddy
Posts: 31559
Joined: Mon Mar 29, 2004 3:24 pm
Location: Bothell, Washington, USA

Post by feyd »

You don't really need a bitwise operation.. you need a simple comparison.

Code: Select all

switch($foo & 7)
{
  case 1:
  case 2:
  case 4:
    // only one bit was set.

  default:
}
alex.barylski
DevNet Evangelist
Posts: 6267
Joined: Tue Dec 21, 2004 5:00 pm
Location: Winnipeg

Post by alex.barylski »

Heh...I'm failing to see how that works at least how it meets my requirements anyways :P

I just need a simple way of testing the 'state' to ensure *only* a single byte is set...

Using a fallthrough case would do that, but I would then again inside that last CASE need to implement some kind of check to act appropriately depending on the state. Thus the reason I thought some bitwise magic might work...

I'm missing something :)
User avatar
feyd
Neighborhood Spidermoddy
Posts: 31559
Joined: Mon Mar 29, 2004 3:24 pm
Location: Bothell, Washington, USA

Post by feyd »

You don't have to use fall through. That was just an example.

Code: Select all

if ($foo & 7 == 1) { doStuff(); }
elseif ($foo & 7 == 2) { doOtherStuff(); }
elseif ($foo & 7 == 4) { doSomeStuff(); }
Same concept, just more annoying to type quickly.
alex.barylski
DevNet Evangelist
Posts: 6267
Joined: Tue Dec 21, 2004 5:00 pm
Location: Winnipeg

Post by alex.barylski »

Although, logically, that is what i am trying to acocmplish, I am trying to do so *without* conditionals, ternary, switch, etc...

basically one big nasty statement :) Hoping some bitwise hack would reduce it to a couple of bitwise tricks and voila :)
User avatar
feyd
Neighborhood Spidermoddy
Posts: 31559
Joined: Mon Mar 29, 2004 3:24 pm
Location: Bothell, Washington, USA

Post by feyd »

With some logicals it can be accomplished, but what's the point?
alex.barylski
DevNet Evangelist
Posts: 6267
Joined: Tue Dec 21, 2004 5:00 pm
Location: Winnipeg

Post by alex.barylski »

Well for starters it's a challenge to see if anyone can devise an interesting solution to the problem using only bitwise operators in a single statement - logicals too I guess.

I don't want to use conditional statements or ternary operators, etc....thats the challenege :)

The point is, I have several functions which are passed flags and sometimes flags are mutually exclusive, in that only one flag may be set, if more than one are set, the result is unexpected.

Having a simple, fast bitwise statement which could tell me TRUE or FALSE could be used inside the function to indicate argument error, by simply returning FALSE or some other value.

Unit testing the interface only doesn't suffice, because flags are coming from anywhere and everywhere and many conditions dictate whether one flag is set or not.

You could I guess write countless tests to see if any combination broke the test, but I think it would be easier to handle this on the implementation side of things seeing how there are a few functions which take STATES. Also there is the added benefit that production time slip ups are also flagged, not just while unit testing.

I have always used an implementation test (using macros which disappear in release) strategy so it's natural for me to continue to do so. :)

In PHP it's not very efficient to load your code with implementation level checks as PHP doesn't have a preprocessor so unit testing in environments like this comes in handy, but we still shouldn't neglect implementation level testing, just try and make it as transparent as possible and as fast as possible - hence a single bitwise statement which could quickly do the trick :)

Cheers :)
User avatar
feyd
Neighborhood Spidermoddy
Posts: 31559
Joined: Mon Mar 29, 2004 3:24 pm
Location: Bothell, Washington, USA

Post by feyd »

Without comparisons, it will require more processing time and will be more confusing to read. Are you still sure you want an all bitwise and logical version?
alex.barylski
DevNet Evangelist
Posts: 6267
Joined: Tue Dec 21, 2004 5:00 pm
Location: Winnipeg

Post by alex.barylski »

Bitwise operations would take more processing time than several conditional statements?

I find that hard to believe, can you justify this with actual proof? :?

Readability is *not* the key, it's simply acting like a macro in C or atleast it's purpose. Simply return true or false is more than a single bit is set...
User avatar
feyd
Neighborhood Spidermoddy
Posts: 31559
Joined: Mon Mar 29, 2004 3:24 pm
Location: Bothell, Washington, USA

Post by feyd »

What have you come up with as a solution?
alex.barylski
DevNet Evangelist
Posts: 6267
Joined: Tue Dec 21, 2004 5:00 pm
Location: Winnipeg

Post by alex.barylski »

based on my understanding of compilers and assembly, typically bitwise operations are faster in terms of execution speed...any conditional almost always requires a jump instruction, in addition to logical/bitwise tests, thus my confusion...

Maybe i'm not understanding properly. :)

Here are a few solutions:

Code: Select all

(((x&1) + ((x&2)>>1) + ((x&4)>>2)) == 1);
((x&7) && !((x&3) || (x&5) || (x&6));

Code: Select all

b & (b - 1) is false for all powers of two

Code: Select all

!(((a^110b)+((a^101b)>>1)+((a^011b)>>2))>>1)

Code: Select all

!(((a^110b)+((a^101b)>>1)+(a>>2))>>1)
None of these I constructed myself, but apparently do as I requested :)
Post Reply