[ALG] toepassing bitwise operators,bitshifting en bitset?

[Laurens-R]

Wederom hallo allemaal,

Een n00b vraag:

Ik heb me gisteren eens verdiept in bitwise operators,bitshifting, std::bitset, etc en ik snap het ook nog eens (dat scheelt). Mijn vraag is: wat zijn nou eigenlijk de toepassings gebieden voor dit soort truukjes? Ik bedoel ik vond het helemaal te gek dat ik op bitniveau variabelen aan het bewerken was, maar wat zijn nou realworld scenario's waarbij dit enorm handig is? Ik zie het mezelf niet zo snel gebruiken.

Ik had al begrepen dat je er in sommige gevallen snel calculaties mee kan uitvoeren en dat het bij encryptie wordt gebruikt, maar niet iets in de zin van ... Nou dit is enorm handig bij dit <type applicatie> omdat je enorme voordelen mee behaald bij <een bepaald type algoritme>.

Dus wanneer is het handig om bitbewerkingen te gebruiken.

edit: typo

[RobIII]

Allereerst: Ik heb C++ uit je titel gehaald, voor deze discussie is namelijk niet relevant om welke taal het gaat. Bitwise operaties zijn in (zo goed als?) elke taal bruikbaar.

Bitwise operaties gebruik je waarschijnlijk meer dan je denkt; een simpele optelling bijvoorbeeld is namelijk ook een bitwise operatie. Wanneer je echt met bits en bytes gaat zitten AND-en/OR-en/XOR-en etc is nogal afhankelijk van waar je mee bezig bent. Soms ben je bepaalde bits uit een gegeven aan het masken, soms ben je idd bezig met encryptie. Echt specifieke taken kun je er niet aan toekennen; daar is de operatie te low-level voor: het zou onzin zijn om te beweren dat er in ´banking software meer ANDs worden gebruikt´ bijvoorbeeld.

Veel programmeurs grijpen naar bitewise operaties als iets ´snel´ gedaan moet worden maar vaak maakt het de code onnodig complex en is de winst (behalve in tight loops natuurlijk) vaak niet de moeite waard.

[ Voor 13% gewijzigd door RobIII op 24-03-2007 12:28 ]

[Laurens-R]

@ RobIII: Dus als ik je goed heb begrepen hangt het meer af van je persoonlijke inzicht icm het stuk algoritme/code waarmee je bezig bent?

edit: typo

[ Voor 6% gewijzigd door Laurens-R op 24-03-2007 12:37 ]

[RobIII]

EvilB2k schreef op zaterdag 24 maart 2007 @ 12:36:
@ RobIII: Dus als ik je goed heb begrepen hangt het meer af van je persoonlijke inzicht icm het stuk algoritme/code waarmee je bezig bent.

edit: typo

Uiteraard. Maar dat geldt voor het gebruik van elke instructie. Zo zie ik hier regelmatig posts voorbij komen van mensen die vragen "wat is de code voor..."? Er is daarop altijd maar 1 anwoord mogelijk: Er is geen dé code ergens voor. Programmeren is wat dat betreft net als timmeren; je hebt een gereedschapskist met daarin hamers, zagen, schroevendraaiers etc. (je instructies die je kunt gebruiken) en enkel door het juist gebruik en inzet ervan (right tool for the right job) krijg je uiteindelijk een werkend product. Je begrijpt ook dat iedere timmerman zijn (min of meer) eigen manier van werken heeft, maar dat doet er ook niet toe als het resultaat net zo goed is.

[Arjan]

bij beeldbewerking kan het enorm handig zijn. Neem nu 32bit kleurinformatie
die zit vaak als RGBA opgeslagen, hetgeen betekend dat een kleur er zo uit ziet:

C++:

uint32_t kleur = 0xAABBGGRR;

of

C++:

uint32_t kleur = 0xRRGGBBAA;

afhankelijk van je systeem.

om nu de rode pixel waarde te krijgen doe je dit:

C++:

uint32_t kleur = 0xAABBGGRR;
byte rood = kleur & 0x000000FF;

rood bevat nu alleen de waarden van de laatste byte, want

C++:

AAAAAAAA BBBBBBBB GGGGGGGG RRRRRRRR
bijvoorbeeld
11111111 00000000 00000000 00001010

11111111 00000000 00000000 00001010
00000000 00000000 00000000 11111111 (0x000000FF)
------------------------------------  &
00000000 00000000 00000000 00001010

voor bijvoorbeeld blauw moet je eerst bitshiften

C++:

