Parsing Bits

[MadGypsy]

I've been tossing some things around in my head, just various puzzles and what-not. One in particular has me stumped (sort of).

In QC spawnflags are powers of two. If I was to write a script in some other language that utilized the spawnflag system, what would be the most efficient way to parse out the proper power of 2 values, from a variable that contains multiple "flags"?

The keyword here is efficient. I have a way, but I believe it is probably the stupid way.

[MadGypsy]

hmmm, I was clear in my question, but not clear in the answer I am looking for

function isThisBitInMe (bit, bitHolder)
{
	//what do I do here
}

to quake the use of that function

	someVar = isThisBitInMe(SOME_FLAG, self.spawnflags)

note that this is not for quake at all, this is because I am always parsing something. I threw some QC concepts/vars in there because the puzzle resides in quake functionality and in the case of the last code block any QC programmer will get what type of data I am trying to get into a function, making what I am trying to get out of the function also obvious (a boolean).

I am also not looking for the most obvious answer of simply using a bitwise operator to begin with. I'm trying to figure out the math behind this. The most efficient math. So, making an array of possible values and using that array as a comparison/detection system, is not gonna fly. That's not even really math actually. I need math.

[MadGypsy]

public class Bitwise
{	public function Bitwise():void{/*abstract - can't return values in the constructor*/}

	private function findMax(bitHolder:int):Int
	{	var maxValue:int = 0;
		for(var bit:int=0; pow(2, bit)<bitHolder; ++bit)
		{	maxValue = pow(2, bit);	
		}
		return maxValue;
	}

	private function getBits(bitHolder:int):Array
	{	var table:Array = new Array();
		var mV:int = 0;
		while(bitHolder > 0)
		{	mV =  findMax(bitHolder);
			table.push(mV);
			bitHolder -= mV;
		}
		return table;
	}

	public function bitwise(bit:int, bitHolder:int):Boolean
	{	return in_array(bit, getBits(bitHolder));
	}
}

var and:Class = new Bitwise();
var someBoolean:Boolean = and.bitwise(SOME_BIT, obj.flags);

For all intents and purposes, if I was writing these same concepts in an actual language, this would work. I don't like that it takes 3 methods, 2 Loops and an Array to get the answer. I'm also not really getting the bits. I'm process of elimination-ing the flags.

edit: I got bored, hard typed everything and classed it out. I guess now it's almost exactly AS3

[Spike]

In C-based languages (basically pretty much any language nowadays other than basic), the 'bitwise and' operator is expressed with the & character.

var someBoolean:Boolean = !!(obj.flags & SOME_BIT);

Some languages don't like you assigning an int directly to a boolean, hence the evil !! thing. moo har har.

you might also want to replace SOME_BIT with (1<<i) if you're looping through them. other than that, you're existing findmax function looks like its missing an = in the increment term.

[R00k]

im gonna make a t-shirt with

"moo har har"
on it

[MadGypsy]

bit+=bit (lol) ooops (it was only concept code anyway, based on ECMA standards, I guess). Well, really it's all messed up, because this is just a bunch of procedures and what I really want is the math behind this. Like an actual math formula. My procedures describe the formula though.

1) some math formula that returns the highest power of 2 within the number (this would be a huge start)
2) the remainder
3) is SOME_FLAG the result or the remainder
4) if neither and repeatable - repeat

In C-based languages (basically pretty much any language nowadays other than basic), the 'bitwise and' operator is expressed with the & character.

I am also not looking for the most obvious answer of simply using a bitwise operator to begin with.

I know about left and right shift but I don't understand how they work. I'll read up on it later (or right now).

edit: OK I understand shift now. (thank you wikipedia)

!!

LOL, I'm not doing that in my code.

[Spike]

! changes a 0 to 1 and a non-0 to 0.
!! changes a non-0 to 1, and a 0 to 0. woo.
so o|=(!!(i&(1<<4)))<<6; will set bit 6 in o only if bit 4 is set in i. other bits in o are unchanged.
o &= ~(1<<0); will clear bit 0, others are unchanged. ~(1<<0) == ~1 == 0xfffffffe

[MadGypsy]

What does (~) tilde do? I don't think any of the languages that I know use that.

[Spike]

~ = bitwise not.
! = logical not.

~ just inverts the bits. 101010b becomes 010101b
! ors the bits together and inverts a single condition. 101010b -> 1b -> 0. _only_ 0 becomes 1.

[MadGypsy]

Whaddaya know, ECMA compliant scripts support that. I never knew, but I also don't spend any time playing with bits. Thank you, Sensei - I have grown wiser through your teachings.

[Zop]

You could repeat a right shift (>>) until you got to zero, and use a loop count to see how many iterations it took. Otherwise, you need a logarithmic function (of base two) to get the number you want.

[MadGypsy]

hmmm, the thing with this shift thingy is, I get it and I don't. I need to play with the values that it returns so I can see exactly how the information is being processed. I'm sure this is real simple for you guys, but my programming experience has never involved bits ever. I have never needed that functionality. I still don't need it.

This is an exercise for me. I am always trying to push my skills to another level AND I have this odd fascination with parsing things. I could probably parse your DNA if I had an example strand to work with.

[Solecord]

In some other code I deal with, I need to get a full list of ALL bits associated with a value, so I use the following function. Not sure if this helps you at all:

function getBitwiseValues($decimal)
{
    $bin = decbin($decimal);
    $total = strlen($bin);
    $stock = array();
    for ($i = 0; $i < $total; $i++)
    {
        if ($bin{$i} != 0)
        {
            $bin_2 = str_pad($bin{$i}, $total - $i, 0);
            array_push($stock, bindec($bin_2));
        }
    }
    return $stock;
}

and an example:

$a = 67;

print_r(getBitwiseValues($a));

outputs:

Array
(
    [0] => 64
    [1] => 2
    [2] => 1
)

[Solecord]

Oh, and if you're interested in parsing, figure out and write an easy to use PHP parser for x12 EDI documents to XML

[MadGypsy]

is this a trick question? All the EDI stuff I googled keeps leading me to XML. If not, could you provide me with a language reference? I googled and I can't find one.

If it's parsable and humanly readable, I can parse it.