reverse the bits in an interger?

[KG]

Could any one tell me how to reverse the bits in an interger?

 

[Richard Heathfield]

KG said:

Could any one tell me how to reverse the bits in an interger?

int reverse_bits(int n)
{
return ~n;
}

 

[Joachim Schmitz]

KG said:


int reverse_bits(int n)
{
return ~n;
}

That's inverting (1 turn into 0 and vice versa), not reverting. I understood
the OP wants the laest significant bit being the most significate, the 2nd
least being the second most and so on.

Bye, Jojo

 

[Michal Nazarewicz]

Could any one tell me how to reverse the bits in an interger?

Use a loop. For instance here you have a pseudocode (foo represents
ith bit):

#v+
output := 0;
FOR i := 0 TO number of bits:
IF input is set
set output[number of bits - i];
#v-

 

[Anonymous]

Could any one tell me how to reverse the bits in an interger?

First of all you need to know the size of integer, then you should go
somthing like this:

<snip>
int cnt=0,num=0,temp=0,res=0;
while(cnt<32) // here i consider size of integer to be 32-bit
{
temp=num & 1; // num contains the value of integer
res=res | temp;
num=0;
num=num>>1;
res=res<<1;
cnt++;
}
</snip>

I havent checked it. But still the idea will like this only. Also
check for the 32 iteration.


Thanks and Regards,
ar

 

[Chris Dollin]

Could any one tell me how to reverse the bits in an interger?

Use a loop. For instance here you have a pseudocode (foo represents
ith bit):

#v+
output := 0;
FOR i := 0 TO number of bits:

Suppose we have 2-bit integers, so number of bits is 2; and assuming
the usual reading of a FOR-TO loop ...

IF input is set

.... there will be an array indexing problem, since `i` will take on
the values 0, 1, 2 and either the index `0` or `2` will be wrong.
I suspect you want `number of bits - 1`. Or even better

for i from lowestBitIndex to highestBitIndex do

or, since the ordering doesn't matter

for i in validIndexes do

where `validIndexes` is the set of legal index values.

Encoding these is C is of course straightforward.

 

[Torsten Karwoth]

Could any one tell me how to reverse the bits in an interger?

---------snip------------
#include <string.h>
#include <stdio.h>

unsigned int revbits(unsigned int n)
{
unsigned int i, result = 0;

for (i = sizeof(int) * 8; i; --i)
{
result <<= 1;
if (n & 1)
result |= 1;
n >>= 1;
}
return result;
}

int main(void)
{
int i = (sizeof(int) * 8);

while (--i >= 0)
printf("IN:0x%.08x OUT:0x%.08x\n",
1<<i, revbits(1<<i));
return 0;
};
-----------snap----------
tk@localhost ~/test $ gcc -O2 -Wall -o test test.c
tk@localhost ~/test $ ./test
IN:0x80000000 OUT:0x00000001
IN:0x40000000 OUT:0x00000002
IN:0x20000000 OUT:0x00000004
IN:0x10000000 OUT:0x00000008
..............
IN:0x00000004 OUT:0x20000000
IN:0x00000002 OUT:0x40000000
IN:0x00000001 OUT:0x80000000

(the printf doesnt take sizeof(int) into account)

 

[Richard Heathfield]

Joachim Schmitz said:

That's inverting (1 turn into 0 and vice versa), not reverting.

It reverses the sense of each bit.

I understood the OP wants the laest significant bit being the most
significate, the 2nd least being the second most and so on.

And so you have (unwittingly?) made explicit the implicit lesson that
specifications *matter*.

 

[Army1987]

---------snip------------
#include <string.h>
#include <stdio.h>

