[Alg] boolean algoritme

[TukkerTweaker]

Ik heb een bepaald aantal boolean velden, laten we zeggen 22, waarvan de waardes in 1 nummeriek veld in een database moeten worden opgeslagen.
De volgorde van de boolean velden ligt vast. Op welke manier kan ik het beste de waardes vertalen naar een nummer.

voorbeeld:
'n' false = 0
1 true, 'n' false = 1
1 true, 2 true, 'n' false = 2
1 false, 2 true, 'n' fasle = 3
etc.

wie weet hier een efficiete methode voor?

[Janoz]

Je kunt toch gewoon binair tellen?

[Lustucru]

Bitsgewijs, dus in machten van twee, lijkt me. De uiteindelijke implementatie is taalafhankelijk.

[Macros]

Ik zou clusters van 8 booleans bijelkaar zetten, daar ascii chars vanmaken. Die in een string zetten, en dan een huffman compressie overheen gooien.

[OZ-Gump]

Laat me voorop stellen dat het natuurlijk niet echt tof is om 22 waardes in één veld op te willen slaan. Alhoewel dat erg makkelijk kan werken als je inderdaad binair telt.

Voorbeeld met 5 waardes:
1 = true = 1
2 = true = 2
3 = true = 4
4 = true = 8
5 = true = 16

Uiteindelijke waarde: 31. Wanneer 3 false is, wordt de uiteindelijke waarde 27. Daar kun je altijd alles uithalen.

[André]

Ik snap je niet helemaal, als je booleans toch al vast staan kun je het toch zo opslaan:
1110101010101011100011

[TukkerTweaker]

OZ-Gump schreef op 08 juli 2004 @ 10:06:
Laat me voorop stellen dat het natuurlijk niet echt tof is om 22 waardes in één veld op te willen slaan. Alhoewel dat erg makkelijk kan werken als je inderdaad binair telt.

Voorbeeld met 5 waardes:
1 = true = 1
2 = true = 2
3 = true = 4
4 = true = 8
5 = true = 16

Uiteindelijke waarde: 31. Wanneer 3 false is, wordt de uiteindelijke waarde 27. Daar kun je altijd alles uithalen.

Dit is inderdaad een mooie oplossing, bedankt.

[TukkerTweaker]

André schreef op 08 juli 2004 @ 10:07:
Ik snap je niet helemaal, als je booleans toch al vast staan kun je het toch zo opslaan:
1110101010101011100011

Dit levert geen nummerieke waarde (denk aan voor/naloopnullen)

[Robtimus]

OZ-Gump schreef op 08 juli 2004 @ 10:06:
Laat me voorop stellen dat het natuurlijk niet echt tof is om 22 waardes in één veld op te willen slaan. Alhoewel dat erg makkelijk kan werken als je inderdaad binair telt.

Voorbeeld met 5 waardes:
1 = true = 1
2 = true = 2
3 = true = 4
4 = true = 8
5 = true = 16

Uiteindelijke waarde: 31. Wanneer 3 false is, wordt de uiteindelijke waarde 27. Daar kun je altijd alles uithalen.

Dit is de meest gebruikte manier ja. Kijk ook naar bitwise and en or om te kijken of een boolean is gezet of een boolean te zetten.

Bv: 27 & 4 = 0, 27 & 8 = 8 (dus '4' is false, '8' is true)
27 | 4 = 31 (zet '4' op true)
31 & 27 = 27 (zet '4' op false)

[Janoz]

TukkerTweaker schreef op 08 juli 2004 @ 10:18:
[...]


Dit levert geen nummerieke waarde (denk aan voor/naloopnullen)

Dat is wel degelijk een prachtig (binair) numeriek getal wat hetzelfde effect heeft als al die andere voorstellen .

[drm]

Allereerst is het handig om even de standaard bitwise operaties te snappen. Ik weet niet of je dat al kent, maar het is heel eenvoudig. Je hebt eigenlijk 4 elementaire operaties:
[list=1]• AND
Beide bits moeten op die plek geset zijn, dus:

code:

0010
0011   AND
-----
0010
  ^

alleen op die plek zijn beide bits geset

• OR
Eén van beide bits moet geset zijn, of beide bits. (inclusive OR):

code:

0010
0011   OR
----
  ^^

op die twee plekken is er sprake van inclusive or.

• XOR
Eén van beide bits moet geset zijn, maar niet beide. (exclusive OR):

code:

0010
0011   XOR
----
   ^

Enkel op die plek is 1 van beide bits geset.

• NOT
Draai alle bits om:

code:

0010   NOT
-----
1101

so far de basiskennis.

Het is het eenvoudigst om gewoon alle bits even in constanten te zetten of macros of iets van dien aard. Vervolgens om te checken of die bepaalde bit geset is doe je een AND operatie, om een bit uit te zetten doe je een AND NOT operatie en om een bit aan te zetten doe je een OR operatie. Even in pseudocode:

code:

define BIT_0    1
define BIT_1    1 << 1 // Left shift
define BIT_2    1 << 2
define BIT_3    1 << 3
...
define BIT_21   1 << 21

// checken of bit geset is:
if ( somevalue & BIT_3 ) {

}
// zet bit aan
somevalue = somevalue | BIT_9; // OR

// zet bit uit
somevalue = somevalue & ~BIT_1; // AND NOT

// flip bit (0 wordt 1, 1 wordt 0)
somevalue = somevalue ^ BIT_22; // XOR

// checken of meerdere bits geset zijn
if ( ( somevalue & (BIT_1 | BIT_3) ) == (BIT_1 | BIT3) ) {

}

Dan is het natuurlijk niet onverstandig om de constanten ook even duidelijke namen te geven. Let overigens ook op alignment van de variabelen. De constanten moeten zelf een even grote bitlength (of aantal bytes) hebben als waarmee je de constanten wilt gaan gebruiken (3 bytes in dit geval, wat waarschijnlijk uitdraait op een 4 byte waarde) die uiteraard gepad is met nullen.

offtopic:
Overigens: als je dit in een database wilt gaan zetten wil ik je aanraden van bitwise af te stappen en met n:m relaties te gaan werken. Da's namelijk een stuk beter onderhoud- en schaalbaar.