Hello,
Hi I Need To Flip The Bits In An Integer (not Toggle Them But To Actually Get A Mirror Image With Respect To Bit Positions). The Problem Is That I Am Taking An Input Data In Integer Form From A System But It Places The Msb At 0th Position And Lsb At Last Position Whereas For Computation I Need To Do It The Opposite Way. I Have Thought Of Shift, Shift-rotate Etc But Can't Figure Out How To Do It . Please Help

Regards
Fskhan

Capitalizing the first letter of every single word makes your sentences harder to read.

>I Have Thought Of Shift, Shift-rotate Etc But Can't Figure Out How To Do It
You're probably trying to do it in-place and that's confusing you. Try building a whole new value by ORing the least significant bit into the new value, shifting the new value left and trimming the least significant bit from the old value:

#include <limits.h>
#include <stddef.h>

#define NBITS(x) ( sizeof (x) * CHAR_BIT )

int reverse_bits ( unsigned value )
{
  unsigned int rv = value;
  size_t n = NBITS ( value ) - 1;

  while ( ( value >>= 1U ) != 0 ) {
    rv = ( rv << 1U ) | ( value & 1U );
    --n;
  }

  return rv << n;
}
Comments
Nice
I like how the solution is wrong in multiple ways.
Nice little optimization of the loop.
unsigned int a = (int)0x12345678;
unsigned int b = 0;
int i = 0;

	for (i = 31; i > 0; --i)
	{
		b = b + ((a>>(31 - i))<<(31)>>(31 - i));
	}

this will also work...member of the ugly code club

Here's a rather neat solution that is relatively portable. It only reverses bytes though.

unsigned int reverse_bytes(unsigned int n) {

#if UINT_MAX > 4294967295

    n = ((n & 0xFFFFFFFF00000000) >> 32) | ((n & 0x00000000FFFFFFFF) << 32);

#endif

#if UINT_MAX > 65535

    n = ((n & 0xFFFF0000FFFF0000) >> 16) | ((n & 0x0000FFFF0000FFFF) << 16);

#endif

    n = ((n & 0xFF00FF00FF00FF00) >> 8) | ((n & 0x00FF00FF00FF00FF) << 8);
    n = ((n & 0xF0F0F0F0F0F0F0F0) >> 4) | ((n & 0x0F0F0F0F0F0F0F0F) << 4);

    return n;
}
unsigned int a = (int)0xffff0000;
	unsigned int b = 0;

	for (int i = 31; i >= 0; --i)
	{
		b = b + ((a>>(31 - i))<<(31)>>(31 - i));
	}

	return 0;

this will also work...member of the ugly code club

Yoinks people! Always the hard way!

unsigned long reverse_bits( unsigned long value )
{
  unsigned long result = 0;

  while (value)
  {
    result <<= 1;
    result += value & 1;
    value >>= 1;
  }

  return result;
}

>Yoinks people! Always the hard way!
The easy way isn't always the best way. As my case in point, your function is woefully broken in that it completely fails to do what it's supposed to do, which is reverse all of the bits. It doesn't work because in your quest for simplicity, you fail to take leading unset bits into account, when in the reversal they become critical.

> As my case in point, your function is woefully broken in that it completely fails to do what it's supposed to do, which is reverse all of the bits. (emphasis added)

Well, that depends entirely on what you mean by "all".

> It doesn't work because in your quest for simplicity, you fail to take leading unset bits into account, when in the reversal they become critical.

Yes, of course, you are right. So then:

unsigned long reverse_bits( unsigned long value )
{
  unsigned long result = 0;
  size_t n = NBITS( value );

  while (value)
  {
    result <<= 1;
    result += value & 1;
    value >>= 1;
    n--;
    }

  return result << n;
  }

Before complaining too loudly you should have noticed that my algorithm and yours are nearly identical.


[EDIT] BTW. I almost just told everyone to read your algorithm again... I should have, instead of hacking in that "forgets the leading zeros" one.[/EDIT]

