On Saturday, February 8, 1997 12:00:00 AM UTC-8, Guido van Rossum wrote: > > I installed modified versions of stringobject.c and stropmodule.c on our web > > server. They are accessible via > > > > http://www.automatrix.com/~skip/python/ > > Cool. I read your description and am very pleased with your > approach. Did you benchmark it with pystone yet? (I'm still waiting > for a better benchmark, but nobody has given me one yet... ;-) > > > Warning: This is just a first attempt. I've done some testing, but not a > > bunch. Use this on an experimental basis only. The code isn't yet properly > > packaged, and there are some definite warts on it. Feedback is welcome. > > I immediately went to resizestring (to check that you'd taken care of > it properly -- you have) and noticed that there's one easy > optimization there: when the new and old sizes fall in the same > bucket, you don't need to do anything except change the ob_size field. > > > One thing I haven't yet figured out is this: Given an arbitrary number, n, > > return the power of two that is equal to or greater than n *without writing > > a loop*. I can clearly do something like: > > > > for (i = 1; i < n; i <<= 1); > > > > Can it be done using a single bit-twiddling expression though? > > For numbers < 256 you can do it with a single table lookup, if you can > spare 256 bytes for the table. For larger numbers you can quickly > find the highest byte in the number that's non-zero and use that to > index the table and add 8* the byte number (if you count from the > right end ;_)
Below is the code for this idea. #include <stdio.h> int log[256]; int next_power_of_two(int no) { int t, tt, r; if(tt = no>> 16) { r = (t = tt >> 8)?24+log[tt]:16+log[t]; } else { r = (t = no >> 8)?8+log[t]:log[no]; } return r; } void make_table() { int i; log[0] = 0; log[1] = 1; for(i=2;i<256;i++) { log[i] = 1 + log[i/2]; } } int main() { int no = 512; make_table(); printf ("%d\n", next_power_of_two(no)); } > > --Guido van Rossum (home page: http://www.python.org/~guido/) -- https://mail.python.org/mailman/listinfo/python-list