[Last Call] Learn how to a build a cloud-first strategyRegister Now

x
  • Status: Solved
  • Priority: Medium
  • Security: Public
  • Views: 458
  • Last Modified:

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
0
YamSeng
Asked:
YamSeng
  • 3
  • 2
  • 2
  • +2
1 Solution
 
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
 
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
Concerto Cloud for Software Providers & ISVs

Can Concerto Cloud Services help you focus on evolving your application offerings, while delivering the best cloud experience to your customers? From DevOps to revenue models and customer support, the answer is yes!

Learn how Concerto can help you.

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

Featured Post

Concerto's Cloud Advisory Services

Want to avoid the missteps to gaining all the benefits of the cloud? Learn more about the different assessment options from our Cloud Advisory team.

  • 3
  • 2
  • 2
  • +2
Tackle projects and never again get stuck behind a technical roadblock.
Join Now