> As my case in point, your function is woefully broken in that it completely fails to do what it's supposed to do, which is reverse all of the bits. (emphasis added)

Well, that depends entirely on what you mean by "all".

Not really. There is only one acceptable definition of "all" in this case

> It doesn't work because in your quest for simplicity, you fail to take leading unset bits into account, when in the reversal they become critical.

Yes, of course, you are right. So then:

Nothing like fixing a bug with a kludge. If you think about it, you'd find this is more straight forward:

unsigned long reverse_bits( unsigned long value )
{
    unsigned long result = 0;
    size_t n = NBITS( value );  // interesting -- I'll let you get away 
                    // with this assuming NBITS is defined for your 
                    // compiler

    while (n--)        // saves messing around later
    {
        result <<= 1;
        result += value & 1;
        value >>= 1;
        n--;
    }

  return result;
  }

Before complaining too loudly you should have noticed that my algorithm and yours are nearly identical.

Nearly may be true -- and immaterial. Nearly correct and correct are quite a bit different. I'd want my pilot to be "exactly" correct. If he's "nearly" correct, we might be landing short of the runway. But he did everything "nearly" right... :icon_rolleyes:

Before complaining too loudly you should have noticed that my algorithm and yours are nearly identical.

Man, as soon as I saw that sentence of yours with "nearly identical" I thought. Poor guy. He's is leaving himself open for incoming cheap criticism.

>Well, that depends entirely on what you mean by "all".
So at what point are you going to start arguing the definition of "is"? :icon_rolleyes: I mean, I'd love to hear what definition of "all" you derive from the first post in this thread that conflicts with mine.

>Before complaining too loudly you should have noticed
>that my algorithm and yours are nearly identical.
There's no gray area between correct and incorrect. Either it does what it's supposed to do, or it doesn't. "Nearly" falls into the "it doesn't" camp.

>// interesting -- I'll let you get away
>// with this assuming NBITS is defined for your
>// compiler
I think you can excuse that, as Duoas was probably using the macro I defined without explicitly defining it.

If you think about it, you'd find this is more straight forward:

If you look at Narue's, though, it's got a nice little optimization yours lacks.

If you look at Narue's, though, it's got a nice little optimization yours lacks.

True, but I try to keep it extremely simple for the newbies. They'll get into the optimization end of thing when they're ready. I'm sure instructors would look questioningly at a new student handing in code optimized in such a professional (advanced/expert) way.

But hers is much cooler! :icon_smile:

WaltP, why the vitrol? I've already make my opinion known that I think Narue's was fine to begin with...

By "all" I mean the number of bits required in the domain. Narue's assumes every bit possible in a machine word, and relies upon the compiler to properly handle conversion to other integer types. My original version only considered bits terminated by 1 Either interpretation may be correct depending on the problem domain.

A "perfect" solution would take the bit-domain as argument, and work against that.

Whenever you (or anyone) find yourself spouting off about the one true way of looking at things you almost always make yourself automatically wrong. The closest thing the OP said about his operational domain was to refer to MSB and LSB... So where, exactly, is MSB? It makes a significant difference!

WaltP, why the vitrol? I've already make my opinion known that I think Narue's was fine to begin with...

Vitriol? How so? I disagree, and backed up Narue's position. If you want the value 7 to be bit flipped and get 7, that's fine. I (and I'm fairly sure the OP) would want E0000000h.

Whenever you (or anyone) find yourself spouting off about the one true way of looking at things you almost always make yourself automatically wrong. The closest thing the OP said about his operational domain was to refer to MSB and LSB... So where, exactly, is MSB? It makes a significant difference!

If you think so. But I still hold that there was only one way to interpret "I Need To Flip The Bits In An Integer". Feel free to think differently. As the OP hasn't responded, your opinion is certainly valid.

This article has been dead for over six months. Start a new discussion instead.