[ Cola @ 16.10.2009. 13:13 ] @
Pozdrav :)

Zanima me kako u C# iz broja izvući indekse bitova gde u broju stoji 1.

npr iz broja 27 (11011) da dobijem niz 1, 2, 4 ,5

naravno znam raditi sa bitovima ali me zanima kako bi ovo najbrže radilo.

Npr ako je broj long (64 bita) da ne radim u nekoj for petlji pa da šiftujem masku 1 64 puta.

Znam da u asembleru postoji bsf ali kako da radim sa asemblerom iz C#???

Kako biste vi odradili ovaj posao (naravno optimizovano)

Hvala :D
[ Cola @ 19.10.2009. 17:53 ] @
Evo ako nisam bio jasan, na ovo sam mislio
Code:

        public Int32[] GetIndexsOfBits(UInt32 p_number)
        {
            UInt64 mask = 1;
            List<Int32> indexsOfBits = new List<Int32>();
            for (Int32 i = 0; i < 64; i++)
            {
                if ((p_number & (mask << i)) != 0)
                {
                    indexsOfBits.Add(i);
                }
            }
            return indexsOfBits.ToArray();
        }


Može li se ovo kako optimizovati?
[ sallle @ 20.10.2009. 02:33 ] @
ovo shiftovanje mozda moze da se optimizuje (mask<<i)

mogo bi da stavis
Code:

for (int i=0;i<64;i++)
{
 if ((p_number & mask)!=0)
   indexofbits.add(i);
 mask = mask<<1;
}


to ce da optimizuje pod pretpostavkom da je procesoru jeftinije da odradi shift za jedno mesto, neg za n mesta;

Ono sto tebi ovde obesmisljava uopste rad na optimizaciji je koriscenje list<int> strukture.

[ Cola @ 20.10.2009. 06:53 ] @
Znam da korištenje List nije jeftino sa te strane ali me samo interesovao ovaj dio o kome si pisao.
Zamia me samo da li se nešto slično ovome
može iskoristiti
[ Cola @ 22.10.2009. 21:47 ] @
Mislim da sam pronašao rešenje

ChessAssember.h file
Code:

using namespace System;

extern "C" __declspec(dllexport) int IndexOfFirstBit64(UInt64* p_x);


ChessAssember.cpp file
Code:

#include "stdafx.h"

#include "ChessAssember.h"

__declspec(dllexport) int IndexOfFirstBit64(UInt64* p_x)
{
    int result = 0;
    __asm
    {
            bsf ebx, dword ptr [p_x]
            jnz    DOWN_BIT_FOUNDED
            bsf ebx, dword ptr [p_x+4]    
            jz BIT_NOT_FOUNDED
            add    ebx, 32
        DOWN_BIT_FOUNDED:
            add ebx, 1
        BIT_NOT_FOUNDED:
            mov result, ebx
    };
    return result;
}


cs file
Code:

[DllImport("ChessAssember.dll")]
private static extern int IndexOfFirstBit64(UInt64 p_x);


Još moram napraviti sličnu funkciju
Code:

__declspec(dllexport) int GetFirstBitAndClear64(UInt64& p_x)

koja će vraćati index bita i poništiti taj bit tako da u sledećeoj iteraciji nebi naletio na njega, pa bi je mogao iskoristiti umjesto onog gore for-a
Optimizavija bi bila u tome da bi preskočio nula bitove.

Meni ovo treba za šah (kao što se vidi iz imena fajlova haha) u BitBoard reprezentaci pozicije, pa s obzirom da bi u jednom UInt64 mogao imati max 10 jedinica (npr. dva topa + još 8 promovisanih topova iz piuna)
vidim da mi je u najgorem slučaju 10 od 64 bita jednako jedinici, a tek kako se uzme u obzir da je često podignuta samo 1 ili dvije jedinice u celom broju optimizacija je velika (milioni poteza po malo vremena nabere se )

Naravno u ovom primjeru nisam provjeravao da li je 64-bitna arhitektura u kojoj se nebih bakćao sa niži i višim bitovima (bilo bi brže i lakše)

kada napišem kod postaviću ga ko zna možda nekom zatreba

[ Cola @ 17.03.2016. 13:54 ] @
Može ovako

Code:

    static int[] firstBitTable = {
      63, 30, 3, 32, 25, 41, 22, 33, 15, 50, 42, 13, 11, 53, 19, 34, 61, 29, 2,
      51, 21, 43, 45, 10, 18, 47, 1, 54, 9, 57, 0, 35, 62, 31, 40, 4, 49, 5, 52,
      26, 60, 6, 23, 44, 46, 27, 56, 16, 7, 39, 48, 24, 59, 14, 12, 55, 38, 28,
      58, 20, 37, 17, 36, 8
    };

    public static int GetIndexOfFirstBit(ulong p_number)
    {
      ulong b = p_number ^ (p_number - 1);
      uint fold = (uint)((b & 0xffffffff) ^ (b >> 32));
      return firstBitTable[(fold * 0x783a9b23) >> 26];
    }



Ako nekom zatreba :)