Springen naar inhoud

Bitpatroon filteren van ongewenste bitjes...


  • Log in om te kunnen reageren

#1

Chip

    Chip


  • >100 berichten
  • 157 berichten
  • Ervaren gebruiker

Geplaatst op 16 april 2009 - 17:09

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

Dit forum kan gratis blijven vanwege banners als deze. Door te registeren zal de onderstaande banner overigens verdwijnen.

#2

meijuh

    meijuh


  • >100 berichten
  • 202 berichten
  • Ervaren gebruiker

Geplaatst op 16 april 2009 - 18:08

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.

#3

Chip

    Chip


  • >100 berichten
  • 157 berichten
  • Ervaren gebruiker

Geplaatst op 16 april 2009 - 19:00

Is C ja...

#4

Cycloon

    Cycloon


  • >1k berichten
  • 4810 berichten
  • VIP

Geplaatst op 16 april 2009 - 23:11

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:

while(getal > 0) {
   if(getal%2==1)
	  // 1 in het patroon
   else
	  // 0 in het patroon
   getal/=2;
}

Veranderd door Cycloon, 16 april 2009 - 23:12


#5

Vladimir Lenin

    Vladimir Lenin


  • >250 berichten
  • 829 berichten
  • Ervaren gebruiker

Geplaatst op 19 april 2009 - 23:44

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-- (Владимир Ильич Ульянов)

#6

Benm

    Benm


  • >5k berichten
  • 8789 berichten
  • VIP

Geplaatst op 19 april 2009 - 23:55

Oplossing van cycloon klinkt goed - scheelt je de string conversie en terug.

Je kan het zo uitbouiwen:

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

#7

biorsin

    biorsin


  • >25 berichten
  • 72 berichten
  • Ervaren gebruiker

Geplaatst op 20 april 2009 - 00:23

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

#8

Vladimir Lenin

    Vladimir Lenin


  • >250 berichten
  • 829 berichten
  • Ervaren gebruiker

Geplaatst op 20 april 2009 - 01:03

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-- (Владимир Ильич Ульянов)

#9

Chip

    Chip


  • >100 berichten
  • 157 berichten
  • Ervaren gebruiker

Geplaatst op 20 april 2009 - 17:36

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

9876543210

1001101110
-0-1-0-1-0

ben tenslotte op de volgende code gekomen... (negatieve logica)
#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;
}

Veranderd door Wouser, 20 april 2009 - 17:39


#10

Cycloon

    Cycloon


  • >1k berichten
  • 4810 berichten
  • VIP

Geplaatst op 20 april 2009 - 18:54

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

#11

virtlink

    virtlink


  • >100 berichten
  • 158 berichten
  • Ervaren gebruiker

Geplaatst op 25 juni 2009 - 19:52

Als ik het probleem goed begrijp, zou dit ook moeten werken:
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..."

#12

Rogier

    Rogier


  • >5k berichten
  • 5679 berichten
  • VIP

Geplaatst op 25 juni 2009 - 20:10

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

#13

Chip

    Chip


  • >100 berichten
  • 157 berichten
  • Ervaren gebruiker

Geplaatst op 25 juni 2009 - 21:06

Is al opgelost hoor ;)

#14

Rogier

    Rogier


  • >5k berichten
  • 5679 berichten
  • VIP

Geplaatst op 25 juni 2009 - 21:19

Wat doe je trouwens hier precies:

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.

#15

Chip

    Chip


  • >100 berichten
  • 157 berichten
  • Ervaren gebruiker

Geplaatst op 28 juni 2009 - 21:18

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.





0 gebruiker(s) lezen dit onderwerp

0 leden, 0 bezoekers, 0 anonieme gebruikers

Ook adverteren op onze website? Lees hier meer!

Gesponsorde vacatures

Vacatures