Bittien murskaamis ongelma.

Voit pyytää apua ohjelmointiongelmiin täältä.
Post Reply
User avatar
JATothrim
Tech Developer
Tech Developer
Posts: 606
Joined: Tue Aug 28, 2007 6:46 pm
Location: Kuopio

Bittien murskaamis ongelma.

Post by JATothrim » Thu Nov 12, 2009 11:39 pm

Koodatessani kuvan pakkaus algoritmiäni törmäsin ylitse pääsemättömään brobleemaan:
Ohjelma työntää jonoon (First In, First Out. tietorakenne) n-kappaletta yksittäisiä tavuja (eli 8 bittiä per luku).
Nyt jonosta pitäisi voida ottaa n-Bittiä kerralla, ikäänkuin koko jono olisi yksi pötköbittejä, jono lyhenee tällöin n-Bittin verran. Otettu n-bittin pötkö palautetaan 32-bittisessä muuttujassa. Tästä seuraa, että yli 32 bittiä ei voida ottaa kerralla jonosta (32-bit integer). Miten tämä toteutetaan? Apuja?

Esim:
Jono enen kuin siitä otetaan bittejä pois:
tavu 1: tavu 2: tavu 3:
10110100 10101011 00100110 10010101 01111010

Otetaan 6 bittiä: "101101" ja jono lyhenee muotoon:
00 10101011 00100110 10010101 01111010

Otetaan nyt 3 bittiä: "001" ja jono lyhenee muotoon:
0101011 00100110 10010101 01111010

Otetaan jälleen 16 bittiä: "0101011 00100110 1" ja jono lyhenee muotoon:
0010101 01111010

(PS: Jostain syystä osasin tehdä bittijonooni lisäys operaation, mutta otto operaation takkuaa pahasti.)
-On selkeästi impulsiivinen koodaaja joka...
ohjelmoi C++:lla rekursiivisesti instantioidun templaten, jonka jokainen instantiaatio instantioi sekundäärisen singleton-template-luokan, jonka jokainen instanssi käynistää säikeen tulostakseen 'jea'.

User avatar
KilledWhale
Tech Developer
Tech Developer
Posts: 543
Joined: Sun Aug 26, 2007 2:43 pm
Location: Liminka

Re: Bittien murskaamis ongelma.

Post by KilledWhale » Fri Nov 13, 2009 12:29 am

JATothrim wrote:(hyminää... (olen jo lähes 100% C++/IDE konkari) :P :lol: tirsk. ketjun "pro-maisuus" on alle nollan..)
skorpioni-cb: Käännät ne käyttäen jotain vapaasti saatavilla olevaa kääntäjää. Esim MinGW (joka on siis GCC wintoosalle) paketilla onnistuu. Hyvä IDE auttaa asiassa paljon. Esim. itse käytän Code:Blocks:ia.
Kylläkait 100% C++/IDE konkari tuollaiseen pystyy? Jos suuria lukuja haluat niin c++ löytyy ainakin GMP, joka on suhteellisen helppokäyttöinen.
CoolBasic henkilökuntaa
Kehittäjä

cbFUN Kello
cbSDL
Whale.dy.fi

<@cce> miltäs tuntuu olla suomen paras

User avatar
Dibalo
Advanced Member
Posts: 298
Joined: Mon Aug 27, 2007 8:12 pm
Location: Espoo, Finland
Contact:

Re: Bittien murskaamis ongelma.

Post by Dibalo » Fri Nov 13, 2009 12:45 am

Koska olet 100% C++-konkari, annan vain vinkkejä:
  • Dynaaminen muistinvaraus (esim malloc).
  • Osoitinaritmetiikka.
  • Bittioperaatiot.
The darkest spells can be found from
http://tunkkaus.blogspot.fi

User avatar
JATothrim
Tech Developer
Tech Developer
Posts: 606
Joined: Tue Aug 28, 2007 6:46 pm
Location: Kuopio

Re: Bittien murskaamis ongelma.

Post by JATothrim » Fri Nov 13, 2009 12:51 am

