Kirjoittaja: Antti Laaksonen
Kirjoitettu: 30.12.2006 – 30.12.2006
Tagit: koodi näytille, vinkki
Bitti voi tuntua aluksi aika tylsältä jutulta - sehän on pelkkä ykkönen tai nolla! Mutta todellisuudessa harva asia on yhtä kiinnostava. Tässä on kaksi esimerkkiä, jotka ovat pientä esimakua ensi keväänä ilmestyvästä "Ohjelmoijan matematiikka" -sarjan oppaasta.
* * *
Vanhassa taikatempussa avustaja valitsee ensin yhden luvun, jota hän ei kerro ääneen. Sitten taikuri esittää muutaman lukutaulukon ja avustaja ilmoittaa, missä taulukoissa tuo valittu luku esiintyy. Siinä samassa taikuri jo tietää, minkä luvun avustaja valitsi.
Taikurin näyttämät taulukot ovat tässä:
I: 1 3 5 7 9 11 13 15 17 19 21 23 25 27 29 31
II: 2 3 6 7 10 11 14 15 18 19 22 23 26 27 30 31
III: 4 5 6 7 12 13 14 15 20 21 22 23 28 29 30 31
IV: 8 9 10 11 12 13 14 15 24 25 26 27 28 29 30 31
V: 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31
Nyt avustaja valitsee esimerkiksi luvun 22 ja kertoo, että luku on taulukoissa II, III ja V. Taikuri saa luvun selville laskemalla yhteen näiden taulukoiden ensimmäiset luvut, siis 2 + 4 + 16 = 22. Samalla tavalla paljastuu mikä tahansa muukin luku välillä 0 - 31.
Tempun salaisuus on siinä, että taulukkoon I on koottu luvut, joiden viimeinen bitti on 1, taulukkoon II luvut, joiden toiseksi viimeinen bitti on 1, taulukkoon III luvut, joiden kolmanneksi viimeinen bitti on 1 jne. Esimerkiksi luku 22 on bittimuodossa 10110, niinpä tämä luku on taulukoissa II, III ja V.
Miksi lukuväli on juuri 0 - 31? Viidellä taulukolla eli viidellä bitillä voi esittää korkeintaan näin monta lukua. Jokaisen taulukon kohdalla avustaja sanoo, kuuluuko luku tähän taulukkoon vai ei. Siis erilaisten tilanteiden määrä on 25 = 32.
* * *
Nyt pitää tehdä ohjelma, jonka avulla voi varata huoneen tiettyyn aikaan päivästä. Varaus ilmoitetaan tunnin tarkkuudella, esim. joku voisi varata huoneen välillä 12 - 14 ja joku toinen välillä 16 - 19. Ohjelman pitää tietää, mitkä ajat on varattu.
Perinteinen ratkaisu olisi tehdä taulukko, jossa on 24 alkiota - yksi joka tunnille. Esimerkin tilanteessa taulukon alkioiden 12, 13, 16, 17 ja 18 arvo olisi 1 ja muiden 0. Tämä on kuitenkin hieman tuhlaavaista, koska sama tieto mahtuu yhteen tavalliseen kokonaislukumuuttujaan!
Jos luvun bitti on 0, huone on vapaana vastaavan tunnin. Jos taas bitti on 1, huone on varattu. Yhden huoneen tila vie siis tilaa vain yhden bitin. Kun kokonaisluku on 32-bittinen, 24 tuntia mahtuu siihen hyvin. Tässä on muutamia esimerkkejä, kuinka varaukset ilmoitetaan bitteinä:
1. Huone on koko päivän vapaa:
000000000000000000000000 = 0
2. Varaus klo 12 - 14:
000000000001100000000000 = 6144
3. Varaus klo 12 - 14 ja 16 - 19:
000000111001100000000000 = 235520
4. Varaus klo 8 - 12 ja 15 - 16:
000000000100011110000000 = 18304
5. Varaus klo 6 - 8, 10 - 14 ja 17 - 18:
000000010001111001100000 = 73312
Nyt koko päivän varauksia voi käsitellä bittien välisillä laskuilla. Kahden varauksen yhdistäminen vastaa laskua OR - siis tunnin pitää olla varattu jommassakummassa. Sitä ennen kannattaa tarkastaa, että varaukset eivät mene päällekkäin. Tämä tapahtuu laskulla AND - jos varauksissa ei ole yhtään samaa tuntia, tuloksen pitäisi olla nolla.
Tässä tapauksessa varausten käsittely bitteinä on lähinnä ohjelmoijan taitojen esittelyä - muistia tosin säästyy ja varausten vertailu on kymmeniä kertoja nopeampaa, mutta tuskinpa ohjelma olisi tavalliseen tapaan tehtynäkään hidas. On kuitenkin tilanteita, joissa taulukon muutto luvuksi kannattaa. Tällaisen luvun nimi on bittivektori.
* * *
Ohjelmat:
1. Luvun arvaus taulukoista
2. Huoneiden varaukset
Jos luvun bitti n oikealta katsoen on 1, luvun osa voidaan ilmoittaa 2n - 1.
ARVAUS.BAS
CLS
PRINT "Valitse luku väliltä 0 - 31."
SLEEP
luku% = 0
FOR i% = 0 TO 4
PRINT "Onko luku tässä? (K/E)"
FOR j% = 0 TO 31
IF (2 ^ i% AND j%) <> 0 THEN
PRINT j%;
END IF
NEXT
DO
v$ = INKEY$
SELECT CASE v$
CASE "k", "K"
luku% = luku% + 2 ^ i%
EXIT DO
CASE "e", "E"
EXIT DO
END SELECT
LOOP
NEXT
PRINT
PRINT "Valitsit luvun"; luku%HUONEET.BAS
' koko päivän vapaa
v&(1) = 0
' varaus klo 12 - 14
v&(2) = 2 ^ 11 + 2 ^ 12
' varaus klo 12 - 14 ja 16 - 19
v&(3) = 2 ^ 11 + 2 ^ 12 + 2 ^ 15 + 2 ^ 16 + 2 ^ 17
' varaus klo 8 - 12 ja 15 - 16
v&(4) = 2 ^ 7 + 2 ^ 8 + 2 ^ 9 + 2 ^ 10 + 2 ^ 14
' varaus klo 6 - 8, 10 - 14 ja 17 - 18
v&(5) = 2 ^ 5 + 2 ^ 6 + 2 ^ 9 + 2 ^ 10 + 2 ^ 11 + 2 ^ 12 + 2 ^ 16
CLS
FOR i% = 1 TO 5
PRINT "Varaus"; i%; ": ";
kuva v&(i%)
NEXT
PRINT
PRINT "Mahdolliset kahden varauksen yhdistykset:"
FOR i% = 1 TO 5
FOR j% = i% + 1 TO 5
IF (v&(i%) AND v&(j%)) = 0 THEN
PRINT i%; "ja"; j%; " : ";
kuva (v&(i%) OR v&(j%))
END IF
NEXT
NEXT
' näyttää huoneen varaustilanteen merkkeinä
SUB kuva (v&)
FOR i% = 23 TO 0 STEP -1
IF (v& AND 2 ^ i%) = 0 THEN
PRINT "_";
ELSE
PRINT "#";
END IF
NEXT
PRINT
END SUBBitti on kyl jännä. :P
en olisi uskonut että bitestä sa irti noin paljon :)
jos alkaisi itsekin etsiä sovellutuksia bitin käyttöön; noisi olla hyötyä ohjelmoinnissakin ;) kiitos antti
EDIT: toivottavasti se opas tulee pian
:P
EDIT: Hyvä on, :)
KoTW > Ei :P vaan :)
Private Function TarkistaJokuBitti(luku As Long, moneskoOikealta As Long) As Boolean Dim x As Long, y As Long y = 2 ^ (moneskoOikealta - 1) x = luku And y If x Then TarkistaJokuBitti = True: Exit Function TarkistaJokuBitti = False: Exit Function End Function Private Sub Form_Load() Dim i As Long Dim luq As Long Text1 = "" For i = 1 To 10 For luq = 1 To 127 ' ja jos haluat kasibittisen, 255 ja blablabla, ysibittinen on 511 If TarkistaJokuBitti(luq, i) Then Text1 = Text1 & luq & " " End If Next luq Text1 = Text1 & VbCrLf & VbCrLf Next i End Sub
Tämä luo tuon ensimmäisen taian taulukoita.
Voisko joku tehdä VB:llä ton Arvaus-ohjelman? (En oo mikään hyvä koodari)
Dim KeyAski As Long
Private Sub Form_KeyDown(KeyCode As Integer, Shift As Integer)
KeyAski = KeyCode
End Sub
Private Sub Form_KeyUp(KeyCode As Integer, Shift As Integer)
KeyAski = -1
End Sub
Private Sub Form_Load()
Me.Show
Cls
Print "Valitse luku väliltä 0 - 31."
Sleep
luku% = 0
For i% = 0 To 4
Print "Onko luku tässä? (K/E)"
For j% = 0 To 31
If (2 ^ i% And j%) <> 0 Then
Print j%;
End If
Next
Do
v = Inkey
Select Case v
Case vbKeyK
luku% = luku% + 2 ^ i%
Exit Do
Case vbKeyE
Exit Do
End Select
DoEvents
Loop
Cls
Next
Print
Print "Valitsit luvun"; luku%
End Sub
Private Sub Sleep()
Do Until Inkey <> 0
DoEvents
Loop
End Sub
Private Function Inkey()
If KeyAski <> -1 Then Inkey = KeyAski: KeyAski = -1
End FunctionKiitti, KoTW! :)
arvausohjelma toimisi myös näin:
INPUT "Valitse luku väliltä 0-31", a IF a => 0 AND a =< 31 THEN INPUT "Onko luku tässä?", a$ IF a$ = "kyllä" THEN PRINT "Valitsit luvun "; a ELSE PRINT "Luku ei ole väliltä 0-31!" SLEEP END END IF
Mutta yllä olevassa koodinpätkässä ei ole kylläkään mitään ihmeellistä.
Se huonejuttu oli loistava, arvaus hyvä. Bitistä alkoi tulla minullekkin paljon kiinnostavampi. Kiitos!