Navigacija
Lista poslednjih: 16, 32, 64, 128 poruka.

Indeksi bitova u broju, Kako?

[es] :: .NET :: Indeksi bitova u broju, Kako?

[ Pregleda: 2882 | Odgovora: 5 ] > FB > Twit

Postavi temu Odgovori

Autor

Pretraga teme: Traži
Markiranje Štampanje RSS

Cola
Slađan Čolić
Banja Luka

Član broj: 23736
Poruke: 160
*.lanaco.com.

Sajt: www.knjigaimena.com


+5 Profil

icon Indeksi bitova u broju, Kako?16.10.2009. u 13:13 - pre 175 meseci
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
 
Odgovor na temu

Cola
Slađan Čolić
Banja Luka

Član broj: 23736
Poruke: 160
*.broadband.blic.net.

Sajt: www.knjigaimena.com


+5 Profil

icon Re: Indeksi bitova u broju, Kako?19.10.2009. u 17:53 - pre 175 meseci
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?

 
Odgovor na temu

sallle
Sasa Ninkovic
GTECH
Beograd

Član broj: 146
Poruke: 480
91.148.83.*

ICQ: 20785904


+4 Profil

icon Re: Indeksi bitova u broju, Kako?20.10.2009. u 02:33 - pre 175 meseci
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.

 
Odgovor na temu

Cola
Slađan Čolić
Banja Luka

Član broj: 23736
Poruke: 160
*.lanaco.com.

Sajt: www.knjigaimena.com


+5 Profil

icon Re: Indeksi bitova u broju, Kako?20.10.2009. u 06:53 - pre 175 meseci
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

 
Odgovor na temu

Cola
Slađan Čolić
Banja Luka

Član broj: 23736
Poruke: 160
*.broadband.blic.net.

Sajt: www.knjigaimena.com


+5 Profil

icon Re: Indeksi bitova u broju, Kako?22.10.2009. u 21:47 - pre 175 meseci
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


 
Odgovor na temu

Cola
Slađan Čolić
Banja Luka

Član broj: 23736
Poruke: 160
*.lanaco.com.

Sajt: www.knjigaimena.com


+5 Profil

icon Re: Indeksi bitova u broju, Kako?17.03.2016. u 13:54 - pre 97 meseci
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 :)
 
Odgovor na temu

[es] :: .NET :: Indeksi bitova u broju, Kako?

[ Pregleda: 2882 | Odgovora: 5 ] > FB > Twit

Postavi temu Odgovori

Navigacija
Lista poslednjih: 16, 32, 64, 128 poruka.