KilledWhale wrote:
JATothrim wrote:(hyminää... (olen jo lähes 100% C++/IDE konkari) :P :lol: tirsk. ketjun "pro-maisuus" on alle nollan..)
...
Kylläkait 100% C++/IDE konkari tuollaiseen pystyy? Jos suuria lukuja haluat niin c++ löytyy ainakin GMP, joka on suhteellisen helppokäyttöinen.
:D _lähes_ 100% ja en puhunut ongelman ratkaisusta. Ei hauskaa.

GMP auttaa isojen lukujen laskemisessa, mutta ei pilkkomisessa osiin. Tuota bittijonoa käsittellään siis vähän kuin merkkijonoa.
-On selkeästi impulsiivinen koodaaja joka...
ohjelmoi C++:lla rekursiivisesti instantioidun templaten, jonka jokainen instantiaatio instantioi sekundäärisen singleton-template-luokan, jonka jokainen instanssi käynistää säikeen tulostakseen 'jea'.

User avatar
skorpioni-cb
Advanced Member
Posts: 364
Joined: Wed Dec 03, 2008 4:48 pm
Location: Turku

Re: Bittien murskaamis ongelma.

Post by skorpioni-cb » Fri Nov 13, 2009 4:22 pm

JATothrim wrote:
KilledWhale wrote:
JATothrim wrote:(hyminää... (olen jo lähes 100% C++/IDE konkari) :P :lol: tirsk. ketjun "pro-maisuus" on alle nollan..)
...
Kylläkait 100% C++/IDE konkari tuollaiseen pystyy? Jos suuria lukuja haluat niin c++ löytyy ainakin GMP, joka on suhteellisen helppokäyttöinen.
:D _lähes_ 100% ja en puhunut ongelman ratkaisusta. Ei hauskaa.

GMP auttaa isojen lukujen laskemisessa, mutta ei pilkkomisessa osiin. Tuota bittijonoa käsittellään siis vähän kuin merkkijonoa.

Lukekaa mitä nuo sanoo.
Minä en tiedä mitä tiedän, mutta sen tiedän ettei se ole mitään kaunista.

User avatar
Dibalo
Advanced Member
Posts: 298
Joined: Mon Aug 27, 2007 8:12 pm
Location: Espoo, Finland
Contact:

Re: Bittien murskaamis ongelma.

Post by Dibalo » Fri Nov 13, 2009 6:14 pm

Attention:

Noniin lapset (itseni mukaan lukien)! Tämä asiattomien kommenttien postaaminen loppuu tässä ketjussa tähän. Jos moista näkyy, niin varoituksia alkaa lennellä.

Mutta sitten itse ongelmaan. Itse suosittelisin sinua tekemään vaikka oman luokan noille "liukuville bittijonoille". Kuten aikaisemmin mainitsin, on malloc varsin sopiva tähän tilanteeseen. Konstruktori voisi vaikka ottaa vaikka halutun bittimäärän kokonaislukuina. Huomioi, että malloc voi varata minimissään täysiä tavuja, joten bittisarjojen pituus on aina 8. kertoin.

En saa antamastasi esimerkistä oikein kunnon kuvaa alogritmisi toiminnasta, mutta malloc:n palauttamaa osoitinta voidaan käyttää esimerkiksi vaikka taulukkona bytejä (unsigned char). Näin ollen voit lukea jonostasi bittejä tähän taulukkoon. Byte-order:n (little-/big-endian) voit päättää vapaasti, kannattaa tosin valita sellainen, joka sopii itsellesi paremmin. Ja malloc:n varaama muistihan pitää luonnollisesti vapauttaa lopuksi free:llä. ;) Jos haluat homman kompaktiin pakettiin, niin tiettyjen operaattoreiden (=, ==, !=, <<, >>, jne.) ei ole pahitteeksi. :)

Ja ihan vinkkinä seuraavaan kertaan: ylimielisyys kannattaa unohtaa heti alkuunsa, varsinkin, kun omalla "paremmuudella" tarkoituksella halveerataan toista tai asetetaan tämä alenevaan asemaan. Silloin on todellakin hyvä pystyä seisomaan omien sanojen takana. Muuten seuraukset ovat hyvinkin tuhoisia itsensä kannalta.
The darkest spells can be found from
http://tunkkaus.blogspot.fi

Post Reply