Solved

bitwise operations, permutation

Posted on 2002-03-14
9
350 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
  • 3
  • 2
  • 2
  • +2
9 Comments
 
LVL 12

Expert Comment

by:pjknibbs
Comment Utility
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
Comment Utility
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
Comment Utility
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
 
LVL 4

Expert Comment

by:jos010697
Comment Utility
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
Do You Know the 4 Main Threat Actor Types?

Do you know the main threat actor types? Most attackers fall into one of four categories, each with their own favored tactics, techniques, and procedures.

 
LVL 84

Expert Comment

by:ozo
Comment Utility
Do you want a specific set of permutations?
0
 
LVL 84

Expert Comment

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

Author Comment

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

yam
0
 
LVL 84

Expert Comment

by:ozo
Comment Utility
So what specific permutations are you interested in?
0
 
LVL 5

Accepted Solution

by:
BlackDiamond earned 20 total points
Comment Utility
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

6 Surprising Benefits of Threat Intelligence

All sorts of threat intelligence is available on the web. Intelligence you can learn from, and use to anticipate and prepare for future attacks.

Join & Write a Comment

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…
An Outlet in Cocoa is a persistent reference to a GUI control; it connects a property (a variable) to a control.  For example, it is common to create an Outlet for the text field GUI control and change the text that appears in this field via that Ou…
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 how to use strings and some functions related to them 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

Need Help in Real-Time?

Connect with top rated Experts

9 Experts available now in Live!

Get 1:1 Help Now