Page 1 of 1
bit operation challenge
Posted: Fri Mar 16, 2007 9:26 pm
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

Posted: Fri Mar 16, 2007 9:35 pm
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:
}
Posted: Fri Mar 16, 2007 9:43 pm
by alex.barylski
Heh...I'm failing to see how that works at least how it meets my requirements anyways
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

Posted: Fri Mar 16, 2007 9:47 pm
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.
Posted: Sat Mar 17, 2007 12:05 am
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

Posted: Sat Mar 17, 2007 12:23 am
by feyd
With some logicals it can be accomplished, but what's the point?
Posted: Sat Mar 17, 2007 1:22 am
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

Posted: Sat Mar 17, 2007 8:29 am
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?
Posted: Sat Mar 17, 2007 1:13 pm
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...
Posted: Sat Mar 17, 2007 1:24 pm
by feyd
What have you come up with as a solution?
Posted: Sat Mar 17, 2007 5:36 pm
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
