?
Solved

bitwise operations, permutation

Posted on 2002-03-14
9
Medium Priority
?
397 Views
Last Modified: 2010-04-15
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
Comment
Question by:YamSeng
[X]
Welcome to Experts Exchange

Add your voice to the tech community where 5M+ people just like you are talking about what matters.

  • Help others & share knowledge
  • Earn cash & points
  • Learn & ask questions
  • 3
  • 2
  • 2
  • +2
9 Comments
 
LVL 12

Expert Comment

by:pjknibbs
ID: 6863940
I think your only option is to use the bit shifting approach--there isn't any faster way that I can think of.
0
 
LVL 4

Expert Comment

by:jos010697
ID: 6864638
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
 
LVL 1

Author Comment

by:YamSeng
ID: 6867024
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
What does it mean to be "Always On"?

Is your cloud always on? With an Always On cloud you won't have to worry about downtime for maintenance or software application code updates, ensuring that your bottom line isn't affected.

 
LVL 4

Expert Comment

by:jos010697
ID: 6867458
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
 
LVL 84

Expert Comment

by:ozo
ID: 6867478
Do you want a specific set of permutations?
0
 
LVL 84

Expert Comment

by:ozo
ID: 6867519
Or are you asking how to generate all values with n bits set?
0
 
LVL 1

Author Comment

by:YamSeng
ID: 6867564
ozo,
yes, I do have a few sets of specific permutations.

yam
0
 
LVL 84

Expert Comment

by:ozo
ID: 6867597
So what specific permutations are you interested in?
0
 
LVL 5

Accepted Solution

by:
BlackDiamond earned 80 total points
ID: 6869421
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

VIDEO: THE CONCERTO CLOUD FOR HEALTHCARE

Modern healthcare requires a modern cloud. View this brief video to understand how the Concerto Cloud for Healthcare can help your organization.

Question has a verified solution.

If you are experiencing a similar issue, please ask a related question

Have you thought about creating an iPhone application (app), but didn't even know where to get started? Here's how: ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ Important pre-programming comments: I’ve never tri…
This tutorial is posted by Aaron Wojnowski, administrator at SDKExpert.net.  To view more iPhone tutorials, visit www.sdkexpert.net. This is a very simple tutorial on finding the user's current location easily. In this tutorial, you will learn ho…
The goal of this video is to provide viewers with basic examples to understand and use structures in the C programming language.
The goal of this video is to provide viewers with basic examples to understand recursion in the C programming language.
Suggested Courses

764 members asked questions and received personalized solutions in the past 7 days.

Join the community of 500,000 technology professionals and ask your questions.

Join & Ask a Question