1 van 1
Bitpatroon filteren van ongewenste bitjes...
Geplaatst: do 16 apr 2009, 18:09
door Chip
Ik heb bijvoorbeeld het volgende bitpatroon...
10101010101, nu wil ik alle nullen eruit hebben waardoor vervolgens het volgende bitpatroon overblijft 111111
Iemand enig idee hoe ik dit doe? Heb al tijdje zitten nadenken maar niets schiet me te binnen...
Re: Bitpatroon filteren van ongewenste bitjes...
Geplaatst: do 16 apr 2009, 19:08
door meijuh
Is dit in C of in java? Van java weet ik dat je het zo om kunt zetten naar een String en dan de 1 tjes counten.
In C weet ik ook zo geen trucje, als ik er 1 heb meld ik het.
Re: Bitpatroon filteren van ongewenste bitjes...
Geplaatst: do 16 apr 2009, 20:00
door Chip
Is C ja...
Re: Bitpatroon filteren van ongewenste bitjes...
Geplaatst: vr 17 apr 2009, 00:11
door Cycloon
Is dit bitpatroon gewoon beschikbaar als string ofzo? Of heb je een gewoon getal voor handen waarvan je het bitpatroon gaat gebruiken?
Indien het eerste kan je natuurlijk gewoon simpelweg alle tekens overlopen. In het 2de geval kan je volgend algoritme gebruiken:
Code: Selecteer alles
while(getal > 0) {
if(getal%2==1)
// 1 in het patroon
else
// 0 in het patroon
getal/=2;
}
Re: Bitpatroon filteren van ongewenste bitjes...
Geplaatst: ma 20 apr 2009, 00:44
door Vladimir Lenin
Hoe werk je precies met bits, bij mijn weten is de byte het kleinste datatype in iedere programmeertaal, toegegeven een boolean zou een bit kunnen zijn, maar in het geheugen wordt dat toch als 1 byte gerekend (een enorme verspilling als je het mij vraagt) anders denk ik wel dat ik enkele truckjes uit de doos kan halen.
Re: Bitpatroon filteren van ongewenste bitjes...
Geplaatst: ma 20 apr 2009, 00:55
door Benm
Oplossing van cycloon klinkt goed - scheelt je de string conversie en terug.
Je kan het zo uitbouiwen:
Code: Selecteer alles
result = 1;
while(getal > 0) {
if(getal%2==1)
{
result = result * 2; // of result << 1;
}
getal = getal / 2; // of getal >> 1;
}
result = result - 1;
Hoe werk je precies met bits, bij mijn weten is de byte het kleinste datatype in iedere programmeertaal, toegegeven een boolean zou een bit kunnen zijn, maar in het geheugen wordt dat toch als 1 byte gerekend (een enorme verspilling als je het mij vraagt)
Is niet helemal waar, in veel talen voor embedded processors kun je individuele bits van een byte aanspreken en zo tot 8 bools stallen in 1 byte geheugen. Op x86 zal echter niemand malen om de verloren 7 bits per bool.
Re: Bitpatroon filteren van ongewenste bitjes...
Geplaatst: ma 20 apr 2009, 01:23
door biorsin
De oplossing van Cycloon is goed als hetgeen je wilt timmeren altijd met 1 begint
Re: Bitpatroon filteren van ongewenste bitjes...
Geplaatst: ma 20 apr 2009, 02:03
door Vladimir Lenin
akkoord dat je ze kunt oproepen maar ik vroeg me af of je ze als samengestelde bytes representeerd (als byte,...) of in een array van bijvoorbeeld booleans
Re: Bitpatroon filteren van ongewenste bitjes...
Geplaatst: ma 20 apr 2009, 18:36
door Chip
Bedankt voor de vele reacties alleen was ik vergeten dat een 0 en 1 ook anders om kunnen zijn dus bijvoorbeeld het volgende patroon...
1001101110
Hij had dan vervolgens alle oneven of even bits moeten filteren... waardoor er bijvoorbeeld wanneer alle even (of oneven) bits zijn gefiltert dit eruit komt...
ben tenslotte op de volgende code gekomen... (negatieve logica)
Code: Selecteer alles
#include <stdio.h>
#include <stdlib.h>
unsigned short issetBit(const unsigned int bit, const unsigned int bits)
{
return (~bits & (0x01 << bit)) && 1;
}
int main()
{
int i, bit1 = 0, bit2 = 0, bits = 0x269; // 1001101001
for (i = 0; i < 10; i++) {
if (issetBit(i, bits)) {
if (i & 1)
bit1 |= 0x01 << (i / 2);
else
bit2 |= 0x01 << (i / 2);
}
}
printf("Filter bit1: %x\n", bit1);
printf("Filter bit2: %x\n", bit2);
fflush(stdin);
getchar();
return 0;
}
Re: Bitpatroon filteren van ongewenste bitjes...
Geplaatst: ma 20 apr 2009, 19:54
door Cycloon
De oplossing van Cycloon is goed als hetgeen je wilt timmeren altijd met 1 begint
Als je wat voorlopende nulletjes hebt werkt het niet natuurlijk, da's een feit, maar in zijn voorbeeld gaf hij dan ook aan dat hij bv alle eentjes wou filteren. Elk probleem vraagt een andere oplossing natuurlijk
Re: Bitpatroon filteren van ongewenste bitjes...
Geplaatst: do 25 jun 2009, 20:52
door virtlink
Als ik het probleem goed begrijp, zou dit ook moeten werken:
Code: Selecteer alles
int bereken(int input)
{
int a = 1;
int i = 0;
int result = 0;
while (i < (32 / 2))
{
// Pak de juiste bit,
// schuif hem op de juiste plaats
// en OR hem aan het resultaat.
result |= (input & a) >> i;
// De plaats schuift steeds één op.
i++;
// De juiste bit schuift twee op.
a << 2;
}
return result;
}
Re: Bitpatroon filteren van ongewenste bitjes...
Geplaatst: do 25 jun 2009, 21:10
door Rogier
Dat 'bitpatroon', in welke vorm heb je dat, en hoe lang is dat patroon? Is het een losse int? Een pointer naar een stuk geheugen? Lees je een file? Een of andere stream die ergens binnenkomt?
En je zegt dat je de nullen eruit wilt filteren. Dan hou je een setje enen over, maar als je dat opslaat (in een byte of int bijvoorbeeld) kunnen er bovenin nog nullen zitten op de ongebruikte locaties: je kunt het resultaat minimaal per hele byte tegelijk opslaan, en als er bijvoorbeeld 6 enen in zitten moet je dus alsnog 2 nullen opslaan.
Wil je niet gewoon het aantal enen tellen?
Enfin, ervanuit gaande dat je bitpatroon een normale int is, lijkt me dit de meest efficiënte oplossing: (in C++)
Code: Selecteer alles
int TelAantalEnen( int x )
{
static const int bitSize = sizeof(x)*8;
int aantal = 0;
for (int i=0; i<bitSize; i++)
{
if (x&(1<<i)) aantal++;
}
return aantal;
}
int VerwijderNullen( int x )
{
return (1<<TelAantalEnen(x))-1;
}
Re: Bitpatroon filteren van ongewenste bitjes...
Geplaatst: do 25 jun 2009, 22:06
door Chip
Is al opgelost hoor
Re: Bitpatroon filteren van ongewenste bitjes...
Geplaatst: do 25 jun 2009, 22:19
door Rogier
Wat doe je trouwens hier precies:
Wouser schreef:Code: Selecteer alles
unsigned short issetBit(const unsigned int bit, const unsigned int bits)
{
return (~bits & (0x01 << bit)) && 1;
}
Vanwaar de ~, daarmee inverteer je de bits, je wilt toch checken of hij op 1 staat? Als dat het geval is returnt je issetBit functie volgens mij nu juist 0.
De enige reden waarom dit nu goed
lijkt te gaan, is omdat in je testgetal (0x269) toevallig alle paren even en oneven bits ongelijk zijn, waardoor de twee resultaten (bit1 en bit2) in feite verwisseld zijn, wat niet direct opvalt.
Probeer maar eens een testgetal met een aantal enen achter elkaar (bijvoorbeeld 0xfff), bit1 en bit2 zullen dan beide 0 zijn volgens mij
Verder is de && 1 overbodig. Het linker deel is waar of niet, en AND'en met 1 verandert er daar niks aan.
Re: Bitpatroon filteren van ongewenste bitjes...
Geplaatst: zo 28 jun 2009, 22:18
door Chip
Rogier schreef:Wat doe je trouwens hier precies:
Vanwaar de ~, daarmee inverteer je de bits, je wilt toch checken of hij op 1 staat? Als dat het geval is returnt je issetBit functie volgens mij nu juist 0.
De enige reden waarom dit nu goed
lijkt te gaan, is omdat in je testgetal (0x269) toevallig alle paren even en oneven bits ongelijk zijn, waardoor de twee resultaten (bit1 en bit2) in feite verwisseld zijn, wat niet direct opvalt.
Probeer maar eens een testgetal met een aantal enen achter elkaar (bijvoorbeeld 0xfff), bit1 en bit2 zullen dan beide 0 zijn volgens mij
Verder is de && 1 overbodig. Het linker deel is waar of niet, en AND'en met 1 verandert er daar niks aan.
Negatieve logica
en && 1 is vanwege eigen bool datatype had gemaakt maar daar nog niet voor stond.