Page 2 of 4
Log of 2
Posted: Tue Aug 12, 2003 4:07 pm
by Peijen
is there a easy way to deteremine the log of 2 without using the log function?
let's say i have the following
Code: Select all
enum shit {
black = 1,
brown = 2,
yellow = 4,
green = 8,
red = 16
};
unsigned char *tag;
I want tag[0] to be associated to black, tag[1] to brown and so on. What's the fastest way of deremining log of 2 without a look up table?
Posted: Tue Aug 12, 2003 4:37 pm
by Jason
and with a bit mask and then check for true or false.
Posted: Tue Aug 12, 2003 4:48 pm
by Jonathan
Use less memory with an unsigned int instead of a char *.
Code: Select all
const unsigned int black = 1;
const unsigned int brown = 2;
const unsigned int yellow = 4;
const unsigned int green = 8;
const unsigned int red = 16;
unsigned int tag;
tag = dostuff();
if (tag & black) cout << "tag is black\n";
Posted: Tue Aug 12, 2003 5:06 pm
by Peijen
Dwindlehop wrote:Use less memory with an unsigned int instead of a char *.
it's not really a char*, it's actually char [log2(ubound)+1].
Here is how I want to use this.
Code: Select all
enum shit {
black = 1,
brown = 2,
yellow = 4,
green = 8,
red = 16
};
unsigned char tag[5];
shit a;
void addshit(shit s, char t) {
a &= s;
if (s & black) {
tag[0] = t;
} // etc
}
char shitwhat(shit s) {
if (a & s) {
switch (s) {
case black:
return tag[0];
// etc
}
}
}
I am will aware of bit mask and stuff, it's extra information associated with each flag that I am interest in.
Posted: Tue Aug 12, 2003 5:09 pm
by Peijen
oops should finish typing before hit submit.
What I wanted is less if/swtich statment so the code would look like this
Code: Select all
void addshit(shit s, char t) {
a &= s;
tag[log(s)] = t;
}
char shitwhat(shit s) {
if (a & s) return tag[log(s)];
}
This way I can add new element to enum without adding extra code to handle each of them. However I don't want to use the <math.h>'s log function since it's probably slower and more complex than what I needed.
Posted: Tue Aug 12, 2003 5:12 pm
by Jonathan
Use an STL map? Because that's what this really is, is a hash.
Posted: Tue Aug 12, 2003 5:13 pm
by Jonathan
The answer, of course, is a recursive function that shifts bits until it sees a one. The race to write it starts... NOW!
Posted: Tue Aug 12, 2003 5:14 pm
by Peijen
Dwindlehop wrote:Use an STL map? Because that's what this really is, is a hash.
well memory size and all that, but you are probably right. Why write your own code when others already did it ...
Posted: Tue Aug 12, 2003 5:16 pm
by Jonathan
Code: Select all
int log2(int a) {
// base case
if(a == 1)
return 0;
else
return 1+log2(a>>1);
}
This only works for powers of two. But that's what you asked for.
Posted: Tue Aug 12, 2003 5:18 pm
by Peijen
Dwindlehop wrote:The answer, of course, is a recursive function that shifts bits until it sees a one. The race to write it starts... NOW!
What this is what I don't want to do ...
long index(unsigned long x)
{
long j = 1;
for (int i = 0; i < -1; ++i) {
if ((j<<i) == x) return i;
}
}
Posted: Tue Aug 12, 2003 5:19 pm
by Peijen
damn you for posting before I do, but my solution is better anyway ...
Posted: Tue Aug 12, 2003 5:20 pm
by Jonathan
Peijen wrote:damn you for posting before I do, but my solution is better anyway ...
you, sir, have no functional programming soul.
Posted: Tue Aug 12, 2003 5:32 pm
by Peijen
Dwindlehop wrote:Peijen wrote:damn you for posting before I do, but my solution is better anyway ...
you, sir, have no functional programming soul.
What I ask for is speed, and less memory print. recursive function is alot worse than lookup table.
Posted: Tue Aug 12, 2003 8:50 pm
by quantus
Is this really going to be the inside of a tight loop where you really require speed? The sheer fact that you're resisting a hash (array in this case) is absurd if you really really want speed. It's the only thing where pointer arithmetic is quick and simple. Hint, to truly make this fast, make sure your compiler is aligning the array with the cache line. Anyways, you took 213, you know this shit.
Posted: Tue Aug 12, 2003 9:18 pm
by Peijen
quantus wrote:Is this really going to be the inside of a tight loop where you really require speed?
tell you the truth, not really. I have pretty much optimized all formular used in the program. The most of the time will be spend reading/writing data.
quantus wrote:The sheer fact that you're resisting a hash (array in this case) is absurd if you really really want speed. It's the only thing where pointer arithmetic is quick and simple. Hint, to truly make this fast, make sure your compiler is aligning the array with the cache line. Anyways, you took 213, you know this shit.
I am compareing my solution to Jon's. At this point I don't really care about cache performance, since I have no idea what kind of computer (processor) the broker is using, and I am not about to look up if there is difference between 486/P/Pii/Piii/Piv/Duran/Thunderbird/etc.
Posted: Sat Aug 16, 2003 2:24 am
by VLSmooth
quantus wrote:Anyways, you took 213, you know this shit.
Since you're talking about coursework, you KNOW you want to take 212 now. You'll love/hate it. Well, you'll at least hate it
Posted: Sat Aug 16, 2003 9:10 am
by quantus
courses? what are those?
Posted: Sat Aug 16, 2003 5:29 pm
by Jonathan
quantus wrote:courses? what are those?
you don't have any left?
Posted: Sat Aug 16, 2003 6:18 pm
by Jason
Dwindlehop wrote:quantus wrote:courses? what are those?
you don't have any left?
maybe that's why he keeps failing his PhD qualifier.
Posted: Sat Aug 16, 2003 8:01 pm
by quantus
I haven't really had classes since Fall last year when I took one because I felt like it.