reverse binary number

[etlam]

hello,
I have a number and I need to have the binary digits reversed.
So if I have: 0...0101110 I want to have 0...0011101 (but if I have 011101000..., than this is also fine, since than I just divide. )
Is there a simpler way of computing the second number from the first one than doing this bit per bit?

Thanks in advance,
etlam
EDIT: I just noticed that I posted tis in the false forum, if a moderator could put it to Genaral Programming? thanks.
Sorry for my bad english

[suthers]

Download/Open the lintel manuals and have a look at the RCL/RCR/ROL/ROR-—Rotate part...
Jules

[etlam]

Thanks, but how does rotating help reversing the number?
I'm sorry if I have overseen something, but I don't see how to reverse the binary representation of a number with rotating.

Thanks in advance,
etlam

[suthers]

Sorry My fault, I didn't understand your post properly...
Jules

[jnc100]

Besides the obvious (portable) way of masking out each bit etc in a long loop in C, with x86 you can do:

(Intel Syntax, untested, cdecl)

Code: Select all

; unsigned long int reverse_bin(unsigned long src, unsigned long bitlength);

reverse_bin:
push ebp
mov ebp, esp

mov edx, [ebp + 8]
mov ecx, [ebp + 12]
xor eax, eax
.do_shift:rcl edx
rcr eax
loop .do_shift

pop ebp
ret

Regards,
John.

[suthers]

That's the sort of thing I was talking about, but it isn't computing, it's the same thing, except it will be faster than C because it uses optimized x86 instructions...
Jules

[stephenj]

There are six methods describing how to reverse bits using Bit Twiddling Hacks.

[suthers]

OMG in three OPS....
How the hell does that work?
Jules

edit: sorry there's an explanation underneath, but I wouldn't have thought of that in 100 years

[bewing]

@stephenj -- that's a hell of a nice link.

I just do it with a per-byte table lookup. If you do it more than once (so the table ends up in the cache) it's really fast.

[suthers]

Found another way, but it's prone to accuracy due to rounding:

Code: Select all

x = (1 - (x / 255)) * 255;

I haven't tested it completely, but I have a felling it could have rounding errors....
Jules

edit: This is for a byte obviously, to adapt it, all you have to do is change 255 to (2 ^ size_of_var) - 1... (I don't know why I'm saying this on forum...)

[suthers]

Nope wrong again, works only for the one example I tried (F0)...
Jules

[codemastersnake]

one slower and easy method would be:

# save binary in an array and reverse the string, then convert it back to binary.

Other would be:

# saving binary digit as a number like of integer datatype,
# then keep on dividing the number by then and get the remainfder until the number becomes zero (as we do in palindrome checking)
# save the remainder in another variable
# you have reversed binary digit!

[etlam]

Thank you all for the answers. They helped me a lot.

etlam

[chezzestix]

This is more of a question than a suggestion:

Couldnt you just use XOR? Just XOR the number against the lagest possible number in the bit size.

11111111 - 255
XOR
00110001
Yeilds
11001110

So the code would look like
XOR al,255
or
XOR ax,65535
etc...

Im sure someone must have thought of this before me but why isnt it used? We use its brother AND to mask so why not apply it here?

[Edit]
*facepalm*

[suthers]

This is more of a question than a suggestion:

Couldnt you just use XOR? Just XOR the number against the lagest possible number in the bit size.

11111111 - 255
XOR
00110001
Yeilds
11001110

So the code would look like
XOR al,255
or
XOR ax,65535
etc...

Im sure someone must have thought of this before me but why isnt it used? We use its brother AND to mask so why not apply it here?

chezzestix, that's not what he wants to do, he want's to make the first bit the last bit, the last the first, the second the before last, etc...
not invert....
Jules