AAAAAAAA BBBBBBBB GGGGGGGG RRRRRRRR
bijvoorbeeld
11111111 00001010 00000000 00000000

11111111 00001010 00000000 00000000 >> 16 = 00000000 00000000 11111111 00001010

00000000 00000000 11111111 00001010
00000000 00000000 00000000 11111111 (0x000000FF)
------------------------------------ &
00000000 00000000 00000000 00001010

[Laurens-R]

RobIII schreef op zaterdag 24 maart 2007 @ 12:40:
[...]

Uiteraard. Maar dat geldt voor het gebruik van elke instructie. Zo zie ik hier regelmatig posts voorbij komen van mensen die vragen "wat is de code voor..."? Er is daarop altijd maar 1 anwoord mogelijk: Er is geen dé code ergens voor. Programmeren is wat dat betreft net als timmeren; je hebt een gereedschapskist met daarin hamers, zagen, schroevendraaiers etc. (je instructies die je kunt gebruiken) en enkel door het juist gebruik en inzet ervan (right tool for the right job) krijg je uiteindelijk een werkend product. Je begrijpt ook dat iedere timmerman zijn (min of meer) eigen manier van werken heeft, maar dat doet er ook niet toe als het resultaat net zo goed is.

Eigenlijk had ik vanuit dat perspectief nooit bekeken en nu je het zo benaderd denk ik dat veel mensen die denkstap missen wat dat betreft.

Nu programmeer ik toch al een tijdje en zo zie je maar weer dat je soms toch nog op de meest fundamentele dingen nog 'verlicht' kan worden na een aantal jaren. En dan heb ik het puur over de gedachtegang, want je valt al snel in het patroon dat je gaat zoeken naar die ene manier waarop het moet gebeuren.

@ Atgast:

Cool! bedankt voor je voorbeeld


edit: reactie op atgast

[ Voor 9% gewijzigd door Laurens-R op 24-03-2007 12:55 ]

[RobIII]

Atgast geeft nu een mooi voorbeeld waarbij het waarschijnlijk makkelijk(er) voor je is om er een voorstelling bij te maken; maar dat neemt niet weg dat (ik roep maar wat) bijvoorbeeld bij het ontleden/interpreteren en opbouwen van een TCP/IP frame bitwise operaties net zo 'handig' zijn.

[Laurens-R]

@RobIII: kortom zodra ik een variabele tegenkom, waarvan de bitinformatie is opgedeeld in meerdere onderdelen voor meerdere types aan informatie (vb: rgb waarden), dan is het handig (zo niet enige manier) om bitshifting/bitoperators te gebruiken.

So geeky, yet so cool

Beide: bedankt voor jullie hulp

[ Voor 18% gewijzigd door Laurens-R op 24-03-2007 13:03 ]

[RobIII]

Atgast schreef op zaterdag 24 maart 2007 @ 12:41:
voor bijvoorbeeld blauw moet je eerst bitshiften

Of masken met een andere waarde

EvilB2k schreef op zaterdag 24 maart 2007 @ 12:59:
@RobIII: kortom zodra ik een variabele tegenkom, waarvan de bitinformatie is opgedeeld in meerdere onderdelen voor meerdere types aan informatie (vb: rgb waarden), dan is het handig (zo niet enige manier) om bitshifting/bitoperators te gebruiken.

Ja, hoewel je hiet niet zo zeer moet denken aan 'een variabele' maar 'een byte/word/dword etc'. Daarnaast wordt er (vaak in bijvoorbeeld binary files) gewoon optimaal gebruik gemaakt van ruimte (= minder opslagruimte) door (wederom: ik noem maar wat) 8 booleans in 1 byte te duwen. Nu is ruimte anno 2007 niet zo heel erg duur meer maar het hele Y2K probleem had er wel z'n oorzaak in

Bitwise operaties kun je werkelijk overal tegenkomen; compressie, beeldbewerking, encryptie; geluidsbewerking en ga zo maar door. Wer-ke-lijk overal.

[ Voor 72% gewijzigd door RobIII op 24-03-2007 13:07 ]

[Laurens-R]

Daarnaast wordt er (vaak in bijvoorbeeld binary files) gewoon optimaal gebruik gemaakt van ruimte (= minder opslagruimte) door (wederom: ik noem maar wat) 8 booleans in 1 byte te duwen. Nu is ruimte anno 2007 niet zo heel erg duur meer maar het hele Y2K probleem had er wel z'n oorzaak in

