[C++] Tricky for-loops aangaande binaire indexeringen

[Verwijderd]

Ik probeer het volgende te doen:

Ik schrijf de elementen van een array van lengte 2^n=N volgens hun binaire representatie. Neem twee getallen j en k met j>=k die de posities voorstellen in de binaire representatie waarbij ik tel vanaf 0 vanaf de least significant bit (rechts dus). Nu wil ik de elementen eruitpikken die op posities k,...,j van 0 tot 2^(j-k+1) tellen in binair.

Dit wil ik allemaal mbv for-loopjes doen.

Een voorbeeld: stel n=4 bits en N=16. Dit zijn de indices:

C++:

   j k
   3210
   ====
0  0000
1  0001
2  0010
3  0011
4  0100
5  0101
6  0110
7  0111
8  1000
9  1001
10 1010
11 1011
12 1100
13 1101
14 1110
15 1111

Stel j=2 en k=1. Dan wil ik loopen over de volgende elementen:

C++:

0 0000
2 0010
4 0100
6 0110

en

C++:

1 0001
3 0011
5 0101
7 0111

en dan over

C++:

8  1000
10 1010
12 1100
14 1110

en

C++:

9  1001
11 1011
13 1101
15 1111

Een ander voorbeeld: als j=3 en k=1 wil ik de elementen hebben:

C++:

0  0000
2  0010
4  0100
6  0110
8  1000
10 1010
12 1100
14 1110

en vervolgens

C++:

1  0001
3  0011
5  0101
7  0111
9  1001
11 1011
13 1101
15 1111

Laatste voorbeeld: als j=k=3 dan wil ik loopen over

C++:

0  0000, 8  1000 en
1  0001, 9  1001 en 
2  0010, 10 1010 en 
3  0011, 11 1011 en
4  0100, 12 1100 en
5  0101, 13 1101 en
6  0110, 14 1110 en
7  0111, 15 1111

Dit is wat ik nu heb (werkt niet goed)

C++:

