🔒 Locked

Flip Bits

Started by TheBluMage Dec 29, 2004 at 3:38 AM 11 replies 2k views

Original Post

Dec 29, 2004 at 3:38 AM

I need to flip the bits (backwards) around on a few long longs, and am wondering if anyone knows any more efficient way other than a loop full of shifts, ORs and ANDs. Example: This: First Bit -->01011101 10101110 10011000 00011111 00110110 10000001 10101100 11011101<-- Last Bit Would be changed into this: Previously Last Bit -->10111011 00110101 10000001 01101100 11111000 00011001 01110101 10111010<-- Previously First Bit Right now I'm using: for(int i = 63; i > -1; --i) { flippedNum |= (oldNum >> i) & 1; flippedNum <<= 1; } Not only is this ugly, but it's pretty slow. There must be a better way... mustn't there? Thanks in advance. EDIT: If someone knows of a good way to preform this on an arbitrary number of bytes that would work even better (rather than the individual long longs).

basananas

Dec 29, 2004 at 4:14 AM

Credits to Extrarius! I asked about the same a couple of days ago and he came up with this clever solution (slightly modified by me for 64 bits):

unsigned long x;x = ((x & 0x00000000FFFFFFFF) << 32) | ((x & 0xFFFFFFFF00000000) >> 32);x = ((x & 0x0000FFFF0000FFFF) << 16) | ((x & 0xFFFF0000FFFF0000) >> 16);x = ((x & 0x00FF00FF00FF00FF) << 8) | ((x & 0xFF00FF00FF00FF00) >> 8);x = ((x & 0x0F0F0F0F0F0F0F0F) << 4) | ((x & 0xF0F0F0F0F0F0F0F0) >> 4);x = ((x & 0x3333333333333333) << 2) | ((x & 0xCCCCCCCCCCCCCCCC) >> 2);x = ((x & 0x5555555555555555) << 1) | ((x & 0xAAAAAAAAAAAAAAAA) >> 1);

By the way; what is all this stuff about LONG? I needed it a couple of times but I never could store more than an int in it, else it would start moaning: "error: integer constant is too large for "long" type". That's also why the code above is untested

Any ideas why this is? Is it compiler/system specific?

fractoid

$fractoid$

fractoid

Dec 29, 2004 at 4:38 AM

Quote:
Original post by basananas
Any ideas why this is? Is it compiler/system specific?

I don't think VC++ supports the C99 standard (including the 'long long' data type), although others (Intel, GCC) do. You can always use a typedef equal to __int64, if you're worried about compatibility.

Oh, btw, Extrarius' method is brilliant. I'd rate him up if it weren't for this silly forum bug that stops me rating people up twice. [grin]

basananas

Dec 29, 2004 at 4:58 AM

Quote:
Original post by fractoid
Quote:
Original post by basananas
Any ideas why this is? Is it compiler/system specific?
I don't think VC++ supports the C99 standard (including the 'long long' data type), although others (Intel, GCC) do. You can always use a typedef equal to __int64, if you're worried about compatibility.

Oh, btw, Extrarius' method is brilliant. I'd rate him up if it weren't for this silly forum bug that stops me rating people up twice. [grin]

Ah, that's funny! I'm using DJGPP GCC :D

Spoonbender

122

Spoonbender

Dec 29, 2004 at 5:19 AM

Quote:
Original post by basananas
Credits to Extrarius! I asked about the same a couple of days ago and he came up with this clever solution (slightly modified by me for 64 bits):

*** Source Snippet Removed ***

By the way; what is all this stuff about LONG? I needed it a couple of times but I never could store more than an int in it, else it would start moaning: "error: integer constant is too large for "long" type". That's also why the code above is untested

Any ideas why this is? Is it compiler/system specific?

Because a long is 32 bit on x86 systems. It's 64 bit on an Athlon 64 though.
And yep, it is compiler and system specific (well, technically it's only compiler specific, but on an architecture that works with 32 bit, it'd be messy to use 64 bit integers)

TheBluMage

Author

TheBluMage

