Author: Heiner Marxen
Date: 14:48:25 07/07/03
Go up one level in this thread
On July 07, 2003 at 17:32:51, Gerd Isenberg wrote:
>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
Does look fine, also.
In the end one either has to do extensive benchmarking (measure time
on real hardware), or one has to go with a simple approach.
>>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'm very pleased that you recognize my estetic feelings :-))
>I will condsider it next time,
Really? Wow!
>>Well, it was fun to develop. :-)
>>
>>Happy micro-optimizing & Cheers,
>>Heiner
>
>Thanks & Cheers,
>Gerd
Deep in our hearts we chess programmers are real bit hackers, aren't we?
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.