Bit rearrangement/manipulation in C

Question

I want to arrange bits in a byte, to result in a certain order. For example, if the starting byte is as follows 0 1 1 0 1 0 1 0 with bits labeled as 1 2 3 4 5 6 7 8, I want to arrange it so it matches the following positioning: 2 4 3 5 7 1 8 6 this results to: 1 0 1 1 1 0 0 0. What would be the most efficient way of doing so? I read about "look-up" tables but I am not sure how this works. Can someone give an example and an explanation of an efficient way of doing this bit rearrangement in C.

Could you please be more precise in what you want to change and how? Regarding your example it is not very clear for me what you want to achieve. E.g. the 4. bit in your original byte is 0 but in your resulting one it is 1... — ckruczek, Nov 23 '15 at 06:06
I edited my answer. Basically the byte is in the form 1 2 3 4 5 6 7 8 I want to rearrange the bits to 2 4 3 5 7 1 8 6. The 4th bit in my original is 0, it should be changed to the 5th bit (which is 1), since in 2 4 3 5 7 1 8 6, bit 5 is now in the 4th position. — unconditionalcoder, Nov 23 '15 at 06:11
in any case, i don't think it is possible to do that within 1-byte level — mangusta, Nov 23 '15 at 06:14
sometimes abstracting away detail make things harder. still don't know what is being asked. — Shakil Ahamed, Nov 23 '15 at 06:18
@silentboy he wants to get a particular permutation of original bit set — mangusta, Nov 23 '15 at 06:19

score 3 · Answer 1 · answered Nov 23 '15 at 06:36

3

You could create an array of "unsigned char" with 256 entries. The index into that array would be the current value of the byte to be converted, and the value at that entry would be the "converted" value.

Alternatively, you could use bit masking, and "if" statements... but it would less efficient.

Here's a snippet of the "array" method... with only a few values defined... ... and no output of the output in "binary-text" format.

#include<stdio.h>

unsigned char lkup[256] =
    { 0x00,            /* idx: 0  (0x00) */
      0x02,            /* idx: 1  (0x01) (0b00000001) */
      0x08,            /* idx: 2  (0x02) (0b00000010) */
      0x0a,            /* idx: 3  (0x03) (0b00000011) */
      0x01             /* idx: 4  (0x04) (0b00000100) */
      };

int main(int argc, char **argv)
{
    unsigned char wk = 3;

    printf("Input: %u  output: >%u\n", wk, lkup[wk]);
}

answered Nov 23 '15 at 06:36

TonyB

927
6
13

Thank you for your response. I'm a little confused, once you get the "converted" value for one of the bits, what do you do for the remainder of the bits? – unconditionalcoder Nov 23 '15 at 14:52
1

In the example "lkup[wk]" IS the new VALUE of the converted byte.... therefore, there are NO leftover bits... This example requires YOU to determine the "converted" byte for each of the 256 possible values of a byte. This methodology provides the fastest converstion... ckruczek's answer above will not force YOU to perform the bit swapping to come up with the answer, but it is probably slower (although probably not by a very much). But since this is probably an assignment, having you perform the calculations will probably be a good exercise. – TonyB Nov 23 '15 at 20:09
I like this way I just do not understand how look up tables work. Sorry, I'm very new to bit manipulation. ie: why did you choose those values for the table? – unconditionalcoder Nov 24 '15 at 02:20

score 2 · Accepted Answer · answered Nov 23 '15 at 06:35

I think I understood what he wants to achieve. This code may help you:

#include <stdio.h>
#include <stdint.h>

int main(void) {
  uint8_t original = 0b01101010;
  uint8_t positions[8] = {1,3,2,4,6,0,7,5};
  uint8_t result = 0;

  for(int i = 0; i < 8; i++)
  {   
     if(original & (1 << (7 - positions[i])))
        result |= (1 << (7-i));
  }
 return 0;
}

The first thing I have done is to create a byte that represents the original value as well as a array of the positions you want to change. Next step ist to look the original byte at the xth. position is zero or one and then shift the value in the result if so. The last for-loop is just for printing the result. I adjusted your indices to be zero-based.

Thank you! is this way more efficient than a lookup table? – unconditionalcoder Nov 23 '15 at 14:59 — unconditionalcoder, Nov 23 '15 at 14:59
I just refer to @TonyB's comment in his answer. – ckruczek Nov 24 '15 at 05:33 — ckruczek, Nov 24 '15 at 05:33

eXtranium · Answer 3 · 2017-10-17T22:17:23.157

Here is one way to change bit-positions. With & (and-operator) we select certain bits from the char and then shift them to new bit-positions. Finally all the shifted bits will happily join together by | (or-operator). The left shift << will move bits left and right shift >> to the right. I took the freedom to renumber bit-positions. 7 means most-significant bit on the left and 0 is least-significant bit, so the left and right shift operations descripts shifting direction correctly.

And why there is the shift operations first and then AND-operation for the last two rows? – Because char-type can be unsigned and if we do the right shift for the negative value, eg 11111000 (-8), the most-significant bit will be copied; 11111000 >> 2 will result (1 filled from this end -->) 11111110 (-2). (See Right shifting negative numbers in C.)

But back into function:

char changebitpositions (char ch) {

                                  // bit locations (- = don't care)
                                  // before      after
    return (ch & 0x20)            // --5----- => --5----- (no change)
        | ((ch & 0x49) << 1)      // -6--3--0 => 6--3--0-
        | ((ch & 0x12) << 2)      // ---4--1- => -4--1---
        | ((ch >> 5) & 0x04)      // 7------- => -----7--
        | ((ch >> 2) & 0x01);     // -----2-- => -------2

        // original and result:      76543210 => 64531702
}

Bit rearrangement/manipulation in C

3 Answers3