Maar je laat wel zien aan je baas/opdrachtgever dat je verstand van zaken hebt als je toch doet

[ Voor 31% gewijzigd door Laurens-R op 24-03-2007 13:13 ]

[RobIII]

EvilB2k schreef op zaterdag 24 maart 2007 @ 13:12:
[...]


Maar je laat wel zien aan je baas/opdrachtgever dat je verstand van zaken hebt als je toch doet

Dan heb je me toch nog niet begrepen; bitwise operaties zijn een concept; geen doel. Dat concept moet je begrijpen. Als je 2 varbelen optelt gebruik je net zo goed bitwise operaties.
Wanneer je ze inzet is afhankelijk van de klus die je wil klaren, als je dat doet om je baas te imponeren dan heb je kans dat a) je baas je vierkant uitlacht (als 'ie weet waar 'ie het over heeft) of b) het totaal geen indruk maakt want een bitwise operatie is niet meer/minder 'complex/stoer/whatever' dan welke andere instructie dan ook (behalve misschien NOP )

Tot slot: Ik denk (en vind) dat bitwise operaties (en dus booleanse logica) les 1 van het programmeren moet zijn / is. Als je dat al imponerend vindt

code:

If 8 = A then
...

Ook hier kun je bitwise gewoon alle bits van 'A' gaan vergelijken met de bits uit "8"; het effect is echter hetzelfde als je gewoon een compare doet (en een stuk leesbaarder). Daarnaast is een compare natuurlijk niets anders dan beide operands AND-en en kijken of het resultaat van de AND gelijk is aan 1 van de 2 operands

[ Voor 25% gewijzigd door RobIII op 24-03-2007 13:20 ]

[Henk007]

Eén belangrijke toepassing is nog niet genoemd hier. Namelijk de left arhytmische shift, dus het schuiven van de bitjes naar links. Effektief resulteert dat dus in een erg goedkope (in klokcycli) vermenigvuldiging met 2, of zelf met 2ⁿ als je n keer schuift. Een moderne compiler gebruikt dit natuurlijk automatisch als het nodig is.
Zie Bitwise operation

[ Voor 9% gewijzigd door Henk007 op 24-03-2007 13:19 ]

[Arjan]

RobIII schreef op zaterdag 24 maart 2007 @ 13:04:
[...]

Of masken met een andere waarde

[...]

dan moet je alsnog shiften om de juiste waarde te krijgen.

je zou het bitshiften overigens kunnen omzeilen als volgt:

C++:

uint32_t kleur = 0xAABBGGRR;

uint8_t *kleurArray = (uint8_t*)&kleur;

uint8_t rood = kleurArray[0];
uint8_t groen = kleurArray[1];
uint8_t blauw = kleurArray[2];
uint8_t alpha = kleurArray[3];

[ Voor 6% gewijzigd door Arjan op 24-03-2007 13:22 ]

[RobIII]

Atgast schreef op zaterdag 24 maart 2007 @ 13:19:
[...]

dan moet je alsnog shiften om de juiste waarde te krijgen.

Uiteraard; u heeft gelijk. Mijn nederige excuses

[Laurens-R]

Zelf doe ik een HBO informatica opleiding met een bedrijfskundige insteek... maar ik moet toegeven, het is dramatisch gesteld met de kwaliteit van het onderwijs. Merendeel van de opleidingen die ik heb onderzocht (in mijn omgeving) verschuiven van het technische vlak naar het business vlak (bedrijfskunde dus).

Nu is dat op zich niet erg, maar dat betekent dat je bij bepaalde onderwerpen niet lang genoeg stil staat. Nu hebben we wel zaken zoals OOP en datastructuren enzo gehad, maar je weet min of meer wat het inhoud. De echte technische verklaring kan 9 van 10 studenten je niet geven.

dus we krijgen: dit is hashtable en zo kan je hem gebruiken, maar wat het echt technisch inhoud weten we niet.

Dan krijg je dus dit soort scenario's waarbij ik eigenlijk niet helemaal weet hoe het ECHT werkt, waardoor je vervolgens dit soort vragen op je forum krijgt.

edit: typos

[ Voor 3% gewijzigd door Laurens-R op 24-03-2007 13:26 ]

[RobIII]

En daarom heb ik ze indertijd op school een lange neus gegeven en ben ik gaan werken. Het gros van de goede programmeurs die ik ken zijn autodidact

[MrBucket]

Ik ben nog een belangrijke toepassing niet tegengekomen: het gebruik van een verzameling bits als een set, waarbij elk bitje (=vlaggetje) aangeeft of dat element wel of niet in de set zit.

