Bitpatroon filteren van ongewenste bitjes...

Moderators: jkien, Xilvo

Reageer

Bericht 16-04-'09, 18:09

Chip

Gebruikersavatar
Berichten: 157

Bitpatroon filteren van ongewenste bitjes...

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...
Omhoog

Bericht 16-04-'09, 19:08

meijuh

Berichten: 202

Re: Bitpatroon filteren van ongewenste bitjes...

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.
Omhoog

Bericht 16-04-'09, 20:00

Chip

Gebruikersavatar
Berichten: 157

Re: Bitpatroon filteren van ongewenste bitjes...

Is C ja...
Omhoog

Bericht 17-04-'09, 00:11

Cycloon

Gebruikersavatar
Berichten: 4.810

Re: Bitpatroon filteren van ongewenste bitjes...

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;

}
Omhoog

Bericht 20-04-'09, 00:44

Vladimir Lenin

Gebruikersavatar
Berichten: 829

Re: Bitpatroon filteren van ongewenste bitjes...

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.
"Als je niet leeft zoals je denkt, zul je snel gaan denken zoals je leeft."

--Vladimir Lenin-- (Владимир Ильич Ульянов)
Omhoog

Bericht 20-04-'09, 00:55

Benm

Berichten: 12.262

Re: Bitpatroon filteren van ongewenste bitjes...

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.
Victory through technology
Omhoog

Bericht 20-04-'09, 01:23

biorsin

Berichten: 72

Re: Bitpatroon filteren van ongewenste bitjes...

De oplossing van Cycloon is goed als hetgeen je wilt timmeren altijd met 1 begint ;)
Omhoog

Bericht 20-04-'09, 02:03

Vladimir Lenin

Gebruikersavatar
Berichten: 829

Re: Bitpatroon filteren van ongewenste bitjes...

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
"Als je niet leeft zoals je denkt, zul je snel gaan denken zoals je leeft."

--Vladimir Lenin-- (Владимир Ильич Ульянов)
Omhoog

Bericht 20-04-'09, 18:36

Chip

Gebruikersavatar
Berichten: 157

Re: Bitpatroon filteren van ongewenste bitjes...

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...

Code: Selecteer alles

9876543210

1001101110

-0-1-0-1-0
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;

}
Omhoog

Bericht 20-04-'09, 19:54

Cycloon

Gebruikersavatar
Berichten: 4.810

Re: Bitpatroon filteren van ongewenste bitjes...

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 :P
Omhoog

Bericht 25-06-'09, 20:52

virtlink

Berichten: 158

Re: Bitpatroon filteren van ongewenste bitjes...

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;

}
"Niet gehinderd door enige kennis van zaken..."
Omhoog

Bericht 25-06-'09, 21:10

Rogier

Gebruikersavatar
Berichten: 5.679

Re: Bitpatroon filteren van ongewenste bitjes...

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;

}
In theory, there's no difference between theory and practice. In practice, there is.
Omhoog

Bericht 25-06-'09, 22:06

Chip

Gebruikersavatar
Berichten: 157

Re: Bitpatroon filteren van ongewenste bitjes...

Is al opgelost hoor ;)
Omhoog

Bericht 25-06-'09, 22:19

Rogier

Gebruikersavatar
Berichten: 5.679

Re: Bitpatroon filteren van ongewenste bitjes...

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.
In theory, there's no difference between theory and practice. In practice, there is.
Omhoog

Bericht 28-06-'09, 22:18

Chip

Gebruikersavatar
Berichten: 157

Re: Bitpatroon filteren van ongewenste bitjes...

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 :P en && 1 is vanwege eigen bool datatype had gemaakt maar daar nog niet voor stond.
Omhoog
Reageer

Terug naar “Informatica en programmeren”