Dec 29, 2004 at 11:53 AM

This Extrarius guy is pretty smart. Works perfectly! Thanks!

Extrarius

234

Extrarius

Dec 29, 2004 at 1:51 PM

Thanks for the credit, but I must admit I saw that solution here(on GameDev) ages ago posted by somebody else and I just remebered the solution rather than coming up with it myself.

iMalc

182

iMalc

Dec 29, 2004 at 2:12 PM

Wow, what an excellent solution! It's so beautiful I had to snip it out and save it elsewhere in case I ever think of a use for it!

What do you use it for btw?

TheBluMage

Author

TheBluMage

Dec 29, 2004 at 7:15 PM

I'm writing a simple Chip8 interpreter, but when I had to draw the back buffer to the screen it ended up upside-down. (The bitmap I'm using is stored backwards.) So I was looking for a good way to flip over the screen.

fractoid

$fractoid$

fractoid

Dec 29, 2004 at 8:39 PM

Quote:
Original post by Extrarius
Thanks for the credit, but I must admit I saw that solution here(on GameDev) ages ago posted by somebody else and I just remembered the solution rather than coming up with it myself.

Ah, yes, but like Carmack's Sqrt it will forever be known by the name of the chap who made it famous. [wink]

Nice Coder

101

Nice Coder

Dec 31, 2004 at 6:37 AM

Nice, but how does it work?

Just curious.

From,
Nice coder

basananas

Dec 31, 2004 at 6:57 AM

Well, to put it easily: instead of swapping each individual bit on location i with the one on location (63 - i), now you use a single variable to swap a lot of them at once. I'll explain how it works.

Consider a 2-bit variable which you want to 'bit flip'. How would you do that? Simple: swap them!
In code, you could do this by ANDing out the first bit, then shifting it one to the right and then ANDing the second bit and shifting it to the left.
code:

situation: [bit0 bit1]swap bit0, bit1after: [bit1 bit0] << bit flipped!

Now, for a 4-bit variable. You just do the thing shown above twice, but on each side:

swap bit0, bit1swap bit2, bit3

Now you'll have: bit1,bit0,bit3,bit2 while you want to get bit3,bit2,bit1,bit0 (which is the bit-flipped order of a 4-bit variable)
You could consider the 2-bit pairs as individual units now, as they do obey the rule that they are odered in the right way (this method is based on recursive thinking which makes it so clever)

so when you add to the two swap-lines above:

swap (bit 1, bit0), (bit3,bit2)

you'll get: bit3,bit2,bit1,bit0

In code, you could do this by ANDing out the first 2 bits, then shifting it two to the right and then ANDing the 3th and 4th bit and shifting it to the left two bits.

Now, you can go on like this forever. The only rule is that the variable to be converted must consist out of 2^n bits, in which n is a whole number of course.

In the method used:

unsigned long x;x = ((x & 0x00000000FFFFFFFF) << 32) | ((x & 0xFFFFFFFF00000000) >> 32);x = ((x & 0x0000FFFF0000FFFF) << 16) | ((x & 0xFFFF0000FFFF0000) >> 16);x = ((x & 0x00FF00FF00FF00FF) << 8) | ((x & 0xFF00FF00FF00FF00) >> 8);x = ((x & 0x0F0F0F0F0F0F0F0F) << 4) | ((x & 0xF0F0F0F0F0F0F0F0) >> 4);x = ((x & 0x3333333333333333) << 2) | ((x & 0xCCCCCCCCCCCCCCCC) >> 2);x = ((x & 0x5555555555555555) << 1) | ((x & 0xAAAAAAAAAAAAAAAA) >> 1);

The 0x5555 and 0xAAAA part do the 1 bit-swap. 0x3333 and 0xCCCC the 2-bit swap and so on. Note that the order in which you put these commands doesn't matter at all.

Bas

Nice Coder

101

Nice Coder

Dec 31, 2004 at 5:40 PM

Thanks, thats certainly a neat way of doing it!

From,
Nice coder

Topic Locked

This topic has been locked by a moderator. New replies are not allowed.