Newsgroup: it.comp.lang.c++
Titolo: Invertire i bit di una variabile...

Ciao a tutti!
Qualcuno conosce un algoritmo per invertire i bit di una variabile
compresa tra 0 e una potenza di 2?!?!?
in pratica se ho un numero che in binario e` 11001 dovrei fare una
procedura che mi restituisca 10011 (nel caso in cui io lavori su 5
bit...)
Okok.. loso, e` una cavolata da fare... pero` io avrei bisogno di
qualcosa di velocissimo!!!
Ciao e grazie!
    Andrea
--
Posted from 
ph02xd.ph.unito.it
 [193.205.64.2]
via Mailgate.ORG Server - 
http://www.mailgate.org

qualcosa di velocissimo!!!
Puoi fare varie micro-ottimizzazioni, tipo "srotolare il loop" -- se
ad esempio non ti interessa il caso nBits=0, ma solo da 1 in su,
    for(;;) {
        result |= u&1;
        if(--nBits==0) break;
        result <<= 1;
        u >>= 1;
        result |= u&1;
        if(--nBits==0) break;
        result <<= 1;
        u >>= 1;
    }
(puoi anche srotolare di un fattore maggiore di 2).  Devi poi
vedere con lo specifico compilatore e CPU che usi che tipo
di beneficio puoi avere da questi approcci.  Puoi usare una
tabella di look-up in qualche forma, ad esempio quattro bit alla
volta: tratti prima gli eventuali 1, 2, o 3 bit "dispari", poi
procedi 4 bit alla volta (come shift e mascheramento)
usando una tabellina statica ausiliaria di 16 valori per avere
l'"inversa" dei "bocconcini" ("nibble") da 0 a 15 trattati.
Soprattutto se il numero di bit e` noto a compile-time, un
approccio con ottimo costo ammortizzato sara` certo quello
di caching.  Supponi, ad esempio, di sapere a priori che
il numero di bit e` 7; allora...:
unsigned inver7(unsigned u)
{
    static unsigned cache[128];
    unsigned result = cache[u];
    if(u && !result) {
        // calcola result con un algoritmo come sopra
        cache[u] = result;
    }
    return result;
}
Alla lunga, questo avra` un costo di un indiciamento,
due confronti con zero, e un and-logico, dopo aver
passato il "transitorio" in cui la cache si riempie.
Maggior velocita` si ottiene precalcolando del tutto
la cache, naturalmente (e` facile farsela scrivere a
tempo di compilazione da un programmino ad hoc
che usa il primo approccio); cosi` si ottiene un costo
di 1 lookup in un array e basta (naturalmente, quando
la funzione diventa abbastanza piccola e veloce e`
_sicuramente_ il caso di dichiararla anche inline!).
Il caching non funziona purtroppo altrettanto bene
se il numero di bit e` anch'esso una variabile, nota
solo a runtime e cangiante ogni volta, ma sono
ovviamente possibili i soliti trade-off spazio-tempo.
Come al solito, il C++ ti offre un'amplissima scelta
di strumenti di ottimizzazione.  Ad esempio, visto
che non ci sono poi molti possibili valori per il numero
di bit (da 1 a 31, immagino?), puoi avere un array
di puntatori a funzione, e definirti a priori le 31
funzioni in gioco, ciascuna ottimizzata al meglio;
o, se un costo transitorio (poi ammortizzato) e`
accettabile, un array di 31 oggetti ciascuno dei
quali calcola le inversioni per un particolare numero
di bit (puoi usare metodi virtuali, ma non e`
strettamente necessario) con relativa cache.
Bisogna definire i parametri dell'ottimizzazione (cosa
e` noto quando -- e` o meno accettabile di dover
preparare prima della compilazione le varie
strutture -- e` o meno accettabile un costo
transitorio di startup -- ecc) con molta piu` chiarezza
e precisione che non "qualcosa di velocissimo",
per potere scegliere in modo ottimale in questo
vero e proprio oceano di possibilita`.
Alex

--
Prova questo esempio.
Ciao
Nazzareno
// ----------------------------------------------
#include <iostream.h>
#include <stdlib.h>
// ----------------------------------------------
template <class T>
T reverse_bit(T t,int nbit)
{
  T ret = 0;
  while(1) {
    if(t & 1)
      ret |= 1;
    if(!--nbit)
      break;
    t >>= 1;
    ret <<= 1;
    }
  return ret;
}
// ----------------------------------------------
template <class T>
void bit2str(char *buff, T t, int nbit)
{
  buff[nbit]=0;
  for(int i = nbit - 1; i >= 0; --i, t >>= 1)
    buff[i] = '0' + (t & 1);
}
// ----------------------------------------------
typedef unsigned long t_test;
int main(int argc,char **argv)
{
  if(argc < 2)
    return 5;
  t_test t = atol(argv[1]);
  char buff[34];
  int nbit = 5;
//  int nbit = sizeof(t) * 8;
  bit2str(buff, t, nbit);
  cout << t << "(" << buff << ") -> ";
  t = reverse_bit(t, nbit);
  bit2str(buff, t, nbit);
  cout << t << "(" << buff << ")" << endl;
  return 0;
}
--
Posted from [195.223.93.3]


 via Mailgate.ORG Server - 
http://www.mailgate.org
Nel caso in cui il numero di bit da invertire e' fisso, se hai memoria a
sufficienza puoi precalcolarti con qualsiasi algoritmo tutti i 2^n
possibili output e memorizzarteli in un array, usando poi il valore da
convertire come indice nell'array.
francesco

      ret |= 1;
(dal mio messaggio precedente)
Mi devo essere mangiato il cervello (spero sia stato dovuto alla stanchezza)
:-)
Naturalmente doveva essere -> ret |= t & 1; (come si poteva dedurre anche
dalla bit2str())
Per rimediare, propongo un'altra soluzione che usa l'assembler inline. Forse
e' un po' OT, ma visto che si cercano le prestazioni ... :-)
Sfrutta il bit del carry negli shift. E' fatto per la 80x86 e successive e
l'ambiente e' quello della Borland.
Pero', dopo aver fatto alcuni test, ho visto che le prestazioni dipendono
molto dalla cpu utilizzata.
Su un vecchio (??) pentium a 133mhz si ha una performance di quasi il 50%.
Provato su un K6, risulta appena un po' piu' veloce (anche se le differenze
aumentano all'aumentare del numero di bit da invertire). Probabilmente il K6
predilige la prediction branch e lavorando in catena....
Volevo riportare solo la routine in asm inline, ma puo' essere interessante
vedere se ci sono differenze di prestazioni significative su altre macchine,
per cui riporto tutto il test :-)
Chiedo scusa ad Alex se ho riportato la sua routine nel test, ma era giusto
per avere un confronto in piu'.
P.S. il template non e' che c'entri poi molto, ma (mi ripeto, forse era la
stanchezza) non avevo notato subito che il reverse doveva avvenire su un
numero variabile di bit e non su tutti i bit (ma ormai l'avevo scritto).
P.P.S.S chiedo scusa se il post non si collega al thread. Da OE, da un po'
di tempo, non riesco a rispondere al NG e allora rispondo tramite mailgate.
A proposito, qualcuno sa erudirmi sul motivo?
// ----------------------------------------------
#include <iostream.h>
#include <stdio.h>
#include <stdlib.h>
typedef unsigned long t_count;
typedef unsigned t_test;
// ----------------------------------------------
#ifdef __WIN32__
  #include <windows.h>
  #define  RX(a)   e##a
  #define _RX(a)  _E##a
  #define GET_TIME GetSystemTime
  #define S_TIME  SYSTEMTIME
  #define HOUR   wHour
  #define MINUTE  wMinute
  #define SECOND wSecond
  #define MSEC  wMilliseconds
  #define DIM_MSEC  1000
#else
  #include <dos.h>
  #define  RX(a)   a
  #define _RX(a)  _##a
  #define GET_TIME _dos_gettime
  #define S_TIME  dostime_t
  #define HOUR   hour
  #define MINUTE  minute
  #define SECOND second
  #define MSEC  hsecond
  #define DIM_MSEC  100
#endif
// -----------------------------------------------
template <class T> T reverse_bit(T t,int nbit)
{
  T ret = 0;
  while(1) {
    ret |= t & 1;
    if(!--nbit)
      break;
    t >>= 1;
    ret <<= 1;
    }
  return ret;
}
// ----------------------------------------------
static unsigned reverse_bit_use_carry(unsigned t,int nbit)
{
asm {
   mov RX(dx), t
   xor RX(ax), RX(ax)
   mov RX(cx), nbit
   }
loop:
asm {
  shr RX(dx), 1 // shift a dx con il bit meno significativo nel carry
  rcl RX(ax), 1  // rol a sx caricando il carry nel lsb
  sub RX(cx), 1
  jne loop
  }
// come si dice "do compiler happy"
 return _RX(AX);
}
// ----------------------------------------------
static unsigned invertiBits(unsigned u, int nBits)
{
    unsigned result = 0;
    for(int i=0; i<nBits; ++i) {
       result |= u&1;
       result <<= 1;
       u >>= 1;
       }
    return result>>1;
}
// ----------------------------------------------
template <class T> void bit2str(char *buff, T t, int nbit)
{
  buff[nbit]=0;
  for(int i = nbit - 1; i >= 0; --i, t >>= 1)
    buff[i] = '0' + (t & 1);
}
// ----------------------------------------------
#define SUB_TIME(a)  res.a = t2.a - t1.a
#define CHECK_TIME(a,b,c)  if(res.a >= b) { res.a += b; --res.c; }
#define CHECK_TIME2(a,b)  if(res.a >= b) { res.a += b; }
static void subtime(S_TIME &t1,S_TIME &t2,S_TIME &res)
{
  SUB_TIME(HOUR);
  SUB_TIME(MINUTE);
  SUB_TIME(SECOND);
  SUB_TIME(MSEC);
  CHECK_TIME(MSEC,DIM_MSEC,SECOND)
  CHECK_TIME(SECOND,60,MINUTE)
  CHECK_TIME(MINUTE,60,HOUR)
  CHECK_TIME2(HOUR,24)
}
// ----------------------------------------------
static void out_res(int type, t_test org, t_test res, S_TIME&t_res, char
*bit)
{
  cout << "\nFunzione n. " << type << endl;
  cout << "Reverse bit di " << org << " = " <<res << " (" << bit << ")";
#define RES(a) int(t_res.a)
  char buff[100];
  sprintf(buff," time=%02d:%02d:%02d:%d\n",
        RES(HOUR),RES(MINUTE),RES(SECOND),RES(MSEC));
  cout << buff;
}
// ----------------------------------------------
static void test(t_test (*pf)(t_test, int), long v, int nbit, int nf)
{
  char buff[34];
  S_TIME t1, t2, t_res;
  const t_count rip = 10000000L;
  t_test tb;
  GET_TIME(&t1);
  for(t_count i = 0; i < rip; ++i)
    tb = pf(v, nbit);
  GET_TIME(&t2);
  subtime(t1, t2, t_res);
  bit2str(buff, tb, nbit);
  out_res(nf, v, tb, t_res, buff);
}
// ------------------------------------
int main(int argc,char **argv)
{
  if(argc < 2)
    return 5;
  t_test t = atol(argv[1]);
  int nbit = 15;
  if(argc > 2) {
    nbit = atoi(argv[2]);
    if(!nbit || unsigned(nbit) > sizeof(t) * 8 -1)
      nbit = sizeof(t) * 8 -1;
    }
  test(reverse_bit, t, nbit, 1);
  test(reverse_bit_use_carry, t, nbit, 2);
  test(invertiBits,  t, nbit, 3);
  return 0;
}
--
Posted from [195.223.93.3]


// come si dice "do compiler happy"
Veramente qui si dice "make", non "do":-).
Alex

Veramente qui si dice "make", non "do":-).
Hahem!! Hai ancora ragione, non ci sono proprio limiti all'ignoranza :-))))
Ne approfitto per postare un po' di risultati su quel test.
Ciao
Nazzareno
Pentium 133mhz - win32 - dato in input 1234
con 5 bit
Funzione n. 1 - time=00:00:04:610
Funzione n. 2 - time=00:00:02:700
Funzione n. 3 - time=00:00:04:170
con 15 bit
Funzione n. 1 - time=00:00:09:400
Funzione n. 2 - time=00:00:05:100
Funzione n. 3 - time=00:00:08:960
con 25 bit
Funzione n. 1 - time=00:00:14:170
Funzione n. 2 - time=00:00:07:470
Funzione n. 3 - time=00:00:13:670
con 31 bit
Funzione n. 1 - time=00:00:16:970
Funzione n. 2 - time=00:00:08:850
Funzione n. 3 - time=00:00:16:530
// ---------------------------------
K6 200mmx - win32 - dato in input 1234
con 5 bit
Funzione n. 1 - time=00:00:02:800
Funzione n. 2 - time=00:00:02:360
Funzione n. 3 - time=00:00:02:860
con 15 bit
Funzione n. 1 - time=00:00:05:610
Funzione n. 2 - time=00:00:04:720
Funzione n. 3 - time=00:00:06:100
con 25 bit
Funzione n. 1 - time=00:00:08:180
Funzione n. 2 - time=00:00:06:980
Funzione n. 3 - time=00:00:09:170
con 31 bit
Funzione n. 1 - time=00:00:09:670
Funzione n. 2 - time=00:00:08:400
Funzione n. 3 - time=00:00:10:990


Puoi usare un'alro metodo completamente diverso :
Inverti i bit byte per byte e poi li ricomponi al contrario :
Crea un array di 256 BYTE e assegni il valore dell'indice con i bit
rovesciati ...
BYTE RovesciaBitArray[256] = { 0, 128, 64, 192,.....255};
dopodiché per avere il vaore rovesciato in bit :
BYTE ArrayDaInvertire[SIZE] = {x,y,z......};
BYTE ArrayInvertito[SIZE];
for(int i = 0; i < SIZE; i++)
    ArrayInvertito[SIZE-i] = RovesciaBitArray[   ArrayDaInvertire[i]  ];
Non l'ho provato, ma dovrebbe funzionare correttamente.
Ingloba l'argoritmo in una funzione che riceve un puntatore all'array da
invertire e la sua dimensione,
e il gioco č fatto.
Saluti.

Ciao a tutti!
Ringrazio tutti coloro che hanno risposto al mio quesito sull'inversione
dei bit di una variabile!
Adesso vi svelo a cosa mi serviva tutto cio` e vi mostro una soluzione
che non ho del tutto capito, ma che funziona molto bene!! :))
Il problema e` quello di effettuare una FFT nel minor tempo possibile...
la prima cosa da fare per realizzare cio` e` scambiare ogni elemento
dell'array con quello la cui posizione e` il bit-inverso dell'elemento
in questione... da cui la mia domanda...
Ecco la soluzione proposta da quel notevole libro che e` il Numerical
Recipes in C...
Dati:
count = numero di elementi dell'array (deve essere una potenza di 2)
data = l'array.... 
Sorgentino...
    for (int i = 0, j = 0; i < count; i++)
    {
        if (j > i)  swap(data[i], data[j]);
 
        int m = count >> 1;
 
        while (m >= 2 && j >= m)
        {
            j -= m;
 
            m >>= 1;
        }
 
        j += m;
    }
ecco qua.... 
in pratica alla linea swap la la variabile j e` il bit-inverso della
i...
Ciao!
    Andrea
--
Posted from 
ph02xd.ph.unito.it
 [193.205.64.2]
