2013-10-03 11 views
5

Mam vector<char> i chcę móc uzyskać liczbę całkowitą bez znaku z zakresu bitów w obrębie wektora. Na przykład.Uzyskaj Integer From Bits Inside `std :: vector <char>`

visualisation of bitvalues

I nie wydaje się być w stanie napisać odpowiednie działania, aby uzyskać pożądany wynik. My przeznaczone algorytm idzie tak:

  • & pierwszy bajt z (0xff >> unused bits in byte on the left)
  • << wyniku lewo liczbę bajtów wyjściowych * liczba bitów w bajcie
  • | to z ostatecznym wyjściem
  • Dla każdego kolejnego bajtu:
    • << pozostawione przez (szerokość bajtu - indeks) * bity na bajt
    • | ten bajt z końcowym wyjściu
  • | ostatni bajt (nie przesunął) z końcowym wyjściu
  • >> końcowy wynik przez ilość zużytego bitów bajtu w prawo

I tu jest moja próba go kodowania, który nie daje poprawny wynik:

#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; 
} 

(w akcji: http://coliru.stacked-crooked.com/a/261d32875fcf2dc0)

Po prostu nie mogę objąć głowy tymi manipulacjami bitów i uważam, że debugowanie jest bardzo trudne! Jeśli ktokolwiek może poprawić powyższy kod lub pomóc mi w jakikolwiek sposób, byłoby to bardzo cenne!

Edycja:

  • Kim bajtów 8 bitów
  • Liczba całkowita powrotu może być 8,16,32 lub 64 bitów wside
  • Liczba całkowita jest przechowywany w konfiguracji Big Endian

Odpowiedz

1

Popełniłeś dwa podstawowe błędy. Pierwszy z nich to:

first_wide <<= byte_width; 

Powinieneś przesuwać się o liczbę bitów, a nie o liczbę bajtów. Kod korygowane jest:

first_wide <<= byte_width * bits_per_byte; 

Drugim błędem jest tutaj:

auto byte_offset = (byte_width - byte_i) * bits_per_byte; 

Powinno być

auto byte_offset = (byte_end - byte_i) * bits_per_byte; 

Wartość w nawiasie musi być liczbę bajtów, aby przesunąć w prawo przez, która jest również liczbą bajtów byte_i jest poza końcem. Wartość byte_width - byte_i nie ma znaczenia semantycznego (jeden to delta, a drugi to indeks)

Reszta kodu jest w porządku. Chociaż ten algorytm ma z tym dwie problemy.

Po pierwsze, podczas używania typu wyniku do kumulacji bitów, zakładasz, że masz wolne miejsce po lewej stronie. Nie jest tak w przypadku, gdy ustawione są bity w pobliżu właściwej granicy, a wybór zakresu powoduje przesunięcie bitów. Na przykład, spróbuj uruchomić

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

Dostaniesz wynik 42, która odpowiada ciągu bitów 00000000 00101010 Prawidłowy wynik wynosi 53290 z ciągu bitów 11010000 00101010. Zauważ, jak wyrównywane są 4-bitowe prawe.Dzieje się tak dlatego, że zaczynasz od nadpisania zmiennej value, powodując przesunięcie tych czterech bitów ze zmiennej. Podczas cofania na końcu powoduje to wyzerowanie bitów.

Drugi problem dotyczy prawej zmiany na końcu. Jeśli najbardziej prawy bit zmiennej value ma wartość 1 przed prawym przesunięciem na końcu, a parametr szablonu jest typem podpisanym, wówczas prawe przesunięcie, które jest wykonywane, jest "arytmetyczną" prawą zmianą, która powoduje bity na prawo do wypełnienia 1-go, pozostawiając użytkownikowi niepoprawną wartość ujemną.

Przykład, spróbuj uruchomić:

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

Oczekiwany wynik powinien być 6976 z ciągu bitów 00011011 01000000, ale obecna implementacja zwraca -1216 z ciągu bitów 11111011 01000000.

Włożyłam moją realizację tego poniżej której buduje ciąg bit od prawej do lewej strony, umieszczając bity we właściwych pozycjach zacząć tak, że powyższe dwa problemy są unikać:

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; 
    } 
} 
+0

ten działa doskonale dla liczb całkowitych bez znaku dziękuję! Jestem właśnie na chwilę badając podpisane liczby całkowite - nie jestem * całkowicie * pewny, jaki jest mój pożądany wynik dla 'get_bits (14, 22)' z minuty na minutę! Wrócę z nadzieją niedługo z aktualizacją, lub jeśli uzna to za pożądane zachowanie, oznaczenie za Ciebie :) – Ell

+0

Wygląda na to, że ten kod nie działa dla 'bits.get_bits (0, 32) ; '- zwraca zero zamiast oczekiwanego' 519053860746' – Ell

+0

Masz rację. Błąd wynika ze sposobu zamaskowania wyniku na końcu. Lewe przesunięcie przesuwa bit o istotność powodując maskę bitową równą 0. Dodałem poprawkę. – Cookyt

0

Interesujący problem. Zrobiłem podobnie, ponieważ niektóre systemy działają.

  • Twój znak ma szerokość 8 bitów? Lub 16? Jak duża jest twoja liczba całkowita? 32 lub 64?
  • Zignoruj ​​złożoność wektora przez minutę.
  • Pomyśl o tym, jako o tablicy bitów.
  • Ile masz bitów? Masz 8 * liczby znaków
  • Musisz obliczyć początkowy znak, liczbę bitów do wyodrębnienia, zakończenie znaku, liczbę bitów tam i liczbę znaków w środku.
  • Musisz bitowym i & dla pierwszego częściowego char
  • trzeba będzie iloczynem bitowym i & do ostatniej częściowej char
  • trzeba będzie lewy-shift < < (lub prawy shift >>) w zależności od tego, której kolejności zaczynasz od
  • jaka jest końcówka twojej liczby całkowitej?

W pewnym momencie będzie można obliczyć wskaźnik do macierzy, która jest bitindex/char_bit_width, dałeś wartość 171 jako swojej bitindex i 8 jako swojej char_bit_width, tak będzie w końcu z tych przydatnych wartościami obliczonymi:

  • 171/8 = 23 // położenie pierwszego bajtu
  • 171% 8 = 3 // bity pierwszego znaku/bajt
  • 8 - 171% 8 = 5 // bitów ostatni znak/bajt
  • sizeof (integer) = 4
  • sizeof (Integer) + ((171% 8)> 0 1: 0) // ile pozycji array zbadać

Niektóre zgromadzenia wymaganej ...

0

Jest jedna rzecz na pewno brakowało Myślę, że sposób indeksowania bitów w wektorze różni się od tego, co dostałeś w danym problemie. To znaczy. z opisanym algorytmem kolejność bitów będzie taka jak 7 6 5 4 3 2 1 0 | 15 14 13 12 11 10 9 8 | 23 22 21 .... Szczerze mówiąc, nie przeczytałem całego twojego algorytmu, ale ten został pominięty w pierwszym kroku.