Solved

bitwise operations, permutation

Posted on 2002-03-14
9
370 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
Independent Software Vendors: We Want Your Opinion

We value your feedback.

Take our survey and automatically be enter to win anyone of the following:
Yeti Cooler, Amazon eGift Card, and Movie eGift Card!

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

Independent Software Vendors: We Want Your Opinion

We value your feedback.

Take our survey and automatically be enter to win anyone of the following:
Yeti Cooler, Amazon eGift Card, and Movie eGift Card!

Question has a verified solution.

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

Suggested Solutions

Title # Comments Views Activity
SQL Statment to match two tables in c# 6 81
How to organize data in excel ? 2 117
An API detour question 7 101
Secondary drive is failing... D Volume 11 48
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…
Summary: This tutorial covers some basics of pointer, pointer arithmetic and function pointer. What is a pointer: A pointer is a variable which holds an address. This address might be address of another variable/address of devices/address of fu…
The goal of this video is to provide viewers with basic examples to understand and use pointers in the C programming language.
The goal of this video is to provide viewers with basic examples to understand and use switch statements in the C programming language.

763 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