Ignoranza su operatori bit a bit?

[Giova411]

Ragazzi qualcuno mi spiega bene il perché utilizzare qualcosa del genere?

DV[j + abil[i]] = DV[j + abil[i]] | (DV[j] << 1);

oppure anche

if (((DV[i] >> s1) & 1) || ((DV[i] >> s2) & 1))

Ho un esempio di un programmino che utilizza questi operatori
Che fanno esattamente?
Cercando ho trovato che, nel primo codice, si fa uno spostamento dei bit (shift) a sinistra e poi un | OR bit a bit
Secondo codice, invece, abbiamo uno spostamento dei bit (shift) a destra, seguito da un & AND bit a bit
Ignorante sono!

[vict85]

Sul primo capisco le operazioni ma mi sfugge lo scopo. Dovrei vedere più codice.

Il secondo controlla se almeno uno dei bit in posizione s1 e s2 è uguale a 1.

[apatriarca]

La prima riga imposta ad uno i bit di DV[ j + abil[ i ] ] che sono uguali ad uno in (DV[ j ] << 1). Il secondo codice esegue le istruzioni all'interno dell'if se almeno uno tra i bit s1 e s2 di DV sono settati. Direi che chi ha scritto quel codice ha probabilmente cercato di ottimizzarlo usando operazioni sui bit invece di usare variabili booleane.

Dai una occhiata ad esempio a questa pagina per vedere qualche trucco basato sugli operatori bit-wise.

[Giova411]

Un onore leggere le vostre risposte come sempre.
(Oltre al contenuto delle risposte dove, ormai, non serve dire altro visto che siete moderatori)
Grazie per l'aiuto!

Era un contest informatico "carino" che stavo guardando.
(Come sempre pensavo fosse semplice ed invece..... Per me no)
Eccolo qui:
http://www.codechef.com/problems/TEAMSEL
Mi sono "arreso" alla soluzione trovata fatta:
http://www.codechef.com/viewsolution/771694
Ora Vic, giustamente, noterà tutte le include messe a caso
Codesta soluzione mi pareva un po' una schifezza ed invece funziona alla grande

[apatriarca]

Le soluzioni più efficienti nei vari contest sono raramente eleganti o leggibili. Lo scopo è quello di ottenere la soluzione più efficiente e questo porta spesso a fare uso di ottimizzazioni che in altre situazioni non sarebbero utilizzate. Inoltre il codice non è mai scritto per essere riutilizzato e di certo la leggibilità da parte di altri programmatori non è certamente una priorità. In questo caso però non sembra che queste ottimizzazioni siano state utili (è infatti lentissimo se confrontato alla soluzione più veloce - che sembra anche essere molto più leggibile). Direi che la ragione di questa differenza sarà quindi dovuta ad una differenza nell'algoritmo usato..

[Giova411]

Apa ma soluzioni più veloci hai notato che usano una ricorsione interna in un for? Come fanno ad esser più veloce.. boh..
Sto sito di contest non mi pare il massimo comunque...

[apatriarca]

La ricorsione non è necessariamente più lenta di altre soluzioni. Ha i suoi problemi e i suoi limiti, soprattutto in linguaggi come il C++, ma a volte è il modo più semplice per descrivere il problema.Considera per esempio il selection sort e il quick sort. Il primo è composto semplicemente da cicli mentre il secondo usa la ricorsione, ma è il secondo che si usa più comunemente ed è più veloce. Non ho guardato con attenzione il codice delle due soluzioni e quindi non ti saprei dire perché una delle due soluzioni sia più veloce ed efficiente dell'altra. Ma posso dirti che il codice prodotto dal primo è in pratica meglio sotto ogni punto di vista: è sia più veloce che più leggibile. Se devi quindi studiare un codice e cercare di capire perché funziona, guarda quello del primo..

[vict85]

"Giova411":Ora Vic, giustamente, noterà tutte le include messe a caso

In questi contest non devi solo rispondere, ma lo devi fare in fretta: immagino abbia un templare.

L'unico vero problema di inserire tante librerie è che rallenti la compilazione e aumenti la dimensione del file. Per le librerie standard il problema di inserire una libreria in più è minimo (sono già state compilate), il problema è quando hai progetti grandi e tanti file .h scritti da te.

[Giova411]

Non andava il Forum!!! Ho detto: mi hanno bannato Apa eVic!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!
[size=50]...ban meritato per quanto rompo!!!![/size]

Migliore soluzione (che devo vedere meglio) secondo voi è questa quindi:
http://www.codechef.com/viewsolution/3807785
Non si può migliorare?
Dico solo a parole non pretendo codice
Un caso, come dice Apa, dove la ricorsione è conveniente.
Vic le tue osservazioni mi hanno insegnato sempre molto, #incluse le include!!! Ultimamente le stavo mettendo a caso effettivamente!!!! Invece non aveva senso... E' come "avvisare i vigili del fuoco" che forse verranno chiamati, per poi chiamare solo i "caramba"

[Giova411]

Volevo chiuedere il topic scrivendo che la soluzione che confronta i bit (ossia la prima soluzione) è errata.
Così come diceva Apatriarca, la versione ricorsiva, non solo è corretta, ma molto efficente.

Vediamo un input che "manda a ceci" la soluzione che shifta i bit: abbiamo 140 abilità e vogliamo ottenere due team che siano più vicini possibili a livello di "bravura".

51 105 124 1191 52 95 68 102 35 82 138 26 45 34 13 117 124 107 110 87 139 94 53 36 17 125 105 36 105 79 86 14 43 80 116 105 33 42 65 78 122 73 103 37 118 114 12 100 79 121 45 88 73 109 122 100 92 97 135 67 35 79 80 88 29 66 51 73 106 126 9 87 69 110 134 45 94 5 3 44 136 59 130 67 26 123 26 128 90 31 53 123 120 3 81 7 67 2 78 32 138 98 129 66 66 121 109 31 136 123 73 130 52 73 68 88 66 104 74 15 133 125 8 111 139 88 128 64 100 77 106 97 33 93 21 109 85 140 138 91 

Il codice che fa gli shift forma questi due team:
1885 team 1
10440 team 2

Quando, invece, l'equilibrio corretto dovrebbe essere tra 6162 e 6163
GRAZIE APA, GRAZIE VIC