Get Integer From Bits Inside `std :: vector <char>`

Question

Ho un vector<char> e voglio essere in grado di ottenere un numero intero senza segno da un intervallo di bit all'interno del vettore. Per esempio.

E io non riesco a essere in grado di scrivere le operazioni giuste per ottenere il risultato desiderato. Mio algoritmo inteso così:

• & il primo byte con (0xff >> unused bits in byte on the left)
• << il risultato ha lasciato il numero di byte di uscita * numero di bit in un byte
• | questo con l'output finale
• Per ogni byte successivo:
  • << lasciato dalla (larghezza byte - indice) * bit per byte
  • | questo byte con l'output finale
• | il byte finale (non spostato) con l'uscita finale
• >> l'output finale per il numero di bit non utilizzati nel byte a destra

E qui è il mio tentativo di codifica di esso, che non dà il risultato corretto:

#include <vector> 
#include <iostream> 
#include <cstdint> 
#include <bitset> 

template<class byte_type = char> 
class BitValues { 
    private: 
    std::vector<byte_type> bytes; 
    public: 
     static const auto bits_per_byte = 8; 
     BitValues(std::vector<byte_type> bytes) : bytes(bytes) { 
     } 
     template<class return_type> 
     return_type get_bits(int start, int end) { 
      auto byte_start = (start - (start % bits_per_byte))/bits_per_byte; 
      auto byte_end = (end - (end % bits_per_byte))/bits_per_byte; 
      auto byte_width = byte_end - byte_start; 
      return_type value = 0; 

      unsigned char first = bytes[byte_start]; 
      first &= (0xff >> start % 8); 
      return_type first_wide = first; 
      first_wide <<= byte_width; 
      value |= first_wide; 

      for(auto byte_i = byte_start + 1; byte_i <= byte_end; byte_i++) { 
       auto byte_offset = (byte_width - byte_i) * bits_per_byte; 
       unsigned char next_thin = bytes[byte_i]; 
       return_type next_byte = next_thin; 
       next_byte <<= byte_offset; 
       value |= next_byte; 
      } 
      value >>= (((byte_end + 1) * bits_per_byte) - end) % bits_per_byte; 

      return value; 
     } 
}; 

int main() { 
    BitValues<char> bits(std::vector<char>({'\x78', '\xDA', '\x05', '\x5F', '\x8A', '\xF1', '\x0F', '\xA0'})); 
    std::cout << bits.get_bits<unsigned>(15, 29) << "\n"; 
    return 0; 
} 

