Newsgroup: it.comp.programmare
Titolo: Numero di bit

Qualcuno sa dirmi un modo ***veloce*** di calcolare il numero di bit
necessari ad immagazzinare un numero interno.
Un modo standard è:
short num;
int cont=0;
while(num)
{
    num>>=1;
    cont++;
}
Alla fine cont mi da il numero di bit necessari ad immagazzinare num.
Io però ho problemi di velocità e vorrei fare tutto in un modo più veloce.
Avete idee?

, Dario Marchese ha scritto:

E` veramente questo il corpo del codice che impiega piu` tempo ad
essere eseguito?
Se proprio ti puo` essere utile (ma dubito che migliori le
prestazioni) prova a fare una ricerca binaria:
es. num = 0000 0101 0110 0000 (raggruppo le cifre 4 a 4, per
semplicita`, chiaramente num l'ho espresso in binario ed ho assunto
che sia a 16 bit)
fai un and con 1111 1111 0000 0000, se il risultato non e` zero allora
vuol dire che la prima cifra e` nella parte piu` a sinistra,
altrimenti a destra. In questo caso il risultato e` diverso da zero.
Allora facciamo un and con 1111 0000 0000 0000
che e` zero, quindi la prima cifra deve essere in
  0000 1111 0000 0000
ergo possiamo anche risparmiarci questo and e proseguiamo con
  0000 1100 0000 0000
ecc...
Spero di essere stato chiaro.
Se vuoi fare le cose veramente velocemente dovresti gestire tutte le
possibili combinazioni senza fare un ciclo. Mi sembra comunque
veramente assurdo ottimizzare questo codice cosi` tanto almeno che non
ce ne sia VERAMENTE la necessita`.
Maurizio
-- 
The last thing one knows in constructing a work is what to put first.
                -- Blaise Pascal

 necessari ad immagazzinare un numero interno.
[cut]
L'arrotondamento superiore del logaritmo in base due del numero?
-- 
{}-{}-{}-{}-{}-{}-{}-{}-{}-{}-{}-{}-{}-{}-{}-{}-{}-{}-{}-{}-{}-{}-{}-{}-{}-{}
SunGray aka Gabriele Lana
contact me @ 
sun...@tiscalinet.it
See you space cowboy ...

 L'arrotondamento superiore del logaritmo in base due del numero?
Beh... non proprio: il log in base 2 di 0 e` impossibile da fare. ;)))


 necessari ad immagazzinare un numero interno.
l'operatore sizeof dovrebbe fare al caso tuo, se usi C++.
-- 
Ikitt

l'operatore sizeof dovrebbe fare al caso tuo, se usi C++.
sizeof restituisce un risultato in byte, non in bit.

Dario Marchese wrote:

Visto che uno short puo` contenere un numero finito di valori IMHO la 
cosa migliore e` preprocessare una tabella in cui memorizzi i risultati:
#include <limits.h>
typedef struct
{
  unsigned short max;
  int bits;
} Pair;
#define SHORT_BIT (sizeof(short) * CHAR_BIT)
Pair numBits[SHORT_BIT];
void init()
{
  int i;
  for(i=0; i<SHORT_BIT; i++)
    {
      numBits[i].max = (1 << (i+1)) - 1;
      numBits[i].bits = i+1;
    }
}
int how_many_bits(unsigned short n)
{
  int i;
  for(i=0; i<SHORT_BIT; i++)
    {
      if (n <= numBits[i].max)
        return numBits[i].bits;
    }
}
Volendo in how_many_bits puoi anche utilizzare la ricerca binaria, ma non 
so fino a che punto ne valga la pena.
ciao Anto
-- 
"Computer science is not about computers any more than astronomy
is about telescopes." -- EW Dijkstra

 ha scritto nel messaggio
news:28c0ua...@anto.cuni.lan...


Grazie a tutti per l'interessamento.
Io nel mentre ho migliorato la velocità dell'algoritmo:
short num, last_num;
int cont=0;
last_num=num;
while(num)
{
    last_num=num;
    num>>=2;
    cont+=2;
}
if(last_num==1)
    cont--;
Così è veloce quasi il doppio.
Io speravo però esistesse una soluzione senza cicli.....
Dario
"Dario Marchese" <x...@xxx.xx> ha scritto nel messaggio
news:XIIM9.12994$R45.5...@news2.tin.it...


 ha scritto nel messaggio
news:bXVM9.477$lj5....@tornado.fastwebnet.it...


Considerate che sono fermo al diploma di ragioneria e che ho soltanto
intuito questa sera dal messaggio che cosa sia un logaritmo..
int(log2(x)) + 1
vale con x > 0
Che ne pensate? Ho detto una cazzata? :)
(Log2(x) significa trovare l'elevazione a potenza che applicata a 2
permette di avere x? Ho intuito correttamente?)



Sì, Log2(x) è l'esponente da dare a due per ottenere x... ma dubito
che sia una grande ottimizzazione...
Augusto Pucci
http://www.neuraldaemon.com/pucci

che sia una grande ottimizzazione...
Se ha bisogno di velocita' se sta programmando in c puo' includere del
codice assembly che con il decremento di un registro, lo shift del
registro col numero e un salto condizionato a seconda dell'eventuale
overflow dello shift faccia il conteggio che gli serve. Piu' veloce di
cosi' non esiste niente.

 C'č da fare 2 logaritmi e una divisione....
