Visualizzazione dei risultati da 1 a 5 su 5
  1. #1

    [C#] ricerca bit a "1" più significativo

    Ciao a tutti,
    qual'è secondo voi il metodo più efficace (in termini di velocità/prestazioni) per trovare la posizione del bit a "1" più significativo in un numero di 64bit (ulong)?

    Esempio (su 8 bit):
    codice:
                ----------
    posizione: | 01234567 |
    valore:    | 00010110 |
                ----------
    devo ottenere 3, senza però effettare cicli pesanti tipo scorrere tutti i bit fino al primo "1"...

    Mi viene in mente una ricerca dicotomica, ma forse c'è di meglio...

    Grazie
    Luciano

  2. #2
    Quote Originariamente inviata da Luciano79 Visualizza il messaggio
    Ciao a tutti,
    qual'è secondo voi il metodo più efficace (in termini di velocità/prestazioni) per trovare la posizione del bit a "1" più significativo in un numero di 64bit (ulong)?

    Esempio (su 8 bit):
    codice:
                ----------
    posizione: | 01234567 |
    valore:    | 00010110 |
                ----------
    devo ottenere 3, senza però effettare cicli pesanti tipo scorrere tutti i bit fino al primo "1"...

    Mi viene in mente una ricerca dicotomica, ma forse c'è di meglio...

    Grazie
    Luciano

    Per una ricerca dicotomica è necessario avere gli elementi ordinati e solitamente viene utilizzata quando sono "unici" quindi differenti fra loro... dunque con un array di soli 0 e 1 non credo possa essere efficace... in questo caso la ricerca dovrebbe essere sequenziale, non conosco altri metodi che possano avere meno complessità computazionale in questo caso..

  3. #3
    Vero Alex..

    Ho trovato questo per un numero a 32 bit, scritto in c.

    codice:
    inline int get_int_1_pos(int i)
    { int n=-1;
      if(i&0xffff0000) {n+=16;i>>=16;};
      if(i&0x0000ff00) {n+=8;i>>=8;};
      if(i&0x000000f0) {n+=4;i>>=4;};
      if(i&0x0000000c) {n+=2;i>>=2;};
      return n+i;
    }
    La logica è simile alla ricerca binaria (guardo metà dei bit, poi metà della metà, ecc...), sempre meglio di un ciclo su tutti i bit, ma le operazioni non sono poche, per ogni step si effettuano una and, una somma e uno shift.
    Sapete se c'è di meglio?

  4. #4
    Utente di HTML.it L'avatar di oregon
    Registrato dal
    Jul 2005
    residenza
    Roma
    Messaggi
    36,462
    Mah ... alla fine, una ricerca con uno scorrimento a sinistra, nella media dei casi, non è tanto lenta.
    Dipende poi da cosa ci devi fare con tanta velocità ...

    Anche il metodo dell'ultimo codice in C non è male ...

    Sicuramente questo è lento

    uint i = 0x80000000;
    int p = (int)(Math.Log((double)i) / Math.Log(2.0));
    No MP tecnici (non rispondo nemmeno!), usa il forum.

  5. #5
    Quote Originariamente inviata da oregon Visualizza il messaggio
    Dipende poi da cosa ci devi fare con tanta velocità
    Ho un albero che pò contenere miliardi di nodi. Ogni nodo contiene alcuni numeri a 64 bit (bitboard). Per alcuni di questi numeri devo fare la ricerca in oggetto.
    E' un chess engine, più riduco i tempi di ricerca più posso aggiungere nodi all'albero (e quindi aumentare la forza).
    Nella prima versione (per la quale non ho badato a "spese" di tempo, ma solo di memoria) per pensare fino a 6 mosse in là (3bianco+3nero) ci metto circa un minuto, un po' troppo.

    Ogni bit rappresenta una delle 64 caselle. In realtà quando i pezzi sono ancora tanti conviene scorrere a sinistra, è molto probabile (quasi certo) che nelle prime 8 caselle ci sia qualcosa. Il problema è quando iniziano a diminuire.
    Ultima modifica di Luciano79; 26-08-2016 a 16:46

Permessi di invio

  • Non puoi inserire discussioni
  • Non puoi inserire repliche
  • Non puoi inserire allegati
  • Non puoi modificare i tuoi messaggi
  •  
Powered by vBulletin® Version 4.2.1
Copyright © 2024 vBulletin Solutions, Inc. All rights reserved.