Koodit: QB: Bittitaikoja

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 2⁵ = 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 2^{n - 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 SUB

Kommentit

Draiz [01.01.2007 01:26:52]

Lainaa #

Bitti on kyl jännä. :P

eraggo [01.01.2007 14:25:36]

Lainaa #

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

moptim [02.01.2007 12:09:16]

Lainaa #

:P
EDIT: Hyvä on, :)

Juhko [08.01.2007 14:51:26]

Lainaa #

KoTW > Ei :P vaan :)

moptim [08.01.2007 19:48:46]

Lainaa #

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.

Skullboy0 [08.01.2007 20:14:03]

Lainaa #

Voisko joku tehdä VB:llä ton Arvaus-ohjelman? (En oo mikään hyvä koodari)

moptim [08.01.2007 20:23:35]

Lainaa #

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 Function

Skullboy0 [08.01.2007 20:33:55]

Lainaa #

Kiitti, KoTW! :)

Chaosworm [02.03.2007 14:38:34]

Lainaa #

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!

Kirjoita kommentti

Tunnus
Salasana
Viesti: Muista lukea kirjoitusohjeet.

Kirjautuminen

Haku

Tehtävät

Kilpailu

Koodit: QB: Bittitaikoja

Kommentit

Draiz [01.01.2007 01:26:52]

eraggo [01.01.2007 14:25:36]

moptim [02.01.2007 12:09:16]

Juhko [08.01.2007 14:51:26]

moptim [08.01.2007 19:48:46]

Skullboy0 [08.01.2007 20:14:03]

moptim [08.01.2007 20:23:35]

Skullboy0 [08.01.2007 20:33:55]

Chaosworm [02.03.2007 14:38:34]

Kirjoita kommentti

Esikatselu