Solved

# bitwise operations, permutation

Posted on 2002-03-14
350 Views
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
Question by:YamSeng
• 3
• 2
• 2
• +2

LVL 12

Expert Comment

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

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

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

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

Do you want a specific set of permutations?
0

LVL 84

Expert Comment

Or are you asking how to generate all values with n bits set?
0

LVL 1

Author Comment

ozo,
yes, I do have a few sets of specific permutations.

yam
0

LVL 84

Expert Comment

So what specific permutations are you interested in?
0

LVL 5

Accepted Solution

BlackDiamond earned 20 total points
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

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.