Esiste un modo di livello basso per ottenere i bit spostati o non spostati risultanti da operazioni bit a bit?

2

Stavo giocando con operazioni bit a bit e una domanda sul conteggio dei bit veri di qualsiasi valore intero positivo, quindi ho risolto il problema con lo spostamento dei bit, quindi ho pensato solo se ci sarebbe stato un modo per ottenere i bit spostati o non spostati dal bit a bit operazione, il codice sarebbe più ottimizzato. Così ho controllato la documentazione di PHP e ho imparato le operazioni bit a bit direttamente tradotte nel codice C. Ho controllato C e non ho visto nessuna sezione correlata. Quindi hai qualche idea al riguardo? È possibile ottenere questi bit? O semplicemente buttato via?

Il codice che sto cercando di ottimizzare:

function num1Bits($number)
{
    if ($number <= 0) {
        return 0;
    }

    $countOf1 = 0;

    do {

        if ($number & 1) {
            ++$countOf1;
        }

    } while ($number = $number >> 1);

    return $countOf1;
}


echo num1Bits(11);

Qualsiasi informazione sarebbe apprezzata.

    
posta FZE 08.04.2016 - 22:23
fonte

3 risposte

3

Se stai spostando x a destra di bit b (x > > b), allora i bit meno significativi andranno persi. Per catturarli prima che si perdano, puoi usare l'operazione bit a bit e l'operazione con una maschera che contiene lo stesso numero di 1 bit mentre stai spostando (cioè 1 per 1 bit, 3 per 2 bit, 7 per 3 bit, 0xF per 4 bit, ... ((1 < < b) - 1) per b bit). Per esempio

lost = num & ((1 << b) - 1);
rest = num >> b;

Ovviamente se stai usando una costante b, puoi precalcolare il valore della maschera.

Hai taggato la domanda con assembly, php e c. In linguaggio assembly (almeno su alcune architetture), se si sposta un valore a destra di un singolo bit, quel bit finisce memorizzato in un flag che può quindi essere utilizzato per vari altri scopi, inclusa l'aggiunta a un numero. Ciò offre un approccio interessante al tuo problema:

mov eax, 0
mov ebx, [number to count bits in]
shr ebx, 1     ; shift right moves lsb into carry flag
adc al, 0        ; add with carry adds 0 + carry flag
shr ebx, 1
adc al, 0
; repeat another 30 times
ret    ; result is in eax.

Si noti che non ci sono istruzioni di ramificazione. Ciò rende molto più veloce il dover ramificarsi in base al fatto che un 1 sia stato spostato o meno, perché ciò significherebbe davvero un errore con la logica di previsione delle branch della cpu. Un'implementazione semplice, pulita e lineare è molto più efficiente.

    
risposta data 08.04.2016 - 23:42
fonte
3

Lo spostamento bit a sinistra ( << ) e lo spostamento a destra ( >> ) nei linguaggi di livello superiore come PHP, C o C ++ perde il più o meno significativo.

Tuttavia, con molte CPU, le istruzioni di assemblaggio per lo spostamento non perdono veramente questo bit ma spostalo nella bandiera di riporto . Potresti quindi reagire su questo carry flag , come spiegato in questa domanda SO .

Tra l'altro, in assembly, a seconda della CPU, spesso non hai solo operazioni di spostamento, ma anche istruzioni di rotazione con o senza prendere in considerazione la bandiera di riporto.

    
risposta data 08.04.2016 - 23:26
fonte
0

beh, certo, ti basta mascherarli prima del turno se non vuoi perderli.

Alcuni set di istruzioni hanno una rotazione che li sposta verso l'alto, questo non si riflette nei linguaggi di alto livello (PHP, C, ecc.). A volte ruotano attraverso il carry. Allo stesso modo, come già detto a volte, si spostano attraverso il carry prima di essere scartati.

Se il tuo obiettivo è di spostare e salvare ciò che viene spostato, semplicemente maschera i bit prima di spostarli e salvarli in quel modo, praticamente qualsiasi linguaggio di programmazione utile (ha alcune operazioni minime bit a bit e, o, no, ecc) supporterà questo.

    
risposta data 10.04.2016 - 15:23
fonte

Leggi altre domande sui tag