Posts you want to find years later go here.
Peijen
Minion to the Exalted Pooh-Bah
Posts: 2790 Joined: Fri Jul 18, 2003 2:28 pm
Location: Irvine, CA
Post
by Peijen » Tue Aug 12, 2003 4:07 pm
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?
Jason
Veteran Doodler
Posts: 1520 Joined: Fri Jul 18, 2003 12:53 am
Location: Fairfax, VA
Post
by Jason » Tue Aug 12, 2003 4:37 pm
and with a bit mask and then check for true or false.
Jonathan
Grand Pooh-Bah
Posts: 6722 Joined: Tue Sep 19, 2006 8:45 pm
Location: Portland, OR
Contact:
Post
by Jonathan » Tue Aug 12, 2003 4:48 pm
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";
Peijen
Minion to the Exalted Pooh-Bah
Posts: 2790 Joined: Fri Jul 18, 2003 2:28 pm
Location: Irvine, CA
Post
by Peijen » Tue Aug 12, 2003 5:06 pm
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.
Last edited by
Peijen on Tue Aug 12, 2003 5:10 pm, edited 1 time in total.
Peijen
Minion to the Exalted Pooh-Bah
Posts: 2790 Joined: Fri Jul 18, 2003 2:28 pm
Location: Irvine, CA
Post
by Peijen » Tue Aug 12, 2003 5:09 pm
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.
Last edited by
Peijen on Tue Aug 12, 2003 5:13 pm, edited 1 time in total.
Jonathan
Grand Pooh-Bah
Posts: 6722 Joined: Tue Sep 19, 2006 8:45 pm
Location: Portland, OR
Contact:
Post
by Jonathan » Tue Aug 12, 2003 5:12 pm
Use an STL map? Because that's what this really is, is a hash.
Jonathan
Grand Pooh-Bah
Posts: 6722 Joined: Tue Sep 19, 2006 8:45 pm
Location: Portland, OR
Contact:
Post
by Jonathan » Tue Aug 12, 2003 5:13 pm
The answer, of course, is a recursive function that shifts bits until it sees a one. The race to write it starts... NOW!
Peijen
Minion to the Exalted Pooh-Bah
Posts: 2790 Joined: Fri Jul 18, 2003 2:28 pm
Location: Irvine, CA
Post
by Peijen » Tue Aug 12, 2003 5:14 pm
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 ...
Jonathan
Grand Pooh-Bah
Posts: 6722 Joined: Tue Sep 19, 2006 8:45 pm
Location: Portland, OR
Contact:
Post
by Jonathan » Tue Aug 12, 2003 5:16 pm
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.
Peijen
Minion to the Exalted Pooh-Bah
Posts: 2790 Joined: Fri Jul 18, 2003 2:28 pm
Location: Irvine, CA
Post
by Peijen » Tue Aug 12, 2003 5:18 pm
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;
}
}
Peijen
Minion to the Exalted Pooh-Bah
Posts: 2790 Joined: Fri Jul 18, 2003 2:28 pm
Location: Irvine, CA
Post
by Peijen » Tue Aug 12, 2003 5:19 pm
damn you for posting before I do, but my solution is better anyway ...
Jonathan
Grand Pooh-Bah
Posts: 6722 Joined: Tue Sep 19, 2006 8:45 pm
Location: Portland, OR
Contact:
Post
by Jonathan » Tue Aug 12, 2003 5:20 pm
Peijen wrote: damn you for posting before I do, but my solution is better anyway ...
you, sir, have no functional programming soul.
Peijen
Minion to the Exalted Pooh-Bah
Posts: 2790 Joined: Fri Jul 18, 2003 2:28 pm
Location: Irvine, CA
Post
by Peijen » Tue Aug 12, 2003 5:32 pm
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.
quantus
Tenth Dan Procrastinator
Posts: 4891 Joined: Fri Jul 18, 2003 3:09 am
Location: San Jose, CA
Post
by quantus » Tue Aug 12, 2003 8:50 pm
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.
Peijen
Minion to the Exalted Pooh-Bah
Posts: 2790 Joined: Fri Jul 18, 2003 2:28 pm
Location: Irvine, CA
Post
by Peijen » Tue Aug 12, 2003 9:18 pm
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.
VLSmooth
Tenth Dan Procrastinator
Posts: 3055 Joined: Fri Jul 18, 2003 3:02 am
Location: Varies
Contact:
Post
by VLSmooth » Sat Aug 16, 2003 2:24 am
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
quantus
Tenth Dan Procrastinator
Posts: 4891 Joined: Fri Jul 18, 2003 3:09 am
Location: San Jose, CA
Post
by quantus » Sat Aug 16, 2003 9:10 am
courses? what are those?
Jonathan
Grand Pooh-Bah
Posts: 6722 Joined: Tue Sep 19, 2006 8:45 pm
Location: Portland, OR
Contact:
Post
by Jonathan » Sat Aug 16, 2003 5:29 pm
quantus wrote: courses? what are those?
you don't have any left?
Jason
Veteran Doodler
Posts: 1520 Joined: Fri Jul 18, 2003 12:53 am
Location: Fairfax, VA
Post
by Jason » Sat Aug 16, 2003 6:18 pm
Dwindlehop wrote: quantus wrote: courses? what are those?
you don't have any left?
maybe that's why he keeps failing his PhD qualifier.
quantus
Tenth Dan Procrastinator
Posts: 4891 Joined: Fri Jul 18, 2003 3:09 am
Location: San Jose, CA
Post
by quantus » Sat Aug 16, 2003 8:01 pm
I haven't really had classes since Fall last year when I took one because I felt like it.