Si potrebbe sapere per cosa ti serve questo algoritmo? Sei sicuro che sia 
cosě lento? Quante volte devi eseguire questo codice?
-- 
Marco Barisione  (ICQ 84277092)
Vota per la creazione di it.comp.software.editor seguendo le istruzioni
contenute nel messaggio news://
MK.it.comp.soft...@news.nic.it

 ha scritto nel messaggio
news:10f271o8...@marco.barisione...


 ha scritto nel
messaggio news:b21a0voh577s7lbbe...@4ax.com...


 dello stream MPEG in memoria.
Allora potresti vedere tra i sorgenti di 
ffmpeg.sf.net
 (cerca lo snapshot CVS)
per vedere come fa lui.
Perche` quei codec sono molto buoni e molto veloci, oltre che opensource :)
Solo un suggerimento :)
-- 
Ikitt

,
Agamennone ha scritto:

Il punto e` che devi dare l'implementazione di log2(x).
Maurizio


 sprecendo in più memoria per la tabella e tempo per accedere ad essa!!
lo hai testato oppure e` un'analisi "a naso"?
In ogni caso se anche cosi` e` troppo lento puoi sempre spingere un po' 
piu` in la il compromesso spazio/tempo: uno short tipicamente ha 16 bit, 
quindi puoi sempre precalcolare una tabella di 2^16 elementi in cui 
memorizzi il numero di biti necessari per ognuno. In questo modo ogni 
ricerca corrisponde ad un accesso diretto in memoria.


 veloce.
La ricerca binaria, seconda me,  rimane il metodo migliore.
---senza loop, please---
Per short a 16 bit:
unsigned short val;
int count = 0;
if (val >= 256)
{
    count += 8;
    val >>= 8;
}
if (val >= 16)
{
    count += 4;
    val >>= 4;
}
if (val >= 4)
{
 count += 2;
 val >>= 2;
}
if (val >= 2)
{
 count++;
 val >>= 1;
}
count += val;
Versione *senza* salti condizionali in ASM per IA-32
(l'ho scritto di getto quindi non ti garantisco che i cicli siano stati
minimizzati,
però è un punto di partenza...)
unsigned short val;
_asm
{
 xor edx, edx ; count = 0
 movzx eax, val
 xor ecx, ecx
 cmp eax, 256   ; if (eax < 256) CF = 1; else CF = 0;
 cmc                  ; CF = 1 - CF
                         ; (cioè if (eax >= 256) CF = 1; else CF = 0)
 adc ecx, ecx     ; ecx = CF
 shl ecx, 3          ; ecx = CF * 8
 add edx, ecx     ; count += ecx
 shr eax, cl         ; val >>= ecx
 xor ecx, ecx
 cmp eax, 16      ; if (eax < 16) CF = 1; else CF = 0;
 cmc                   ; CF = 1 - CF
                          ; (cioè if (eax >= 16) CF = 1; else CF = 0)
 adc ecx, ecx      ; ecx = CF
 shl ecx, 2           ; ecx = CF * 4
 add edx, ecx      ; count += ecx
 shr eax, cl          ; val >>= ecx
 xor ecx, ecx
 cmp eax, 4         ; if (eax < 4) CF = 1; else CF = 0;
 cmc                    ; CF = 1 - CF
                           ; (cioè if (eax >= 4) CF = 1; else CF = 0)
 adc ecx, ecx       ; ecx = CF
 shl ecx, 1            ; ecx = CF * 2
 add edx, ecx       ; count += ecx
 shr eax, cl           ; val >>= ecx
 xor ecx, ecx
 cmp eax, 2          ; if (eax < 2) CF = 1; else CF = 0;
 cmc                     ; CF = 1 - CF
                            ; (cioè if (eax >= 2) CF = 1; else CF = 0)
 adc ecx, ecx        ; ecx = CF
 add edx, ecx        ; count += ecx
 shr eax, cl            ; val >>= ecx
 add edx, eax
 mov count, edx
}
Kiuhnm

 veloce.
Chiedo scusa per il messaggio precedente...dovevo avere la testa altrove.
Già dal 386 esiste un'istruzione per trovare il primo bit settato (a partire
da destra o da sinistra).
unsigned int val = 0x6fad76;
int count;
_asm
{
    bsr    ecx, val            ; Bit Scan Reverse
    inc    ecx
    mov  count, ecx
}
// oppure...
unsigned short sval = 0x6fad;
_asm
{
    bsr    cx, sval            ; Bit Scan Reverse
    and   ecx, 0ffffh
    inc    ecx
    mov  count, ecx
}
Kiuhnm

 meglio.
come ti ho gia` detto la soluzione sta nel precalcolare la tabella:
#include <limits.h>
char bits[USHRT_MAX];
void init_bits()
{
  unsigned short i;
  for(i=0; i<USHRT_MAX; i++)
    {
      int cont = 0;
      unsigned short num = i;
      while(num)
        {
          num>>=1;
          cont++;
        }
      bits[i] = cont;
    }
}
char how_many_bits(unsigned short n)
{
  return bits[n];


 ha scritto nel messaggio
news:HhJN9.19069$Q%4.60...@news1.tin.it...

Questa non la sapevo!!! Grazie!!!
Dario