t = j-k+1;
for (p=0; p<N; p += 2^(j+1) ) {
  for (q=p; q<p+2^t; q += 2^(k+1) {
    // fout
    for (r=q; r<q+2^t; r += 2^k) {
      print r;
    }
  }
}

Ieder hulp zou ik zeer op prijs stellen!

[ Voor 4% gewijzigd door Verwijderd op 10-07-2006 13:54 ]

[.oisyn]

Je beseft wel dat ^ de XOR operator is en dus geen machten verheft he? Schrijf 2^i als (1 << i), wat betekent dat hij het getal 1 i bits naar links moet schuiven (en geeft dus hetzelfde resultaat).

Daarnaast zou ik het anders aanpakken. Blijkbaar zijn de bits tussen k en j het minst significant (want ze veranderen het snelst), en de overige bits meer significant. Ik zou dus gewoon een standaard loopje maken van 0..2^N-1, en dan de iterator zo vervormen dat de minst significante bits verschoven worden naar de plek k..j

[ Voor 26% gewijzigd door .oisyn op 10-07-2006 14:03 ]

[PhysicsRules]

Zoek eens wat informatie over bit-shift operators (<< >>). Die kunnen je hier mee helpen.

[Verwijderd]

.oisyn schreef op maandag 10 juli 2006 @ 14:01:
Je beseft wel dat ^ de XOR operator is en dus geen machten verheft he? Schrijf 2^i als (1 << i), wat betekent dat hij het getal 1 i bits naar links moet schuiven (en geeft dus hetzelfde resultaat).

Daarnaast zou ik het anders aanpakken. Blijkbaar zijn de bits tussen k en j het minst significant (want ze veranderen het snelst), en de overige bits meer significant. Ik zou dus gewoon een standaard loopje maken van 0..2^N-1, en dan de iterator zo vervormen dat de minst significante bits verschoven worden naar de plek k..j

Yup, maar ik dacht ik maak het niet te onoverzichtelijk door 1<<t enzo te typen ;p. Ik ken idd die bitshifts, maar ik zie niet helemaal hoe ik dat hier kan gebruiken. En is zo'n bitshift wel snel? En ik moet dan toch ook if statements gaan gebruiken toch? Is dat niet traag?

Want ik denk dat ik dan indices moet gaan vergelijken.

PhysicsRules schreef op maandag 10 juli 2006 @ 14:04:
Zoek eens wat informatie over bit-shift operators (<< >>). Die kunnen je hier mee helpen.

[ Voor 20% gewijzigd door Verwijderd op 10-07-2006 14:08 ]

[ReverendBizarre]

Verwijderd schreef op maandag 10 juli 2006 @ 14:07:
En is zo'n bitshift wel snel? En ik moet dan toch ook if statements gaan gebruiken toch? Is dat niet traag?

Bit shifts zijn razendsnel.

[.oisyn]

Waarom if-statements?

Neem nou je eerste voorbeeld met j=2 en k=1. In principe loop je gewoon van 0 t/m 15, alleen de bits op plek 0 t/m 1 moeten op plek 1 t/m 2 staan, en de bit die op plek 2 staat moet terug naar 0. En dan heb je precies de volgorde die je wilt hebben.
Dit is vrij simpel te doen, bits verschuiven kun je met << en >>, en met & (and) en | (or) kun je de juiste bits selecteren en samenvoegen.

Verder: j-k+1 is het aantal bits dat verplaatst moet worden, die bits moeten k plaatsen naar links. Vanaf plek j staan k bits die terug naar het begin moeten, oftewel j bits naar rechts.

Het masker voor de eerste n bits is natuurlijk (1 << n+1) - 1. Als je niet de eerste n wilt hebben, maar wilt beginnen vanaf plek m moet je dat masker natuurlijk m bits naar links schuiven: ((1 << n+1) - 1) << m

[ Voor 35% gewijzigd door .oisyn op 10-07-2006 14:19 ]

[Verwijderd]

.oisyn schreef op maandag 10 juli 2006 @ 14:13:
Waarom if-statements?

Neem nou je eerste voorbeeld met j=2 en k=1. In principe loop je gewoon van 0 t/m 15, alleen de bits op plek 0 t/m 1 moeten op plek 1 t/m 2 staan, en de bit die op plek 2 staat moet terug naar 0. En dan heb je precies de volgorde die je wilt hebben.
Dit is vrij simpel te doen, bits verschuiven kun je met << en >>, en met & (and) en | (or) kun je de juiste bits selecteren en samenvoegen.

Aha op die fiets . Thanks! Ik heb nog niet zoveel ervaring met & en | maar ik zal er es mee gaan klooien.

[ Voor 3% gewijzigd door Verwijderd op 10-07-2006 14:16 ]

[Verwijderd]

.oisyn schreef op maandag 10 juli 2006 @ 14:13:
Waarom if-statements?

Neem nou je eerste voorbeeld met j=2 en k=1. In principe loop je gewoon van 0 t/m 15, alleen de bits op plek 0 t/m 1 moeten op plek 1 t/m 2 staan, en de bit die op plek 2 staat moet terug naar 0. En dan heb je precies de volgorde die je wilt hebben.
Dit is vrij simpel te doen, bits verschuiven kun je met << en >>, en met & (and) en | (or) kun je de juiste bits selecteren en samenvoegen.

Verder: j-k+1 is het aantal bits dat verplaatst moet worden, die bits moeten k plaatsen naar links. Vanaf plek j staan k bits die terug naar het begin moeten, oftewel j bits naar rechts.

Het masker voor de eerste n bits is natuurlijk (1 << n+1) - 1. Als je niet de eerste n wilt hebben, maar wilt beginnen vanaf plek m moet je dat masker natuurlijk m bits naar links schuiven: ((1 << n+1) - 1) << m

Ok, ik snap hoe je met bitshifts de bits op plek 0 en 1 naar links schuift:

C++:

for (int i=0; i<N; i++) {
  ind = i<<k;
}

Maar hoe kan je dan specifieke bits naar rechts schuiven? Ik snap dat hele idee van masks nog niet helemaal.

[ Voor 6% gewijzigd door Verwijderd op 10-07-2006 14:53 ]

[ReverendBizarre]

Mijn tip is om het gewoon even uit te tekenen op papier. Zet twee waardes binair uitgeschreven boven elkaar en probeer dan te visualiseren hoe de bitwise operators deze waardes zouden manipuleren. Dat maakt het een stuk makkelijker om een beeld te krijgen van wat je nou eigenlijk doet.

[Verwijderd]

http://en.wikipedia.org/wiki/Bitwise_operation