Author: Gerd Isenberg
Date: 14:32:51 07/07/03
Go up one level in this thread
On July 07, 2003 at 17:09:54, Heiner Marxen wrote:
>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:;
Or Andrew's one?
http://www.talkchess.com/forums/1/message.html?305255
>
>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.
>
It really looks esthetic.
The way you release the ifs to leave the labels in same column - great.
I will condsider it next time,
>Well, it was fun to develop. :-)
>
>Happy micro-optimizing & Cheers,
>Heiner
Thanks & Cheers,
Gerd
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.