• 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
YamSengAsked:
Who is Participating?
 
BlackDiamondCommented:
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
 
pjknibbsCommented:
I think your only option is to use the bit shifting approach--there isn't any faster way that I can think of.
0
 
jos010697Commented:
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
The IT Degree for Career Advancement

Earn your B.S. in Network Operations and Security and become a network and IT security expert. This WGU degree program curriculum was designed with tech-savvy, self-motivated students in mind – allowing you to use your technical expertise, to address real-world business problems.

 
YamSengAuthor 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
 
jos010697Commented:
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
 
ozoCommented:
Do you want a specific set of permutations?
0
 
ozoCommented:
Or are you asking how to generate all values with n bits set?
0
 
YamSengAuthor Commented:
ozo,
yes, I do have a few sets of specific permutations.

yam
0
 
ozoCommented:
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.

All Courses

From novice to tech pro — start learning today.