Author: Heiner Marxen
Date: 14:09:54 07/07/03
Go up one level in this thread
On July 06, 2003 at 23:25:00, Uri Blass wrote:
>In movei I have a number between 0 and 255 and I want to do some functions for
>every 1 that it has in its binary representation(number of functions to
>implement is the same as the number of 1's in the number and there is a
>different function based on the value of the 1)
>
>I do not like to call functions because functions use local varaibles and
>generating a copy of the local varaibles only to forget them may take computer
>time and I also do not use the functions more than once.
>
>I thought to use switch(see the code later in this post) but the problem is that
>switch continue to do everything without break and I want to have switch that
>does not continue to do everything but does not quit and simply forget about the
>fact that I called switch.
>
>Here is the type of the code that I plan to have now.
>I do not like all the if (number&2) or if (number&4) and the question is if I
>can do it faster.
>
>
>i=smallestpower[number];
>switch(i)
>{
> case 0:do list of commands
> if (number==1) break
> else
> {
> number-=1;
> i=smallestpower[number];
> }
> case 1:if (number&2)
> {
> do list of commands
> if (number==2) break;
> else
> {
> number-=2;
> i=smallestpower[number];
> }
> }
> case 2:if (number&4)
> {
> do list of commands
> if (number==4) break;
> else
> {
> number-=4;
> i=smallestpower[number];
> }
> }
> case 3:if (number&8)
> ...
> ...
> case 6:if (number&64)
> ...
> case 7://if you got there you know that number is 128 because you did not get
>out by break so you do not need to check it
>
>
>Uri
Ok, I'll try something...
The simplest approach:
if (n & (1<<0)) code_pos0;
if (n & (1<<1)) code_pos1;
if (n & (1<<2)) code_pos2;
if (n & (1<<3)) code_pos3;
if (n & (1<<4)) code_pos4;
if (n & (1<<5)) code_pos5;
if (n & (1<<6)) code_pos6;
if (n & (1<<7)) code_pos7;
What is bad about it? There are always exactly 8 bit tests.
We want to improve for the case, that few bits are set...
if (n & (1<<0)) { code_pos0; if (! (n -= (1<<0))) goto rdy; }
if (n & (1<<1)) { code_pos1; if (! (n -= (1<<1))) goto rdy; }
if (n & (1<<2)) { code_pos2; if (! (n -= (1<<2))) goto rdy; }
if (n & (1<<3)) { code_pos3; if (! (n -= (1<<3))) goto rdy; }
if (n & (1<<4)) { code_pos4; if (! (n -= (1<<4))) goto rdy; }
if (n & (1<<5)) { code_pos5; if (! (n -= (1<<5))) goto rdy; }
if (n & (1<<6)) { code_pos6; }
if (n & (1<<7)) { code_pos7; }
rdy:;
Now, after the last bit is done, we are really ready.
(That the last 2 cases omit the trailer is wanted.)
Still, we can do better to locate the first bit:
if (n & 0x0f) {
if (n & (1<<0)) { code_pos0; if (! (n -= (1<<0))) goto rdy; }
if (n & (1<<1)) { code_pos1; if (! (n -= (1<<1))) goto rdy; }
if (n & (1<<2)) { code_pos2; if (! (n -= (1<<2))) goto rdy; }
if (n & (1<<3)) { code_pos3; if (! (n -= (1<<3))) goto rdy; }
}
if (n & 0xf0) {
if (n & (1<<4)) { code_pos4; if (! (n -= (1<<4))) goto rdy; }
if (n & (1<<5)) { code_pos5; if (! (n -= (1<<5))) goto rdy; }
if (n & (1<<6)) { code_pos6; }
if (n & (1<<7)) { code_pos7; }
}
rdy:;
Whether the following is worth it, I don't know:
if (n & 0x0f) {
if (n & 0x03) {
if (n & (1<<0)) { code_pos0; if (! (n -= (1<<0))) goto rdy; }
if (n & (1<<1)) { code_pos1; if (! (n -= (1<<1))) goto rdy; }
}
if (n & 0x0c) {
if (n & (1<<2)) { code_pos2; if (! (n -= (1<<2))) goto rdy; }
if (n & (1<<3)) { code_pos3; if (! (n -= (1<<3))) goto rdy; }
}
}
if (n & 0xf0) {
if (n & 0x30) {
if (n & (1<<4)) { code_pos4; if (! (n -= (1<<4))) goto rdy; }
if (n & (1<<5)) { code_pos5; if (! (n -= (1<<5))) goto rdy; }
}
if (n & 0xc0) {
if (n & (1<<6)) { code_pos6; }
if (n & (1<<7)) { code_pos7; }
}
}
rdy:;
Whether you want a global around all that I'm not sure, either:
if( n & 0xff ) {
...the above...
}
I doubt that a switch can be significantly better than
such a bisection approach. But we can try it:
switch( number_of_lo_zero_in(n) ) {
if (n & (1<<0)) {
case 0: code_pos0; if (! (n -= (1<<0))) goto rdy;
}
if (n & (1<<1)) {
case 1: code_pos1; if (! (n -= (1<<1))) goto rdy;
}
if (n & 0x0c) {
if (n & (1<<2)) {
case 2: code_pos2; if (! (n -= (1<<2))) goto rdy;
}
if (n & (1<<3)) {
case 3: code_pos3; if (! (n -= (1<<3))) goto rdy;
}
}
if (n & 0xf0) {
if (n & 0x30) {
if (n & (1<<4)) {
case 4: code_pos4; if (! (n -= (1<<4))) goto rdy;
}
if (n & (1<<5)) {
case 5: code_pos5; if (! (n -= (1<<5))) goto rdy;
}
}
if (n & 0xc0) {
if (n & (1<<6)) {
case 6: code_pos6;
}
if (n & (1<<7)) {
case 7: code_pos7;
}
}
}
}
rdy:;
[ Look Ma, all those embedded case labels! ]
Yes, that is legal C (as far as I can tell).
No, I do not consider this to be readable. It is kind of perverse.
Well, it was fun to develop. :-)
Happy micro-optimizing & Cheers,
Heiner
This page took 0 seconds to execute
Last modified: Thu, 15 Apr 21 08:11:13 -0700
Current Computer Chess Club Forums at Talkchess. This site by Sean Mintz.