11 replies to this topic

[FireGator]

I was curious on the simplest (and fastest) method to flip a byte, and reverse each bit in a way which I can implement it when I need to without needing to look it up for reference, I find some of the functions being somewhat needlessly large and hard to remember.

An example of what I mean by reversing is this:

1010 = 0101

1110 = 0001

1100 = 0011 etc..

[Alexander]

My personal favourite (it can be written by memory for me) is to use a lookup table for speed, although not all entries are needed, it would be somewhat faster than some of the functions you may had seen:

uint8_t lookup[16] = {
   0x0, 0x8, 0x4, 0xC,
   0x2, 0xA, 0x6, 0xE,
   0x1, 0x9, 0x5, 0xD,
   0x3, 0xB, 0x7, 0xF };

uint8_t flipbits( uint8_t n ) 
{
   return (lookup[n & 0x0F] << 4) | lookup[n >> 4];
}

Quote

simplest (and fastest)

(You would need to choose one), although the fastest would be inline assembly.

[dbug]

If you are using only 8 bits, maybe the best way is to create a lookup table (only 256 bytes long) with all precomputed values.

To do it programmatically, I think this is the best option (for 32 bits numbers):

unsigned int swap(unsigned int value)

{

    value = ((value & 0xFFFF0000) >> 16) | ((value & 0x0000FFFF) << 16);

    value = ((value & 0xFF00FF00) >> 8) | ((value & 0x00FF00FF) << 8);

    value = ((value & 0xF0F0F0F0) >> 4) | ((value & 0x0F0F0F0F) << 4);

    value = ((value & 0xCCCCCCCC) >> 2) | ((value & 0x33333333) << 2);

    value = ((value & 0xAAAAAAAA) >> 1) | ((value & 0x55555555) << 1);

    return value;

}

[abzero]

XOR ftw.

1^1 = 0
1^0 = 1
0^1 = 1
0^0 = 0

So for a 4-bits, XOR against 1111, and the bit's are flipped.

[zoranh]

That's bitwise NOT operation:

int a = 5;
int b = ~a;

This is faster than table lookup because it's only one machine instruction, and it doesn't access memory apart from getting a and storing b.

Table lookup is useful to replace complex operations. For example, it is common in computer graphics to store complete pre-calculated tables of trigonometric functions and similar stuff to avoid calculating all of those functions every time when required.

[Momerath]

zoranh said:

That's bitwise NOT operation:

int a = 5;
int b = ~a;

This is faster than table lookup because it's only one machine instruction, and it doesn't access memory apart from getting a and storing b.

Table lookup is useful to replace complex operations. For example, it is common in computer graphics to store complete pre-calculated tables of trigonometric functions and similar stuff to avoid calculating all of those functions every time when required.

He's only dealing with a byte so using int would give the wrong value as it would also flip all the other bits he's not using. The post above yours using xor gives the correct results.

[zoranh]

I've just given an example with integer. Byte example would be with unsigned char instead of int.

XOR method is the only simple solution when part of the variable needs to be inverted, instead of the whole variable. When all bits should be inverted, then XOR boils down to bitwise NOT.

[Zer033]

What is the point of this (not being a smarty pants here, I'm genuinely curious)?

[Alexander]

I assume endianness or practice for network programming/a sort of low level application (compression).

@zoranh, NOT slipped my mind while writing this (I thought it was something much higher OP wanted to produce procedurally), I'm not sure why the many others that do not use it don't.

[Momerath]

zoranh said:

I've just given an example with integer. Byte example would be with unsigned char instead of int.

Not trying to be an ass (but probably succeeding anyway :)) but char is 8 bits and byte is 4 :)

[Alexander]

Momerath said:

Not trying to be an ass (but probably succeeding anyway :)) but char is 8 bits and byte is 4 :)

A byte since IBM systems existing before you were probably born, used 8 bit bytes.

[Momerath]

Nullw0rm said:

A byte since IBM systems existing before you were probably born, used 8 bit bytes.

Gah, you are correct. I've been working with people on some old 4004 stuff and they've gotten me in the habit of calling the word size a byte and it just came out :)