C++ Operacje Na Bitach,kopiowanie Bitów.

[Bartoleon]

Mam następujący problem. Ostatnio bawie się algorytmiką i postanowiłem w 3 różnych wersjach zaimplementowac algorytm szukania najdłuższego wspólnego podciągu 2 ciągów. Problem mam z tym najłatwiejszym i najgorszym tzn o największej złożoności obliczeniowej. Polega on na tym że poprostu generuje wszystkie możliwe podciągi krótszego z tych dwóch ciągów których jest n do potęgi 2 np dla ciągu o długoci 6 istnieje 2 do 6 jego podciągów i sprawdzam czy podciąg ten występuje w drugim ciągu przy czym wartośc jak dotąd najdłuszego wspólnego podciągu zapisuje w jakiejś zmiennej powiedzmy np int longest. Należałoby najpierw zapisać ilośc wszystkich możliwych podciągów tego krótszego ciągu i użyć tej wartości w petli tzn od 0 do tej wartości -1 tworzyć binarne reprezentacje wszytskich liczb z tego przedziału przechowywane w tablicy pomocniczej w postaci 0 i 1 jako jej elementów i chciałbym to zrobić w następujący sposób -

- niech unsigned long long int amount będzie zmienną przechowującą wartość ilości wszytskich podciągów krótszego ciągu

- załóżmy, że np długość krótszego ciągu n = 8 więc istnieje 256 podciągów

-w pętli dla każdej liczby 0-255 zapisuje jej bitową reprezentacje w tablicy o długości n i chciałbym to zrobić w taki sposób żę poprostu kopiuje do tej tablicy 8 ostatnich bitów zmiennej amount(po każdym na ostatni bit w odpowiednim elemencie tablicy n) po to aby w tej tablicy jedynki wyznaczały elementy danego podciagu

 

Czy są w C++ jakieś instrukcje do takiego kopiowania bitów. Jedyne operatory bitowe jakie znam realizują tylko operacje logiczne na bitach. Może jednak takie niskopoziomowe operacje są możliwe jedynie z poziomu asemblera.Jeśli tak to poradze sobie z tym w inny sposób - pisząc funkje zamieniająca liczbe dziesietną na jej binarną postać w postaci 0 i 1 pzrechowywanych jako elementy tablicy ale ciekawy jestem czy możliwe jest zrobienie tego poprzez takie operacje na samych bitach. Z góry wielkie dzięki za odpowiedzi

Edytowane 3 Listopada 2008 przez Bartoleon

[Bartoleon]

Właściwie to w przypadku tego algorytmu wystarczyłoby jakbym w każdej iteracji pętli mógł spawdzic stan odpowiednij ilości ostatnich bitów zmiennej amount bez konieczności tworzenia tablicy binarnej reprezentacji.Więc to wszystko co napisałem można ograniczyć do pytania - czy mozna sprawdzac stany poszczególnych bitów danej zmiennej np odczytywać kolejne stany 6-ściu ostatnich korzystając z jakiś instrukcji c++ ?

Edytowane 4 Listopada 2008 przez Bartoleon

[Gość <account_deleted>]

Hmm, a słyszłeś może o maskach bitowych, rotacjach?

 

Poza tym jakoś coś bardzo zamotany opis przedstawiłeś. Pierwsze zadanie to znalezienie zgodnych par bitów (ciągów 2-bitowych), póżniej 3, 4, itd - najmniej operacji wyjdzie ;)

 

Inne możliwe podejście: zamiana każdego bitu na bajt - marnotrawstwo pamięci, za to masz mnóstwo funkcji do operacji na ciągach np. ASCII ;)

[PelzaK]

co masz na myśli pisząc kopiowanie bitów... gdzie je chcesz kopiować?