• C

# bitwise operations, permutation

If I have 8bits and I want to permutate them in bit level, how should I go about it?

I've thought of shifting them, but I thought it'll means quite a number of lines just to permute 8 bits....

ie.
original bit
12345678

after permutation
26314857

thanks
YamSeng
LVL 1
###### Who is Participating?

Commented:
what about a function like the following.  For your example, you would pass it:

int permuteorder[] = {2,6,3,1,4,8,5,7}

char permute(char inbyte, int * permuteorder) {
char outbyte = 0;
int i;

for (i=0; i<=7; i++) {
outbyte = outbyte >> 1;
outbyte = (outbyte & 0x7f) | ((inbyte << (permuteorder[7-i] - 1)) & 0x80);

}
return outbyte & 0xff;
}

0

Commented:
I think your only option is to use the bit shifting approach--there isn't any faster way that I can think of.
0

Commented:
Note that you're actually talking _combinations_ here,
e.g. given 8 possible positions and two bits equal to 1,
there are only 7*8/2= 28 different 8 bits words with two
bits set to 1.

Why not build a table: 'unsigned char tab[256]' such
that for any bit combination i, tab[i] == j, such that
j is the next combination of i having the same number
of bits set to 1. e.g. tab[1]= 2, tab[2]= 4, tab[4]= 8 ...
tab[128]= 1, i.e. the links are cyclic.

The table needs to be built only once but can be used many times. Below you'll find some code that builds this table
for you:

/* count number of 1 bits in x */
int bits(unsigned char x) {

int b;

for(b= 0; x; ++b, x&= x-1);

return b;
}

void build_elem(unsigned char x) {

int b= bits(x);
unsigned char i;

for (i= 1; i; i++)
if (bits(x+i) == b) {
tab[x]= x+i;
x+= i;
if (tab[x])
break;
i= 0;
}
}

void build_tab() {

unsigned char i;

for (i= 1; i; i++)
build_elem(i);
}

kind regards,

Jos
0

Author Commented:
jos, your solution seems to be quite lengthy for my permutation needs.  I actually need different permutations, not just 1 fixed permutation....

Anyway, if I'm using shifting, can someone show me some examples for this permutation?

0

Commented:
The code I showed above just _builds_ a table. Keep the
table and get rid of the code afterwards. e.g. you want
to print all 8 bit values with 3 bits set:

#define NBITS(n) ((1<<(n))-1)

unsigned char b, c;

c= NBITS(3);
do {
b= c;
printf("%x\n", b);
c= tab[b];
}
while (c > b);

kind regards,

Jos
0

Commented:
Do you want a specific set of permutations?
0

Commented:
Or are you asking how to generate all values with n bits set?
0

Author Commented:
ozo,
yes, I do have a few sets of specific permutations.

yam
0

Commented:
So what specific permutations are you interested in?
0
Question has a verified solution.

Are you are experiencing a similar issue? Get a personalized answer when you ask a related question.

Have a better answer? Share it in a comment.