Je kunt dan door bitwise and's en or's in 1 operatie intersections (doorsnedes) en unions (vereningingen) van twee sets uitvoeren.

Nu moet je deze constructie niet gaan gebruiken voor een willekeurige set aan gegevens, maar voor een klein aantal vaste waarden (bijv. de attributes van een file: Hidden, Readonly, Archive, System) werkt dit prima.

[Laurens-R]

@RobIII: Misschien was in de tijd mogelijk, maar het beeld wat wij meekrijgen is dat je tegenwoordig eigenlijk geen redelijke kans meer maakt op het moment dat je (formeel gezien) ongeschoold en/of onderopgeleid het bedrijfsleven in gaat.

Maar goed, vergeef me als ik in de toekomst nog met enigzins 'basic knowledge' vragen kom

[ Voor 3% gewijzigd door Laurens-R op 24-03-2007 13:36 ]

[chris]

Ik gebruik bitshiften wel eens als ik een lange array met booleans heb. Die kan je ook representeren als een integer, en mbv bitshiften kan je dan combinaties van die array opslaan. Een voorbeeld hiervan is permissies: in plaats van een array met 32 booleans gebruik ik vaak een int van grootte 2^32. Je loopt hier wel af en toe tegen de limiet van integers aan. Het nadeel is dat het niet perse heel schaalbaar is: stel dat je je datatype wilt veranderen van booleans naar iets anders, dan moet je veel code gaan omschrijven.

Ook is bitshiften een van de meest low-level operaties die er is. Het is razend snel en soms erg handig, dat is de reden dat het zelfs in de higher-level programmeertalen voorkomt.

[Verwijderd]

Momenteel volg ik een practicum waarbij ik functionaliteit aan een OS (MINIX3) moet toevoegen. Een opgave gaat over het schrijven van een defragmentatie-programma. Dan werk je met inode en zone bitmaps om te zien welke inodes en zones van een filesystem in gebruik zijn, en dus maak je flink gebruik van het checken en setten van bits.

[prototype]

RobIII schreef op zaterdag 24 maart 2007 @ 13:26:
En daarom heb ik ze indertijd op school een lange neus gegeven en ben ik gaan werken. Het gros van de goede programmeurs die ik ken zijn autodidact

Ik zie niet in hoe autodidact zijn en studeren mutually exclusive zijn, maar 'k ben dan ook nog student

[Janoz]

RobIII schreef op zaterdag 24 maart 2007 @ 13:26:
En daarom heb ik ze indertijd op school een lange neus gegeven en ben ik gaan werken. Het gros van de goede programmeurs die ik ken zijn autodidact

Het is maar goed dat je die 'ik' heb benadrukt . Mijn ervaring is eerder dat juist die type autodidacten het ontwikkelproces nog wel eens willen frustreren. Deze vaak erg eigenwijze personen hebben zo hun eigen maniertjes ontwikkeld, maar missen vaak een theoretische basis. Daarnaast hebben ze vaak lange tijd gefunctioneerd in een omgeving waarin ze geen sparringspartner op niveau hebben. Ze zijn het dus helemaal niet gewend en kunnen dan ook helemaal niet omgaan met op en aanmerkingen die ze krijgen wanneer ze iemand tegenkomen die wel de flaws in hun aangeleerde manieren aanwijst.

Maar goed, dat is dan weer mijn ervaring .

[RobIII]

Janoz schreef op zaterdag 24 maart 2007 @ 18:29:
[...]


Het is maar goed dat je die 'ik' heb benadrukt . Mijn ervaring is eerder dat juist die type autodidacten het ontwikkelproces nog wel eens willen frustreren. Deze vaak erg eigenwijze personen hebben zo hun eigen maniertjes ontwikkeld, maar missen vaak een theoretische basis. Daarnaast hebben ze vaak lange tijd gefunctioneerd in een omgeving waarin ze geen sparringspartner op niveau hebben. Ze zijn het dus helemaal niet gewend en kunnen dan ook helemaal niet omgaan met op en aanmerkingen die ze krijgen wanneer ze iemand tegenkomen die wel de flaws in hun aangeleerde manieren aanwijst.

Maar goed, dat is dan weer mijn ervaring .

