BIT SWAP METHOD

How do I reverse (swap) the order of bits for a fixed bit length (example 16 bits)?
Example: 0001 1010 1100 1000 to 00010011 0101000

Only functions included in the standard library of C language are used, but there are no specific restrictions on the work area.

c algorithm

2022-09-30 20:22

3 Answers

If you can assume that the bit length is the power of two, you can do this.
The code below supports up to 32 bits.

/* Reverse bits whose bit length is an integer x of bits */
unsigned reversebits (unsigned x, int bits)
{
    /*
     * Assume unsigned is 32 bits or more.
     * If it's 16 bits, erase case32: and the line directly below it.
     * Half the length of each mask can handle it.
     */
    assert(sizeof(x)*CHAR_BIT>=32);

    /* bits must be equal to or less than 32 power of 2 */
    assert(bits<=32);
    assert((bits&(bits-1)==0);

    switch(bits)
    {
    case32:
        x=((x&0x0000ffff)<<16)|((x>>16)&0x0000ff);
    case16:
        x=((x&0x00ff00ff)<<8)|((x>>8)&0x00ff00ff);
    case8:
        x=((x&0x0f0f0f0f)<<4)|((x>>4)&0x0f0f0f0f);
    case4:
        x=((x&0x33333333)<2)|((x>>2)&0x33333333);
    case2:
        x=((x&0x5555555)<1)|((x>>1)&0x5555555);
    default:
        break;
    }
    return x;
}

What you're doing

First, the upper half and the lower half of an integer are completely replaced.
Then, for the half, the half is replaced.
Similarly, if you repeat the replacement until you can't cut it in half, the whole thing will eventually be reversed.

example

Invert the 8-bit number of abcdefgh (a through h are 0 or 1, respectively).

Original number: abcdefgh
Replace half of the total: abcdefgh → efghabcd (upper codecase8: directly below)
Replace half more: efghab cd → gefcdab (upper codecase4: directly below)
Replace half more: ge f cdab → hg fed cba (upper code case2: directly below)

Now you can see that you finally get the hgfedcba and you can flip it.

2022-09-30 20:22

Code with a straightforward implementation of bit inversion, where x is the input value and b is the bit length.

 unsigned swapbit(unsigned x, intb){
  unsigned r = 0;
  while(b--){
    r<<=1;
    r | = (x & 1);
    x>>=1;
  }
  return;
}

LiveDemo: http://melpon.org/wandbox/permlink/XVsAjckDHC9g0W06

2022-09-30 20:22

static constant character BitReverseTable 256[256]= 
{
 #   define R2(n)n, n+2*64, n+1*64, n+3*64
 #   define R4(n)R2(n), R2(n+2*16), R2(n+1*16), R2(n+3*16)
 #   define R6(n)R4(n), R4(n+2*4), R4(n+1*4), R4(n+3*4)
     R6(0), R6(2), R6(1), R6(3)
};

unsigned int reverse bits (unsigned int x )
{
  const size_tsz =sizeof x*CHAR_BITS;
  constructed int MASK=(1U<CHAR_BITS) - 1U;
  unsigned intret = 0U;
  assert(CHAR_BITS==8); /*Table size is 256*/
  while(sz--){
    ret=(ret<<CHAR_BIT)|(unsigned int) BitReverseTable 256 [x&MASK];
    x>>=CHAR_BIT;
  }
  return;
}

How to create BitReverseTable 256 is here.

Example: 16-bit integer

 x | sz | ret
---------------------+-------+---------------------
0001 1010 1100 1000  |  2    | 0000 0000 0000 0000
0000 0000 0001 1010  |  1    | 0000 0000 0001 0011
0000 0000 0000 0000  |  0    | 0001 0011 0101 1000

0001 1010 1100 1000 --- > 00010011 0101000

2022-09-30 20:22

If you have any answers or tips

Popular Tags

python x 4647

android x 1593

java x 1494

javascript x 1427

c x 927

c++ x 878

ruby-on-rails x 696

php x 692

python3 x 685

html x 656