unsigned int revbits(unsigned int n)
{
unsigned int i, result = 0;

for (i = sizeof(int) * 8; i; --i)

#include <limits.h> and use CHAR_BIT instead of 8.
Also, what if there are padding bits?
To be *totally* portable: (yes, most machines have 8-bit bytes and
no padding in unsigned int's, but that's not required by the C
standard)
#include <limits.h>

int count_bits(unsigned int n)
{
int result = 1;
while (n /= 2)
result++;
return result;
}

unsigned int revbits(unsigned int n)
{
unsigned int i, result = 0;
for (i = count_bits(UINT_MAX); i; --i)

{
result <<= 1;
if (n & 1)
result |= 1;
n >>= 1;
}
return result;
}

int main(void)
{
int i = (sizeof(int) * 8);

while (--i >= 0)
printf("IN:0x%.08x OUT:0x%.08x\n",
1<<i, revbits(1<<i));
return 0;
};
-----------snap----------
tk@localhost ~/test $ gcc -O2 -Wall -o test test.c
tk@localhost ~/test $ ./test
IN:0x80000000 OUT:0x00000001
IN:0x40000000 OUT:0x00000002
IN:0x20000000 OUT:0x00000004
IN:0x10000000 OUT:0x00000008
..............
IN:0x00000004 OUT:0x20000000
IN:0x00000002 OUT:0x40000000
IN:0x00000001 OUT:0x80000000

(the printf doesnt take sizeof(int) into account)

printf("IN:0x%.*x OUT:0x%.*x\n", CHAR_BIT * sizeof(int) / 4,
i<<i, CHAR_BIT * sizeof(int) / 4, revbits(1<<i));

 

[borkhuis]

That's inverting (1 turn into 0 and vice versa), not reverting. I understood
the OP wants the laest significant bit being the most significate, the 2nd
least being the second most and so on.

I did not understand that: the OP asked for to "reverse the bits in an
interger". This function reverses all bits in the integer. What you
are proposing is reversing the order of the bits, which is different.

Kind regards,
Johan Borkhuis

 

[Joachim Schmitz]

I did not understand that: the OP asked for to "reverse the bits in an
interger". This function reverses all bits in the integer. What you
are proposing is reversing the order of the bits, which is different.

Apparently (looking at the other answers in this thread) only you and
Richard understood it that way.
My point is that inverting (see
http://en.wikipedia.org/wiki/Inverse_(logic)) is not the same as
reverting.

Bye, Jojo

 

[Richard Heathfield]

Joachim Schmitz said:

Apparently (looking at the other answers in this thread) only you and
Richard understood it that way.

Nevertheless, it demonstrates that the specification was inadequate.
Over 28% of the respondents who had expressed an interpretation at the
time of writing have chosen to interpret "reverse the bits in an
integer" as "reverse the bits in an integer" rather than "reverse the
order of the bits in an integer".

My point is that inverting (see
http://en.wikipedia.org/wiki/Inverse_(logic)) is not the same as
reverting.

And reverting is not the same as reversing. And reversing is not the
same as reversing the order.

 

[osmium]

I did not understand that: the OP asked for to "reverse the bits in an
interger". This function reverses all bits in the integer. What you
are proposing is reversing the order of the bits, which is different.

Most people whose natural language is English would say "invert the *sense*
of the bits", for what you are describing.

 

[Army1987]

Joachim Schmitz said:


Nevertheless, it demonstrates that the specification was inadequate.
Over 28% of the respondents who had expressed an interpretation at the
time of writing have chosen to interpret "reverse the bits in an
integer" as "reverse the bits in an integer" rather than "reverse the
order of the bits in an integer".


And reverting is not the same as reversing. And reversing is not the
same as reversing the order.

http://dictionary.reference.com/browse/reverse
Yes, it is not 100% clear, but the most likely meaning is reversing
the order. (Anyway, since correct answers to both the meanings of
the question have been giving, arguing on which one was meant,
until the OP tells us, is sort-of waste of time.)

 

[Joachim Schmitz]

Joachim Schmitz said:


Nevertheless, it demonstrates that the specification was inadequate.

True, incomplete and leaves room for interpretation.

Over 28% of the respondents who had expressed an interpretation at the
time of writing have chosen to interpret "reverse the bits in an
integer" as "reverse the bits in an integer"

"invers the bits in an integer". (or "invert"?) A bit that is set when read
left to right is still set when read right to left, so revers wouldn't be
the right word. But hell, this isn't my native language...

rather than "reverse the order of the bits in an integer".

That could indeed have been the full specification.
Time for the OP to show up and confirm.

And reverting is not the same as reversing.

Oops, of course I meant reversing as the OP wrote.

And reversing is not the same as reversing the order.

What else? To me it is the same. What would 'reverse a string' be to you?
Turn the characters upside down?

Bye, Jojo

 

[Chris Dollin]

Most people whose natural language is English would say "invert the *sense*
of the bits", for what you are describing.

I'm not most people [1], but I think you're wrong.
For those with any interest in the matter at all,
I think they'd say "invert the bits", with
no nonsense about "sense". Or they'd use "flip".
Or "reverse". Or "complement".

I rather suspect that the OP meant "reverse
the order of the bits", but experience in
support on another mailing list suggests that
users asking about something different from
what they /say/ they're asking about
happens often enough that mere suspecting
doesn't bake the biscuit.

[1] For which we're all grateful.

 

[Richard Heathfield]

Army1987 said:

http://dictionary.reference.com/browse/reverse
Yes, it is not 100% clear, but the most likely meaning is reversing
the order.

To your mind, maybe. But it makes much more sense to write the
specification in a way that makes the requirement clear, right from the
start, to *everybody*.

(Anyway, since correct answers to both the meanings of
the question have been giving, arguing on which one was meant,
until the OP tells us, is sort-of waste of time.)

I am not, and have not been, arguing about which one the OP meant. I am
arguing that a clear specification is a sine qua non of a correct
program.

 

[Richard Heathfield]

Joachim Schmitz said:

What else? To me it is the same. What would 'reverse a string' be to
you? Turn the characters upside down?

It could reasonably be interpreted as ROT-((UCHAR_MAX + 1)/2).

 

[Richard Harter]

Well, in all this nonsense I have seen nothing that actually
reverses the order of bits in an unsigned int, independent of
sizeof int. So try this:

while (i) {
push(i & 1, stack);
i >>= 1;
}
while (notempty(stack)) {
i <<= 1;
j = pop(stack);
i != j;
}

with suitable declarations, stack, etc.

You have just exposed a second and much more serious ambiguity, to wit,
what precisely is meant by integer and how is it delimited. The issue is
what determines the number of leading zeroes and the length of the answer.
To illustrate suppose that our "integer" is 00110001 (8 bit words). Is the
correct answer 10001100 or 100011 or 00100011?

 

[CBFalconer]

First of all you need to know the size of integer, then you should
go somthing like this:

Well, in all this nonsense I have seen nothing that actually
reverses the order of bits in an unsigned int, independent of
sizeof int. So try this:

while (i) {
push(i & 1, stack);
i >>= 1;
}
while (notempty(stack)) {
i <<= 1;
j = pop(stack);
i != j;
}

with suitable declarations, stack, etc.