Oh, maar dat ben ik wel met je eens; ik ken ook zat 'programmeurs' die (idd) autodidact zjin en precies voldoen aan 't profiel dat je nu beschrijft; ik verwoordde het misschien verkeerd, maar wat ik dus bedoelde te zeggen is dat de goede programmeurs vaak al ervaring voor/naast/buiten school opdeden maar idd wel hun theoretische basis op school vandaan haalden. De 'gewone' programmeurs (in mijn ervaring) zijn vaak de mensen die netjes hun school af maken, maar het 'hart' voor devven missen; die doen gewoon de kunstjes die ze geleerd hebben maar weten er 'het fijne' niet van; het werkt toch?

[CodeIT]

Ik heb dagelijks te maken met bitwise operators. In een uC (in mijn geval een PSoC) heb je vaak weinig code space en werkt veel met vlaggetjes (bits op een bepaalde locatie van een byte/word/etc.) In het begin is het wel lastig, maar het is eigenlijk heel logisch. Bij het teruglezen moet je alles alleen weer "decoderen" dus het komt de leesbaarheid niet echt ten goede.

[YopY]

Op het sub-onderwerp van zeg maar de autodidact vs de student; als een informatica-student zich echt interreseert in het vakgebied, dan zoekt hij de kleinere dingetjes die hij tijdens de opleiding niet leert uit, of in zijn eigen tijd, of na de opleiding.

Ik ben persoonlijk wel blij met m'n huidige HBO-opleiding; geeft niet alleen basiskennis van bepaalde programmeertalen, maar vooral de theoretische achtergrond van bijvoorbeeld software ontwerp, OOP, kunstmatige intelligentie, concurrent programmeren, enzovoorts.

En het grootste deel van de programmeertalen die we leren mogen we ook mooi zelf leren, zit tenminste geen leraar (meer) ons voor te kauwen wat we precies in moeten typen om wat voor elkaar te krijgen .

@topic: Ik heb zelf (tot nu toe) nog niet echt een toepassing herkend voor dit soort operaties. Als het echter een stuk sneller is dan het meer 'standaard' programmeren, dan wil ik me er wel eens goed in verdiepen.

Maar er is ook een stukje inzicht voor nodig, vooral op het gebied van binaire gegevens e.d. Op de opleiding krijgen (kregen) we wel info over hoe het binaire systeem werkt en hoe je er wat rekensommetjes op los kunt laten, maar niet echt hoe je het kunt gebruiken in hogere (of lagere?) programmeertalen. Is ook niet nodig, in theorie, zolang de compiler / interpreter het maar wel herkennen kan.

[H!GHGuY]

andere toepassingen zijn bvb ook:
protocollen (zoals al aangegeven TCP/IP e.d.) of ook veelal in toepassingen waar men hardware moet aanspreken. Hardware zal typisch een minimaal aantal bits/registers proberen gebruiken om data door te geven en dus kan het voorkomen dat je bvb in een 32 bit register een 5bit, 9bit, 10bit en 3 bit veldje tegenkomt. Die kun je dan uitmaskeren (AND operator) bij uitlezen of shiften en OR'en bij opstellen.

Ik moest onlangs een een protocol decoderen waarin heel veel bits gebruikt werden. Ik had dus een klasse geschreven die een bitstream las. dmv eenvoudige operaties (GetNextBits( nrOfBits) en SkipBits( nrOfBits) ) kon ik telkens de bits die ik nodig had extraheren uit de stream. Intern maakte dit gebruik van masking, shifts en meer van dat leuks...

[Paul]

Een vlak waar je ze enorm veel tegenkomt is bij embedded programmeren. Als je bijvoorbeeld met een microcontroller aan de gang gaat staat je code vol met dingen als:

C:

PORTD &= ~(1 << PD1); // Maak PD1 in PORTD laag
PORTD |= (1 << PD2); // Maak PD2 in PORTD hoog

[Icelus]

Een programmeertaal als C ondersteunt ook direct bitfields.
Bitfields voorbeeld.

[ Voor 14% gewijzigd door Icelus op 26-03-2007 16:19 ]

[MSalters]

Probeer maar eens een efficiente Sudoku solver te maken zonder bit ops.

[Confusion]

MSalters schreef op maandag 26 maart 2007 @ 20:09:
Probeer maar eens een efficiente Sudoku solver te maken zonder bit ops.

Daarbij is een goed algoritme belangrijker dan een efficiënte implementatie. Een huisgenoot van me heeft er een in Python geschreven die je niet snel zal verslaan.

[NielsNL]

Ik programmeer regelmatig PLC's (Siemens S7).
1 en al bitwise operators. Om maar efficient met je geheugen om te gaan, en de snelheid erin te houden. Of simpelweg omdat het in het communicatie protocol staat.