(in azione: http://coliru.stacked-crooked.com/a/261d32875fcf2dc0)

Non riesco proprio a comprendere le piccole manipolazioni e trovo il debug molto difficile! Se qualcuno può correggere il codice sopra, o aiutarmi in qualsiasi modo, sarebbe molto apprezzato!

Edit:

• mie byte sono 8 bit lunghe
• Il numero intero di ritorno potrebbe essere 8,16,32 o 64 bit wside
• Il numero intero è memorizzato in big endian

Answer 1

Hai fatto due errori primari. Il primo è qui:

first_wide <<= byte_width; 

Si dovrebbe passare a un conteggio di bit, non a un conteggio di byte. codice corretto è:

first_wide <<= byte_width * bits_per_byte; 

Il secondo errore è qui:

auto byte_offset = (byte_width - byte_i) * bits_per_byte; 

Dovrebbe essere

auto byte_offset = (byte_end - byte_i) * bits_per_byte; 

Il valore in parentesi deve essere il numero di byte per spostare destra, che è anche il numero di byte byte_i è lontano dalla fine. Il valore byte_width - byte_i non ha significato semantico (uno è un delta, l'altro è un indice)

Il resto del codice va bene. Tuttavia, questo algoritmo ha due problemi con esso.

Per prima cosa, quando si utilizza il tipo di risultato per accumulare bit, si presuppone di avere spazio sulla sinistra da risparmiare. Questo non è il caso se ci sono dei bit impostati vicino alla bobina giusta e la scelta della gamma fa spostare i bit. Per esempio, provare a eseguire

bits.get_bits<uint16_t>(11, 27); 

Si otterrà il risultato 42, che corrisponde alla stringa di bit 00000000 00101010 Il risultato corretto è 53290 con la stringa di bit 11010000 00101010. Si noti come i 4 bit più a destra siano stati azzerati.Questo perché si inizia disattivando la variabile value, causando l'allontanamento di questi quattro bit dalla variabile. Quando si sposta indietro alla fine, ciò comporta il blocco dei bit.

Il secondo problema ha a che fare con lo spostamento a destra alla fine. Se il bit più a destra della variabile value è un 1 prima dello spostamento a destra alla fine e il parametro template è un tipo firmato, quindi lo spostamento a destra eseguito è uno spostamento a destra "aritmetico", che causa dei bit sul diritto di essere riempito a 1, lasciando un valore negativo errato.

esempio, provare a eseguire:

bits.get_bits<int16_t>(5, 21); 

Il risultato atteso dovrebbe essere 6976 con la stringa di bit 00011011 01000000, ma l'implementazione corrente ritorna -1216 con la stringa di bit 11111011 01000000.

ho messo la mia esecuzione del presente di sotto del quale costruisce la stringa di bit da destra a sinistra, ponendo i bit nelle loro posizioni corrette per cominciare in modo che questi due problemi sono evitati:

template<class ReturnType> 
ReturnType get_bits(int start, int end) { 
    int max_bits = kBitsPerByte * sizeof(ReturnType); 
    if (end - start > max_bits) { 
    start = end - max_bits; 
    } 

    int inclusive_end = end - 1; 
    int byte_start = start/kBitsPerByte; 
    int byte_end = inclusive_end/kBitsPerByte; 

    // Put in the partial-byte on the right 
    uint8_t first = bytes_[byte_end]; 
    int bit_offset = (inclusive_end % kBitsPerByte); 
    first >>= 7 - bit_offset; 
    bit_offset += 1; 
    ReturnType ret = 0 | first; 

    // Add the rest of the bytes 
    for (int i = byte_end - 1; i >= byte_start; i--) { 
    ReturnType tmp = (uint8_t) bytes_[i]; 
    tmp <<= bit_offset; 
    ret |= tmp; 
    bit_offset += kBitsPerByte; 
    } 

    // Mask out the partial byte on the left 
    int shift_amt = (end - start); 
    if (shift_amt < max_bits) { 
    ReturnType mask = (1 << shift_amt) - 1; 
    ret &= mask; 
    } 
} 

Answer 2

Interessante problema. Ho fatto simili, per alcuni sistemi funzionano.

• Il tuo carattere è largo 8 bit? O 16? Quanto è grande il tuo intero? 32 o 64?
• Ignora la complessità del vettore per un minuto.
• Pensateci solo come una serie di bit.
• Quanti bit hai? Hai 8 * numero di caratteri
• È necessario calcolare un carattere iniziale, numero di bit da estrarre, fine carattere, numero di bit e numero di caratteri nel mezzo.
• Avrete bisogno di bit a bit-e & per il primo carattere parziale
• dovrai bit a bit-e & per l'ultimo carattere parziale
• avrete bisogno di sinistra-shift < < (o destra-shift >>), a seconda di quale ordine si inizia da
• qual è l'endianità del proprio numero intero?

Ad un certo punto si calcola un indice in vostro array che è BitIndex/char_bit_width, ti ha dato il valore 171 come BitIndex e 8 come char_bit_width, così si finirà con questi valori utili calcolati:

• 171/8 = 23 // posizione del primo byte
• 171% 8 = 3 // bit in primo carattere/byte
• 8 - 171% 8 = 5 // bit in ultimo carattere/byte
• sizeof (numero intero) = 4
• sizeof (interi) + ((171% 8)> 0 1: 0) // quante posizioni serie di esaminare

Some Assembly Required ...

Answer 3

C'è una cosa che certamente ho sbagliato: il modo in cui indicizzate i bit nel vettore è diverso da quello che vi è stato dato nel problema. Cioè con l'algoritmo che hai delineato, l'ordine dei bit sarà come 7 6 5 4 3 2 1 0 | 15 14 13 12 11 10 9 8 | 23 22 21 .... Francamente, non ho letto tutto il tuo algoritmo, ma questo è mancato nel primo passo.