Bitpatroon filteren van ongewenste bitjes...

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

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

[Chip]

Is C ja...

[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;

}

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

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

[biorsin]

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

[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

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

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;

}

[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

[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;

}

[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;

}

[Chip]

Is al opgelost hoor

[Rogier]

Wat doe je trouwens hier precies:

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.

[Chip]

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.